一. 排序相关的概念
排序概念
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
排序的稳定性
在未排序前，a下标对应的值和b下标对应的值相等（a < b），排序后如果这两个位置的相等值仍然保持和排序前一样的前后顺序则说明该排序稳定。
内部排序
数据元素全部放在内存中的完成的排序。
外部排序
数据元素太多不能同时放在内存中完成排序，只能放到文件或磁盘中（存在文件或磁盘中就不能随机访问），借助内存完成的最终把数据存在外存的排序。
二. 常见排序算法的实现
1. 直接插入排序
基本思想
情景：拿到一个数key，要把他插入到一个已经有序的数组。我们从这个有序数组的最后一个位置的数开始比较如果比key大就把这个数往后挪一个位置，如果小于等于key就把key插入到这个数的后面。
实际中我们玩扑克牌时，就用了插入排序的思想
直接插入排序的实现
先完成第一步，把end+1位置的值插入到已经有序的 [0, end] 区间内
void InsertSort(int* a, int n) { // 把end+1位置数据插入到[0, end]的有序区间内 int end; int tmp = a[end - 1]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; --end; } else { break; } } // 不论是end小于0终止还是break终止的循环，最后都是把tmp放到end+1的位置 a[end + 1] = tmp; }
最后，外部加个for循环控制end的值，实现所有数据的排序
// 直接插入排序 void InsertSort(int* a, int n) { // i代表已经排好序数组的最后一个元素的下标 for (int i = 0; i < n - 1; ++i) { // 把第end+1个位置的数插入到前[0,end]的数中 int end=i; int tmp = a[end + 1]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; --end; } else { break; } } a[end + 1] = tmp; } }
直接插入排序的特性
元素已经有序或接近有序时，直接插入排序的时间效率越高。
时间复杂度：O(N^2)。 最好情况（有序）：O（N），最坏情况（逆序）：O(N^2))
空间复杂度：O(1)
稳定性：稳定
2. 希尔排序
基本思想
对于直接插入排序，有序或者接近有序时最快，时间复杂度差不多是O(N)。希尔排序就是在直接插入排序之前对原数组进行预排序，使得原数组接近有序。
希尔排序的实现
预排序
设间隔 gap ,就是每间隔gap个数的数组成一组，一共有gap组。当gap=1时就是直接插入排序。
我们先对间隔为gap的其中的一组进行直接插入排序
void ShellSort(int* a, int n) { // 对间隔为gap的其中一组数据进行直接插入排序 int gap; int end; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end-=gap; } else { break; } } a[end + gap] = tmp; }
通过外套一个for循环，完成所有组的排序，其中i代表end的值，从0开始，循环条件为i小于n-gap就可以完成所有组的排序。注意这里不是严格按照一组一组的排，而是混在一起，但最终完成的效果还是一样的。
void ShellSort(int* a, int n) { // 1、对gap为间隔的每一组进行排序 int gap; for (int i = 0; i < n - gap; ++i) { int end=i; int tmp = a[end + gap]; // 2、单次预排序 while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } }
最终实现
我们上面完成的就是预排序，可以发现预排序好的数组比最开始时更接近有序，且gap越大，前面越大的数越移动到了后面；后面越小的数越移动到了前面。当gap等于1时就是就可以排好序了。我们外套一个while循环来控制gap
// 希尔排序 void ShellSort(int* a, int n) { int gap=n; // 1、预排序，直到gap为1，就是直接插入排序 while (gap > 1) { gap = gap / 3 + 1;// 最后的+1保证gap最后可以为1 // 2、对gap为间隔的每一组进行排序 for (int i = 0; i < n - gap; ++i) { int end = i; int tmp = a[end + gap]; // 3、单次预排序 while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }
希尔排序的特性
希尔排序是对直接插入排序的优化。当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。整体而言，可以达到优化的效果。
时间复杂度：O(N^1.3 — N^2）
空间复杂度：O(1)
稳定性：不稳定，因为依据gap分成不同组，相同数据的相对位置可能被打乱
3. 简单选择排序
基本思想
遍历一遍数组，得到最大值和最小值的下标，最小值交换到最左边位置，最大值交换到最右边位置，然后不计最左边和最右边，缩小数组区间，继续遍历找最大值和最小值下标，最后只剩一个或者没有元素时就排好序了。
简单选择排序的实现
根据简单选择排序的基本思想，我们可以得到下面这个实现
void SelectSort(int* a, int n) { // 从区间[begin,end]选出最大的和最小的放到两端 int begin = 0; int end = n - 1; while (begin < end) { // 找到最大值和最小值的下标 int maxIndex = begin; int minIndex = begin; for (int i = begin+1; i <= end; ++i) { if (a[i] > a[maxIndex]) { maxIndex = i; } if (a[i] < a[minIndex]) { minIndex = i; } } // 把最大值和最小值放到数组两端 swap(a[begin], a[minIndex]); swap(a[end], a[maxIndex]); // 缩小区间，继续迭代 ++begin; --end; } }
因为我们是同时找到最大值和最小值的下标，在其中一个进行交换时，可能会发生另外一个数据的丢失。
所以我们在交换minIndex和begin位置的值后，要判断begin是否等于maxIndex，等于的话就要更新maxIndex位置
// 直接选择排序 void SelectSort(int* a, int n) { // 从区间[begin,end]选出最大的和最小的放到两端 int begin = 0; int end = n - 1; while (begin < end) { int maxIndex = begin; int minIndex = begin; for (int i = begin+1; i <= end; ++i) { if (a[i] > a[maxIndex]) { maxIndex = i; } if (a[i] < a[minIndex]) { minIndex = i; } } swap(a[begin], a[minIndex]); // 如果begin==maxIndex就要更新manIndex的下标 if (begin == maxIndex) { maxIndex = minIndex; } swap(a[end], a[maxIndex]); ++begin; --end; } }
简单选择排序的特性
思想很好理解，但效率不是很好，实际中很少用
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定，因为涉及到数据两两交换，会导致相对位置发生改变
4. 堆排序
基本思想
首先我们要知道，排升序建大堆，排降序建小堆。如果排升序，先把原始数据建大堆，此时堆顶数据就是最大值，把他和最后一个位置数据交换，然后数组个数减1，这个时候堆顶只需进行一次向下调整有可以建堆，在选出次小的数，交换堆顶和最后一个位置的数…，迭代这个过程最终排好序。
堆排序实现
实现堆排序还需要一个接口函数，就是堆的向下调整算法：要求根的左右子树都是大堆（或小堆），从根开始调整可以把所有数据调成一个大堆（或小堆）。
void AdjustDown(int* a, int n,int root) { int parent = root;// 父亲节点 int child = parent * 2 + 1;// 左孩子 // 迭代条件是父亲节点为非叶子节点（一定有左孩子） while (child<n) { // 1、我们建大堆，这里判断右孩子是否比左孩子大 if (child + 1 < n&&a[child + 1] > a[child]) { ++child; } // 2、最大的孩子是否比父亲大 if (a[parent] < a[child]) { swap(a[parent], a[child]); } else { break; } parent = child; child = parent * 2 + 1; } }
有了向下调整算法，我们就可以建堆和实现堆排序了，向下调整算法的时间复杂的是O(logN)，就是树的的高度，而建堆的时间复杂度是O(N)，下面是完成的堆排序。
// 堆排序 void HeapSort(int* a, int n) { // 1、建堆 for (int i = n - 1 - 1 / 2; i >= 0; --i) { AdjustDown(a, n, i); } // 2、把堆顶数据和最后一个位置数据交换，从堆顶继续向下调整找到次大的数据 int end = n - 1; for (int i = end; i > 0; --i) { swap(a[0], a[i]); AdjustDown(a, i, 0); } }
堆排序的特性
堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定，因为堆是树状，向下调整过程中会打乱了相对顺序。
5. 冒泡排序
基本思想
从左往右两两比较，按照要求交换位置，每一趟完了都可以排好一个数。
冒泡排序实现
从左往右遍历数组，两两比较元素的大小，如果前者大于后者就交换，这样比较完一遍就可以排好一个最大的数。
// i代表元素个数 //调整[0,i-1]位置上的元素，把其最大值最后移到i-1位置 for (int j = 0; j < i - 1; ++j) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); } }
i代表元素个数，我们在嵌套一个for循环来控制i的值，，每一趟可以排好一个数，所以i从n开始递减，直到最后i等于1就停止（才剩一个数就不用排，它就是最小的，放在最左边）。
// i代表元素个数 for (int i = n; i > 1; --i) { for (int j = 0; j < i - 1; ++j) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); } } }
最后我们可以优化一下，因为i代表元素个数从n开始递减，所以如果某一次两两比较没有交换元素的话，就说明已经有序了，不用再进行冒泡排序了，我们用flag作为标记来判断是否每一趟两两比较完了之后是否有交换元素。
// 冒泡排序 void BubbleSort(int* a, int n) { // 1、i代表元素个数 for (int i = n; i > 1; --i) { // 2、调整[0,i-1]位置上的元素，把其最大值最后移到i-1位置 int flag = 1; for (int j = 0; j < i-1; ++j) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); flag = 0; } } // 遍历完一遍当前数组，如果已经有序了就不用再往下遍历下一组了 if (flag) { break; } } }
冒泡排序特性
冒泡排序是一种非常容易理解的排序
时间复杂度：O(N^2)。最好O(1)，最坏O( N^2)
空间复杂度：O(1)
稳定性：稳定
6. 快速排序
基本思想
快排的关键是遍历一遍把其中一个数key放到正确的排序位置，这样左边都是小于等于它的数，右边都是大于等于它的数（左边和右边不一定有序）。而实现这个操作的方法有以下三种：
方法一：左右指针法
要注意的是，如果选最右边的数为key，那么left先走；如果选最左边的数为key，right先走。这样保证了他们相遇时所指向的数一定大于等于key（选最右边为key）或小于等于key（选最左边为key），想要证明也很简单，如果是选最右边为key，相遇如果是left走遇到right的话，right要么一直没动就在最右边那么他们相遇就等于key，要么是至少交换一次后遇到right，因为上一次的交换，这时right一定指向大于key的数；如果是right遇到left，因为是left先走，相遇时left=right，所指的数一定大于key。另外一个要注意的是内部的while循环条件一定要是 <= 和 >= 不然会死循环。代码实现如下：
// 左右指针法（快排的一个接口函数） int PartSort1(int* a, int left, int right) { int key = a[right];// 记录key的值 int rightIndex = right;// 记录当前key所在位置的下标 // 找到key正确的排序位置，并且使得左边的数小于等于key，右边的数大于大于key while (left < right) { while (left < right&&a[left] <= key) { ++left; } while (left < right&&a[right] >= key) { --right; } swap(a[left], a[right]); } // 把key交换到正确地位置 swap(a[left], a[rightIndex]); // 返回key的下标 return left; }
方法二：挖坑法
挖坑法其实就是左右指针法的一种变形。
// 挖坑法（快排的一个接口函数） int PartSort2(int* a, int left, int right) { int key = a[right];// 记录key的值 int rightIndex = right;// 记录当前key所在位置的下标 // 找到key正确的排序位置，并且使得左边的数小于等于key，右边的数大于大于key while (left < right) { while (left < right && a[left] <= key) { ++left; } swap(a[left], a[right]); while (left < right && a[right]>=key) { --right; } swap(a[left], a[right]); } // 把key交换到正确地位置 swap(a[left], a[rightIndex]); // 返回key的下标 return left; }
方法三：前后指针法
还是令最右边的元素为key，定义两个指针，prev=left-1和cur=left，然后从左往右遍历数组，如果cur指向的数小于key就交换cur和++prev的元素完了后++cur；如果大于等于key就++cur，prev不动，这样就完成了下与key的数都甩到prev之后，prev和cur之间夹的数就是大于等于key的数。
// 前后指针法（快排的一个接口函数） int PartSort3(int* a, int left, int right) { int key = a[right];// 记录key的值 int rightIndex = right;// 记录当前key所在位置的下标 int prev = left - 1; int cur = left; // 找到key正确的排序位置，并且使得左边的数小于key，右边的数大于大于key while (cur < right) { if (a[cur] < key && a[++prev] != a[cur]) { swap(a[prev], a[cur]); } ++cur; } // 把key交换到正确地位置 swap(a[++prev], a[rightIndex]); // 返回key的下标 return prev;
递归实现快速排序
n个数用一次partsort就可以确定一个数正确地排序位置，我们对这个数的左右区间递归使用partsort再去确认其他数的正确地排序位置，直到这个区间的数才有1个或0个，所有的数就排好序了。
// 快速排序 // 注意这里的left和right是闭区间 void QuickSort(int* a, int left, int right) { if(left>=right) { return; } // 类似于二叉树的前序遍历 int div = PartSort3(a, left, right); QuickSort(a, left, div - 1); QuickSort(a, div + 1, right); }
时间复杂度分析及其优化
既然是二叉树结构，那么就会有单叉树的时候，这会导致效率大大降低
要使得key不为最大值，我们可以来个三数取中，就是区间最左边的数、中间的数、最右边的数，找到中间小的数把它和最右边的数交换（这里我们令key为最右边的位数），使得key不会为最大或最小的数。
// 三数取中（快排的一个接口函数） // 三数取中 int GetMidIndex(int* a, int left, int right) { // 数组中间元素的下标 int mid = left + (right - left) / 2; // 大的分两类情况处理 if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[right] < a[left]) { return left; } else { return right; } } else { if (a[mid] > a[right]) { return mid; } else if (a[right] > a[left]) { return left; } else { return right; } } }
我们把它放到partsort里，这样快排的时间复杂度就保证在O(N*logN)
最后在提一处优化，就是小区间优化，如果数据量小时，没必要在用快排了，它会有压栈的开销，这个时候直接用插入排序来进行小区间的排序比起压栈更快，一般我们认为的小区间是元素个数小于等于10，看源代码可以发现C++中的sort也是用的快排并且有有小区间优化。
// 快速排序 void QuickSort(int* a, int left, int right) { // 小区间优化，用插入排序 if (right - left + 1 > 10) { // 相当于二叉树的前序遍历 int div = PartSort3(a, left, right); QuickSort(a, left, div - 1); QuickSort(a, div + 1, right); } else { InsertSort(a + left, right - left + 1); } }
快速排序非递归实现
利用栈的后进先出特性结合while循环模拟压栈的过程
// 快排非递归写法 void QuickSortNonR(int* a, int left, int right) { stack<int> s; // 先把整个区间的下标入栈 s.push(right); s.push(left); while (!s.empty()) { // 拿出一个区间，对其进行一次PartSort，排好中间位置的数 int begin = s.top(); s.pop(); int end = s.top(); s.pop(); int div = PartSort3(a, begin, end); // 对于中间位置这个数，如果还有左右区间的话继续入他的左右区间 if (div+1<end) { s.push(end); s.push(div+1); } if (begin < div - 1) { s.push(div - 1); s.push(begin); } } }
快速排序特性
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)，如果没有三数取中，最坏是N^2
空间复杂度：空间复杂度：O(logN)，可以理解为每一层共用一个栈空间，所有空间复杂度就是树的高度O(logN)
稳定性：不稳定
7. 归并排序
基本思想
归并排序的核心是两个有序数组（我们这里说的两个有序数组是连在一起的，但总体不是有序）的合并：先创建一个能容纳的下两个数组大小的数组tmp，两个指针begin1和begin2分别指向两个数组的第一个元素，比较他们所指向的元素，小的那个放到tmp中，直到其中一个数组先走完，另外一个数组没走完的部分全挪到tmp后面。最后排好序了把tmp上的数据覆盖到原数组空间。
// 完成两个已经有序并且连续的数组的归并 void MergeArray(int* a, int begin1, int end1, int begin2, int end2, int* tmp) { int i = begin1;// 标记tmp的下标 // left和right代表整个数组的区间的下标 int left = begin1; int right = end2; // 两个都没走完就继续 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } // 最终没走完的挪到tmp后面 while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } // 把tmp上已经排好序的数组覆盖到原数组空间 for (int i = left; i <= right; ++i) { a[i] = tmp[i]; } }
归并排序实现
要让整个数组有序，先让它的左半部分和右半部分有序，在利用上面实现两个已经有序并且连续的数组的归并来使数组整体有序；左半部分和右边部分也是这样的处理，直到整个区间只有1个或0个元素为止。类似于二叉树的后序遍历。
// 递归操作 void _MergeSort(int* a, int left, int right, int* tmp) { // 只有一个数或者没有数，那就什么都不干 if (left >= right) { return; } // 相当于二叉树的后序遍历 int div = left + (right - left) / 2; //[left,div] [div+1,right] _MergeSort(a, left, div,tmp); _MergeSort(a, div + 1, right, tmp); MergeArray(a, left, div, div + 1, right, tmp); } // 归并排序 void MergeSort(int* a, int n) { // 这里实现tmp的创建和销毁，递归操作单独封装一个接口 int* tmp = new int[n]; _MergeSort(a, 0, n - 1, tmp); delete[] tmp; }
归并排序非递归实现
既然是类似于二叉树的后序遍历，那么一定有非递归写法
void MergeSortNonR(int* a, int n) { int* tmp = new int[n]; int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2*gap) { // 两组为单位进行归并操作 // [i,i+gap-1] [i+gap,i+2*gap-1] int begin1 = i; int end1 = i + gap - 1; int begin2 = i + gap; int end2 = i + 2 * gap - 1; // 第二组不存在的话就break，后面（i变大）肯定也不存在了，下一个gap继续 if (begin2 >= n) { break; } // 第二组区间只有部分的话，更新第二组的下标 if (end2 >= n) { end2 = n-1; } // 对这两组进行归并 MergeArray(a, begin1, end1, begin2, end2, tmp); } gap *= 2; } delete[] tmp; }
归并排序特性
归并的缺点在于需要O(N)的空间复杂度，归并排序更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定
8. 计数排序
基本思想
统计每个元素出现的次数
根据统计的结果将序列回收到原来的序列中
计数排序的实现
void CountSort(int* a, int n) { // 1、遍历原数组，得到最大值和最小值 int maxNum = a[0]; int minNum = a[0]; for (int i = 1; i < n; ++i) { if (a[i] < minNum) { minNum = a[i]; } if (a[i] > maxNum) { maxNum = a[i]; } } // 2、遍历原数组，把各个数出现的次数统计到countArray中 int range = maxNum - minNum + 1; int* countArray = new int[range](); for (int i = 0; i < n; ++i) { ++countArray[a[i] - minNum]; } // 3、遍历countArray数组，把对应下标的数据覆盖到原数组中 int index = 0; for (int i = 0; i < range; ++i) { while (countArray[i]--) { a[index++] = i + minNum; } } }
计数排序特性
计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
时间复杂度：O(N+rang)
空间复杂度：O(rang)
稳定性：稳定
