一、排序的概念及其运用
1、排序的概念
- 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
- 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
- 内部排序：数据元素全部放在内存中的排序。
- 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
2、常见的排序算法
二、常见排序算法的实现
1、插入排序（Insertion Sort）
（1）基本思想
直接插入排序是一种简单的插入排序法，其基本思想是： 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中。重复这个过程，直到所有的记录插入完为止，得到一个新的有序序列 。
（2）直接插入排序（InsertSort）
当插入第 i (i >= 1) 个元素时，前面的 array[0]，array[1]，…，array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1]，array[i-2]，… 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。
// 直接插入排序 void InsertSort(int* a, int n) { assert(a); for (int i = 0; i < n - 1; ++i) { // [0,end]有序，把end+1位置的值插入，保持有序 int end = i; int tmp = a[end + 1]; while (end >= 0) { if (tmp < a[end])//升序 { a[end + 1] = a[end]; --end; } else { break; } } a[end + 1] = tmp; } }
a.插入排序是原地排序算法吗？
从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以 空间复 杂度是 O(1) ，也就是说，这是一个 原地排序算法 。
b.插入排序是稳定的排序算法吗？
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素
的后面，这样就可以保持原有的前后顺序不变，所以插入排序是 稳定 的排序算法。
c.插入排序的时间复杂度是多少？
如果要排序的数据已经是 有序 的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为 O(n) 。注意，这里是 从尾到头遍历已经有序的数据 。
如果数组是 倒序 的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为 O(n²) 。
还记得在数组中插入一个数据的平均时间复杂度是多少吗？没错，是 O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以 平均时间复杂度为 O(n²) 。
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高。
- 时间复杂度：O(N²)。
- 空间复杂度：O(1)，它是一种稳定的排序算法。
- 稳定性：稳定。
（3）希尔排序（ShellSort）（缩小增量排序）
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成若干个 组，所有距离为 gap 的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工 作。当到达 gap =1 时，所有记录在统一组内排好序。
// 希尔排序 void ShellSort(int* a, int n) { assert(a); int gap = n; //时间复杂度：O（n*log3n） // 时间复杂度：O(log3n)（以3为底的对数） while (gap > 1) // 不能写成gap>0,因为gap的值始终>=1 { gap = gap / 3 + 1; //gap = gap / 2; for (int i = 0; i < n - gap; ++i) // 时间复杂度：O(n) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }
【关于 gap 的取值】
最初希尔提出的增量是 gap = n / 2，每一次排序完让增量减少一半 gap = gap / 2，直到 gap = 1 时排序相当于直接插入排序。直到后来 Knuth 提出的 gap = (gap / 3) + 1，每次排序让增量成为原来的三分之一，加一是防止 gap <= 3 时 gap = gap / 3 = 0 的发生，导致希尔增量最后不为1，无法完成插入排序。
选择 gap = (gap / 3) + 1 更稳定，能够尽可能地减少比较和交换的次数，以提高排序的效率。通过采用这种递减的方式，可以更好地分组元素，使得在每一轮排序中能够更快地将较小的元素移动到前面。序列被划分为较小的子序列，并通过插入排序的方式对每个子序列进行排序。这样做的好处是在初始阶段，较大的元素可以更快地向后移动，从而减少了后续比较和交换的次数。
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，相当于直接插入，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度并不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定，官方给出的时间复杂度是 O(N^1.3) 。
- 稳定性：不稳定。
希尔排序的时间复杂度都不固定：
《数据结构 (C 语言版 ) 》 --- 严蔚敏
《数据结构-用面相对象方法与C++描述》--- 殷人昆
【总结】
希尔排序在越大的数组上相较于直接插入排序更能发挥优势，因为步子迈的更大，减少插入排序的移动次数更多。比如10w个数据，直接插入排序复杂度为O(N^2),计算10w *10w=100亿次，而希尔排序复杂度为O(NlogN),计算10w *17 = 170w次。（2 ^17 约等于10w）。
2、选择排序
（1）基本思想
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序
每一次从待排序的数据元素中选出 最小(升序) / 最大(降序) 的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
（2）直接选择排序（SelectSort）
- 在元素集合 array[i] -- array[n-1] 中选择关键码最大 / 小的数据元素。
- 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换。
- 在剩余的 array[i] -- array[n-2]（array[i+1] -- array[n-1]）集合中，重复上述步骤，直到集合剩余 1 个元素。
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void SelectSort(int* a, int n) { assert(a); int begin = 0; while (begin < n) { int mini = begin; for (int i = begin; i < n; i++) { if (a[i] < a[mini]) { mini = i; } } Swap(&a[begin], &a[mini]); begin++; } }
// 优化后的代码：(一次选出两个数) void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } // 直接选择排序 void SelectSort(int* a, int n) { assert(a); int begin = 0, end = n - 1; while (begin < end) // 奇数个会相遇 偶数个会错过 { int mini = begin, maxi = begin; for (int i = begin + 1; i <= end; ++i) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } Swap(&a[begin], &a[mini]); // 如果begin和maxi重叠，那么要修正maxi的位置 if (begin == maxi) { maxi = mini; } Swap(&a[end], &a[maxi]); ++begin; --end; } }
a.选择排序是原地排序算法吗？
选择排序空间复杂度为 O(1) ，是一种原地排序算法。
b.选择排序是稳定的排序算法吗？
答案是否定的，选择排序是一种 不稳定 的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。 比如 4，9，4，1，8 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 1 ，与第一个 4 交换位置，那第一个 4 和中间的 4 顺序就变了，所以就不稳定了.
c.选择排序的时间复杂度是多少？
选择排序的最好情况时间复杂度为 n+(n-2)+(n-4)+...（优化后的做法）相当于 n²，最坏情况和平均情况时间复杂度都为 O(n²)。
直接选择排序的特性总结：
- 效率不是很好，实际中很少使用，不建议使用。
- 时间复杂度：O(N²)。
- 空间复杂度：O(1)。
- 稳定性：不稳定。
（3）堆排序（HeapSort）
有关堆（Heap）的相关内容详解，具体请看：【数据结构】堆（Heap）_炫酷的伊莉娜的博客-CSDN博客
堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是 排升序要建大堆，排降序建小堆 。
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void AdjustDown(int* a, int size, int parent) { int child = parent * 2 + 1; while (child < size) { //选出左右孩子中大的那个 if (child + 1 < size && a[child + 1] > a[child]) { ++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) { assert(a); // botto-top(自底向上)，依次遍历完所有子树，分别对其进行调整 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)。
- 稳定性：不稳定。
3、交换排序
（1）基本思想
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将较大值向序列的尾部移动，将较小值向序列的前部移动。
（2）冒泡排序（Bubble Sort）
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
我们要对一组数据 4，5，6，3，2，1，从小到到大进行排序。第一次冒泡操作的详细过程就是这样：
可以看出，经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上。要想完成所有数据的排序，我们只要进行 6 次这样的冒泡操作就行了。
实际上，刚讲的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。下面再举一个例子，这里面给 6 个元素排序，只需要 4 次冒泡操作就可以了。
// 冒泡排序 void BubbleSort(int* a, int n) { assert(a); for (int j = 0; j < n - 1; ++j) { int exchange = 0; // 提前退出冒泡循环的标志 for (int i = 1; i < n - j; ++i) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange = 1; // 表示有数据交换 } } if (exchange == 0) // 没有数据交换，提前退出 { break; } } }
a.冒泡排序是原地排序算法吗？
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1) ，是一个原地排序算法。
b.冒泡排序是稳定的排序算法吗？
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定 性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是 稳定 的排序算法。
c.冒泡排序的时间复杂度是多少？
最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束 了，所以最好情况时间复杂度是 O(n) 。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n²) 。
d.冒泡排序与插入排序相比哪个更好？
两种排序在最好、最坏情况下的时间复杂度相同。但在相对有序的情况下，选择插入排序更好。比如：1 2 3 5 4 6 这个排序，冒泡排序需要 ((N-1)+(N-2)) 比较，插入排序需要 N 次比较。因为冒泡排序排好后，还需要再排多一次。
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序。
- 时间复杂度：O(N²)。
- 空间复杂度：O(1)。
- 稳定性：稳定。
（3）快速排序法（Quicksort）
快速排序算法（Quicksort），我们习惯性把它简称为“快排”。快排利用的是分治思想。快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。
快排的处理过程是由上到下 的，先分区，然后再处理子问题。
// 假设按照升序对array数组中[left, right)区间中的元素进行排序 void QuickSort(int array[], int left, int right) { if(right - left <= 1) { return; } // 按照基准值对array数组的[left, right)区间中的元素进行划分 int div = partion(array, left, right); // 分区函数 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right) // 递归排[left, div) QuickSort(array, left, div); // 递归排[div+1, right) QuickSort(array, div+1, right); }
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后续只需分析如何按照基准值来对区间中数据进行划分的方式即可。
快排在有序的情况下时间复杂度最坏，n+(n-1)+(n-2)+... 为 O(n²) 。
将区间按照基准值划分为左右两半部分的常见方式有： （注意这三种方法 首次单趟后不一定相同）
a.hoare 版本
选出一个关键字 key，一般是头或者尾。经过一次单趟后，key 放到了正确的位置，key 左边的值比 key 小，key 右边的值比 key 大。再让 key 的左边区间有序、key 的右边区间有序。
如何保证相遇位置的值小于 key ？
这个算法右边先走可以保证相遇位置小于 key。
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } // Hoare int PartSort1(int* a, int begin, int end) { int left = begin, right = end; int keyi = left; while (left < right) { // 右边先走，找小 -- 升序 while (left < right && a[right] >= a[keyi]) { --right; } // 左边再走，找大 while (left < right && a[left] <= a[keyi]) { ++left; } Swap(&a[left], &a[right]); } Swap(&a[keyi], &a[left]); keyi = left; return keyi; }
这里的 while 要加等号的原因是避免出现死循环的情况。
b.挖坑法
// 挖坑法 int PartSort2(int* a, int begin, int end) { int key = a[begin]; int piti = begin; while (begin < end) { // 右边找小，填到左边的坑里面去。这个位置形成新的坑 while (begin < end && a[end] >= key) { --end; } a[piti] = a[end]; piti = end; // 左边找大，填到右边的坑里面去。这个位置形成新的坑 while (begin < end && a[begin] <= key) { ++begin; } a[piti] = a[begin]; piti = begin; } a[piti] = key; return piti; }
注意：如果在 while 循环中去掉等号，即将 a[end] >= key 改为 a[end] > key，a[begin] < key 改为 a[begin] <= key，那么当数组中存在与 key 相等的元素时，会导致划分出的两部分不再严格符合小于等于 key 和大于等于 key 的条件，而是可能存在相等的元素分布在两部分中，从而导致排序结果不正确。
因此，在挖坑法中，保持 a[end] >= key 和 a[begin] <= key 的等号是非常重要的，以确保元素能够正确地被划分到两个部分中。
c.前后指针版本
// 前后指针法 int PartSort3(int* a, int begin, int end) { int prev = begin; int cur = begin + 1; int keyi = begin; // 加入三数取中的优化 //int midi = GetMidIndex(a, begin, end); //Swap(&a[keyi], &a[midi]); while (cur <= end) { // a[cur]比a[keyi]大时，prev不会++且排除了自己交换自己这种情况 if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } ++cur; } Swap(&a[prev], &a[keyi]); keyi = prev; return keyi; }
如果将 if 里面的条件改为 a[cur] <= a[keyi]，虽然不会导致排序结果出错，但是可能会改变相等元素的相对顺序，所以还是应该写成 a[cur] < a[keyi]，不要加上等号。
【数据结构】排序（插入、选择、交换、归并） -- 详解（下）https://developer.aliyun.com/article/1514541?spm=a2c6h.13148508.setting.24.4b904f0ejdbHoA
