本章重点
- 排序的概念及其运用
- 常见排序算法的实现
- 排序算法复杂度及稳定性分析
1.排序的概念及其运用
1.1排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2排序运用
1.3 常见的排序算法
2.常见排序算法的实现
2.1 插入排序
2.1.1基本思想：
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
实际中我们玩扑克牌时，就用了插入排序的思想
2.1.2直接插入排序：
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
插入过程：如果end+1位置的值小于end位置，就将end位置的值挪到end+1位置处，否则，直接插入到end+1位置。注意，这里需要保存end+1位置的值，因为end位置的值挪到end+1位置时，会覆盖end+1位置的值。
结束条件：当end+1位置的值小于当前有序序列所有的值时，此时end的值为-1，也就是排序的终止条件
单趟插入排序代码：单趟[0,end]有序，把end+1位置的值插入到前面序列，控制[0，end+1]序列有序。
// 插入排序 void InsertSort(int* a, int n) { int end = ; //保存要排序的值，防止数据被覆盖找不到数据 int temp = a[end + 1]; while (end >= 0) { if (temp < a[end]) { a[end + 1] = a[end]; } else { break; } } //将temp的值赋给end+1位置，这样就插入有序了 a[end + 1] = temp; }
整趟插入排序：我们默认第一个数有序，第二个数插入到有序序列中，调整有序，那么end就是0，如下图，当最后一个元素插入有序系列中，此时end的值时n-2。
#include <stdio.h> // 插入排序 void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int end = i; //保存要排序的值，防止数据被覆盖找不到数据 int temp = a[end + 1]; while (end >= 0) { if (temp < a[end]) { a[end + 1] = a[end]; } else { break; } end--; } //将temp的值赋给end+1位置，这样就插入有序了 a[end + 1] = temp; } } int main() { int a[] = { 1,4,2,7,6,9 }; InsertSort(a, 6); for (int i = 0; i < 6; i++) { printf("%d ", a[i]); } return 0; }
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
2.1.3 希尔排序( 缩小增量排序 )
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
思想：
- 预排序：间接为gap为一组进行排序
- 直接插入排序
单趟排序：将gap为一组的数据进行排序，希尔排序和上面的直接插入排序方法相同，只是希尔排序是将gap间距的数据进行直接插入排序，若gap==1时，希尔排序和直接插入排序相同。
// 希尔排序 void ShellSort(int* a, int n) { int gap = 5; for (int i = 0; i < n - gap; i+=gap) { int end = i; int temp = a[end + gap]; while (end >= 0) { if (a[end] > temp) { a[end + gap] = a[end]; } else { break; } end -= gap; } a[end + gap] = temp; } }
多趟排序：通过gap将一组数据分割，依次将分割的数据直接插入排序，每组的数据都将有序。
// 希尔排序 void ShellSort(int* a, int n) { int gap = 5; for (int j = 0; j < gap; j++) { for (int i = j; i < n - gap; i += gap) { int end = i; int temp = a[end + gap]; while (end >= 0) { if (a[end] > temp) { a[end + gap] = a[end]; } else { break; } end -= gap; } a[end + gap] = temp; } } }
上面的代码将gap组数据进行直接插入排序，是一组数据排完后再排下一组数据，下面我们来看一个更厉害的代码，它在上面的基础上省略了一个for循环。
// 希尔排序 void ShellSort(int* a, int n) { int gap = 5; for (int i = 0; i < n - gap; i++) { int end = i; int temp = a[end + gap]; while (end >= 0) { if (a[end] > temp) { a[end + gap] = a[end]; } else { break; } end -= gap; } a[end + gap] = temp; } }
上面的代码不是一组数据排完后再排下一组数据，它不用跳到下一组数据排序，而是不跨组排序，多组并排，比刚刚的代码更简洁。经过上面的排序，我们只是使得每组数据有序，并没有使得全部的数据有序。上面的排序使得大的数据更快的移动到后面，小的数据更快的移动到前面，gap越大跳的越快，越不接近有序，gap越小跳的越慢，越接近有序。gap为1，该数据就有序了。所有要想数据有序，就要让gap为1。gap>1时就是预排序，gap==1时就是有序。
// 希尔排序 void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap /= 2;//gap等于1，数据有序 for (int i = 0; i < n - gap; i++) { int end = i; int temp = a[end + gap]; while (end >= 0) { if (a[end] > temp) { a[end + gap] = a[end]; } else { break; } end -= gap; } a[end + gap] = temp; } } } int main() { int a[] = { 1,4,2,7,6,9 }; ShellSort(a, 6); for (int i = 0; i < 6; i++) { printf("%d ", a[i]); } return 0; }
我们上面定义的gap是每次除2，这样排序的次数还是有点多，所以我们定义的gap是每次除3，但是除3不一定能保证最后一次是1，比如gap为8，除3是2，再除3就是0，所以我们只需要除3后加1就可以满足最后一次gap为0。
// 希尔排序 void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1;//gap等于1，数据有序 for (int i = 0; i < n - gap; i++) { int end = i; int temp = a[end + gap]; while (end >= 0) { if (a[end] > temp) { a[end + gap] = a[end]; } else { break; } end -= gap; } a[end + gap] = temp; } } }
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：因为咋们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：
2.2 选择排序
2.2.1基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完 。
2.2.2 直接选择排序
- 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
- 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
- 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
// 选择排序 void SelectSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { //假设下标为0的数据最小 int mini = i; for (int j = mini + 1; j < n; j++) { if (a[mini] > a[j]) { mini = j; } } //此时a[mini]是数组中最小的值 Swap(&a[i], &a[mini]); } }
但是上面的每次都是找最小值，然后再放到正确的位置，效率太低，我们是不是可以每次找出一个最大值，再找出一个最小值，然后各自放到正确的位置上，这样效率就提高了很多。
// 选择排序 void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; while(begin < end) { int mini = begin; int maxi = begin; for (int i = begin + 1; i <= end; i++) { if (a[mini] > a[i]) { mini = i; } if (a[maxi] < a[i]) { maxi = i; } } //此时a[mini]是数组中最小的值 //此时a[maxi]是数组中最大的值 Swap(&a[begin], &a[mini]); Swap(&a[end], &a[maxi]); begin++; end--; } }
为什么结果不对呢？我们上面的代码出现了什么问题？
很明显，按照上图的情况，maxi和begin下标相同，当begin和minx下标的数据交换之后，maxi的下标的值就发生变化了，此时end和maxi交换就不正确了，所以上面的程序是有问题的。我们只需要更新一下maxi的位置就行啦。
void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } // 选择排序 void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; while(begin < end) { int mini = begin; int maxi = begin; for (int i = begin + 1; i <= end; i++) { if (a[mini] > a[i]) { mini = i; } if (a[maxi] < a[i]) { maxi = i; } } //此时a[mini]是数组中最小的值 //此时a[maxi]是数组中最大的值 Swap(&a[begin], &a[mini]); //maxi如果被换走就要修正一下 if (maxi == begin) maxi = mini; Swap(&a[end], &a[maxi]); begin++; end--; } } int main() { int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 }; SelectSort(a, 17); for (int i = 0; i < 17; i++) { printf("%d ", a[i]); } }
2.2.3 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
所以我们可以建大堆，将堆顶的数据和最后一个叶子结点交换，由于此时的堆结构没有破坏，左子树和右子树仍然是堆，使用堆的向下调整去调整堆，然后在缩小下次向下调整的范围，也就是把最大的那个数不算做堆的范围了，这样最大的数据就保存在了下标最大的位置处，满足了升序的要求。
void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } // 堆排序 void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child] < a[child+1]) { child++; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapSort(int* a, int n) { //向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } }
堆排序的特性总结：
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
【探索排序算法的魅力：优化、性能与实用技巧】（中）：https://developer.aliyun.com/article/1425258
