【数据结构】排序详解二
文章目录
- 计数排序
- 快速排序
- 归并排序
计数排序
计数排序的基本思想是把每个数出现的次数记录在另外一个数组中，然后我们知道数组下标是有大小的，这样根据数组下标的从小到大去让我们的原数组有序
我们既然要创建一个数组，那么就表明原数组的值的范围不能差别太大，要尽量集中，这样我们创建的数组就可以比较小，就可以满足我们的需求了
void CountSort(int* a, int n) {int max = a[0];int min = a[0];for (int i = 0; i < n; i++) {if (a[i] > max) {max = a[i];}if (a[i] < min) {min = a[i];}}int num = max - min + 1;int* tmp = (int*)malloc(sizeof(int) * num);if (tmp == NULL) {perror("malloc failed");exit(-1);}memset(tmp, 0, sizeof(int) * num);for (int i = 0; i < n; i++) {tmp[a[i] - min]++;}int j = 0;for (int i = 0; i < num; i++) {while (tmp[i]--) {a[j++] = i + min;}}
}
我们创建数组的话肯定不能说下标从0到原数组中的最大值，而范围应该是原数组中从最小值到最大值的那么多范围。这样既缩小了数组的大小，也方便找到原数组中的每个值。
快速排序
快速排序的基本思想就是选取一个key值，把小于key值的放在左边，把大于等于key值的放在右边，这样key就值可以放到它最终该待的位置了，并且同样按照这个思路，去递归处理key左边的值和key右边的值。这就是Hoare大佬最开始发明的排序方法
void QuickSort1(int* a, int begin, int end) {if (begin >= end) {return;}int tmp = a[begin];int left = begin;int right = end;while (left < right) {while (a[right] >= tmp&&left<right) {right--;}while (a[left] <= tmp&&left<right) {left++;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[begin]);QuickSort1(a, begin, left - 1);QuickSort1(a, left + 1, end);
}
之后人们觉得这个思路坑很多，很容易写错，于是根据这个思路就发明了挖坑法，就是最初的key值的位置变成了一个坑，从数组的右边找小值放到坑中，坑就更新，再从左边找大值放到右边的新坑中，坑再更新，直到两个指针相遇，然后还是对左边和右边用递归。
void QuickSort2(int* a, int begin, int end) {if (begin >= end) {return;}int tmp = a[begin];int pit = begin;int left = begin;int right = end;while (left < right) {while (left < right && a[right] >= tmp) {right--;}a[pit] = a[right];pit = right;while (left < right && a[left] <= tmp) {left++;}a[pit] = a[left];pit = left;}a[pit] = tmp;QuickSort2(a, begin, pit - 1);QuickSort2(a, pit+1, end);
}
后人又提出了前后指针法，两个指针都是从最左边开始，找小于key值的，放到左边，直到找不到。慢指针的这个位置就是存放key值的，最后也是递归实现前面的和后面的部分。
void QuickSort3(int* a, int begin, int end) {if (begin >= end) {return;}int tmp = a[begin];int left = begin;int right = begin;while (right <= end) {if (tmp > a[right]&&++left!=right) {Swap(&a[left], &a[right]);}right++;}Swap(&a[begin], &a[left]);QuickSort3(a, begin, left - 1);QuickSort3(a, left + 1, end);
}
快速排序可以递归实现，当然也可以非递归实现，这里就要借用栈了，用栈去保存我们要处理的begin和end值，取出来处理完后再保存它的子范围的两个范围值。直到栈为空为止
void QuickSortNonR(int* a, int begin, int end) {ST st;STInit(&st);STPush(&st, end);STPush(&st, begin);while (!STEmpty(&st)) {int left = STTop(&st);STPop(&st);int right = STTop(&st);STPop(&st);int tmp = a[left];int left1 = left;int right1 = right;while (left < right) {while (left < right && a[right] >= tmp) {right--;}while (left < right && a[left] <= tmp) {left++;}Swap(&a[left], &a[right]);}Swap(&a[left1], &a[left]);if (left1 < left - 1) {STPush(&st, left-1);STPush(&st, left1);}if (left+1 < right1) {STPush(&st, right1);STPush(&st, left + 1);}}
}
这里的一些有关栈的函数可以去看我以前的博客
链接：栈和队列
归并排序
归并排序也可以用递归实现，先将整个数组的小部分有序，然后有序的范围再扩大，然后使整个数组有序。
void _MergeSort(int* a, int* tmp, int begin, int end) {if (begin >= end)return;int mid = (begin + end) / 2;int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;_MergeSort(a, tmp, begin1, end1);_MergeSort(a, tmp, begin2, end2);int cur = begin;while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] < a[begin2]) {tmp[cur++] = a[begin1++];}else {tmp[cur++] = a[begin2++];}}while (begin1 <= end1) {tmp[cur++] = a[begin1++];}while (begin2 <= end2) {tmp[cur++] = a[begin2++];}memcpy(a+begin, tmp+begin, sizeof(int)*(end - begin + 1));}
void MergeSort(int* a, int n) {int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL) {perror("malloc failed");exit(-1);}_MergeSort(a, tmp, 0, n - 1);free(tmp);
}
能用递归实现当然也能用非递归实现，下标范围是有规律的，所以可以利用这个特性去实现非递归
void MergeSortNonR(int* a, int n) {int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL) {perror("malloc failed");exit(-1);}int gap = 1;while (gap < n) {gap *= 2;for (int i = 0; i < n; i += gap) {int begin1 = i;int begin2 = i + gap / 2;int end1 = begin2 - 1;int end2 = begin2 + end1 - begin1;if (begin2 >= n) {break;}if (end2 >= n) {end2 = n - 1;}int cur = begin1;while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] < a[begin2]) {tmp[cur++] = a[begin1++];}else {tmp[cur++] = a[begin2++];}}while (begin1 <= end1) {tmp[cur++] = a[begin1++];}while (begin2 <= end2) {tmp[cur++] = a[begin2++];}memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}}
}
【数据结构】排序详解二
文章目录
- 计数排序
- 快速排序
- 归并排序
计数排序
计数排序的基本思想是把每个数出现的次数记录在另外一个数组中，然后我们知道数组下标是有大小的，这样根据数组下标的从小到大去让我们的原数组有序
我们既然要创建一个数组，那么就表明原数组的值的范围不能差别太大，要尽量集中，这样我们创建的数组就可以比较小，就可以满足我们的需求了
void CountSort(int* a, int n) {int max = a[0];int min = a[0];for (int i = 0; i < n; i++) {if (a[i] > max) {max = a[i];}if (a[i] < min) {min = a[i];}}int num = max - min + 1;int* tmp = (int*)malloc(sizeof(int) * num);if (tmp == NULL) {perror("malloc failed");exit(-1);}memset(tmp, 0, sizeof(int) * num);for (int i = 0; i < n; i++) {tmp[a[i] - min]++;}int j = 0;for (int i = 0; i < num; i++) {while (tmp[i]--) {a[j++] = i + min;}}
}
我们创建数组的话肯定不能说下标从0到原数组中的最大值，而范围应该是原数组中从最小值到最大值的那么多范围。这样既缩小了数组的大小，也方便找到原数组中的每个值。
快速排序
快速排序的基本思想就是选取一个key值，把小于key值的放在左边，把大于等于key值的放在右边，这样key就值可以放到它最终该待的位置了，并且同样按照这个思路，去递归处理key左边的值和key右边的值。这就是Hoare大佬最开始发明的排序方法
void QuickSort1(int* a, int begin, int end) {if (begin >= end) {return;}int tmp = a[begin];int left = begin;int right = end;while (left < right) {while (a[right] >= tmp&&left<right) {right--;}while (a[left] <= tmp&&left<right) {left++;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[begin]);QuickSort1(a, begin, left - 1);QuickSort1(a, left + 1, end);
}
之后人们觉得这个思路坑很多，很容易写错，于是根据这个思路就发明了挖坑法，就是最初的key值的位置变成了一个坑，从数组的右边找小值放到坑中，坑就更新，再从左边找大值放到右边的新坑中，坑再更新，直到两个指针相遇，然后还是对左边和右边用递归。
void QuickSort2(int* a, int begin, int end) {if (begin >= end) {return;}int tmp = a[begin];int pit = begin;int left = begin;int right = end;while (left < right) {while (left < right && a[right] >= tmp) {right--;}a[pit] = a[right];pit = right;while (left < right && a[left] <= tmp) {left++;}a[pit] = a[left];pit = left;}a[pit] = tmp;QuickSort2(a, begin, pit - 1);QuickSort2(a, pit+1, end);
}
后人又提出了前后指针法，两个指针都是从最左边开始，找小于key值的，放到左边，直到找不到。慢指针的这个位置就是存放key值的，最后也是递归实现前面的和后面的部分。
void QuickSort3(int* a, int begin, int end) {if (begin >= end) {return;}int tmp = a[begin];int left = begin;int right = begin;while (right <= end) {if (tmp > a[right]&&++left!=right) {Swap(&a[left], &a[right]);}right++;}Swap(&a[begin], &a[left]);QuickSort3(a, begin, left - 1);QuickSort3(a, left + 1, end);
}
快速排序可以递归实现，当然也可以非递归实现，这里就要借用栈了，用栈去保存我们要处理的begin和end值，取出来处理完后再保存它的子范围的两个范围值。直到栈为空为止
void QuickSortNonR(int* a, int begin, int end) {ST st;STInit(&st);STPush(&st, end);STPush(&st, begin);while (!STEmpty(&st)) {int left = STTop(&st);STPop(&st);int right = STTop(&st);STPop(&st);int tmp = a[left];int left1 = left;int right1 = right;while (left < right) {while (left < right && a[right] >= tmp) {right--;}while (left < right && a[left] <= tmp) {left++;}Swap(&a[left], &a[right]);}Swap(&a[left1], &a[left]);if (left1 < left - 1) {STPush(&st, left-1);STPush(&st, left1);}if (left+1 < right1) {STPush(&st, right1);STPush(&st, left + 1);}}
}
这里的一些有关栈的函数可以去看我以前的博客
链接：栈和队列
归并排序
归并排序也可以用递归实现，先将整个数组的小部分有序，然后有序的范围再扩大，然后使整个数组有序。
void _MergeSort(int* a, int* tmp, int begin, int end) {if (begin >= end)return;int mid = (begin + end) / 2;int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;_MergeSort(a, tmp, begin1, end1);_MergeSort(a, tmp, begin2, end2);int cur = begin;while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] < a[begin2]) {tmp[cur++] = a[begin1++];}else {tmp[cur++] = a[begin2++];}}while (begin1 <= end1) {tmp[cur++] = a[begin1++];}while (begin2 <= end2) {tmp[cur++] = a[begin2++];}memcpy(a+begin, tmp+begin, sizeof(int)*(end - begin + 1));}
void MergeSort(int* a, int n) {int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL) {perror("malloc failed");exit(-1);}_MergeSort(a, tmp, 0, n - 1);free(tmp);
}
能用递归实现当然也能用非递归实现，下标范围是有规律的，所以可以利用这个特性去实现非递归
void MergeSortNonR(int* a, int n) {int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL) {perror("malloc failed");exit(-1);}int gap = 1;while (gap < n) {gap *= 2;for (int i = 0; i < n; i += gap) {int begin1 = i;int begin2 = i + gap / 2;int end1 = begin2 - 1;int end2 = begin2 + end1 - begin1;if (begin2 >= n) {break;}if (end2 >= n) {end2 = n - 1;}int cur = begin1;while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] < a[begin2]) {tmp[cur++] = a[begin1++];}else {tmp[cur++] = a[begin2++];}}while (begin1 <= end1) {tmp[cur++] = a[begin1++];}while (begin2 <= end2) {tmp[cur++] = a[begin2++];}memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}}
}