排序介绍
排序就是使一串记录按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的。比如A = B，在原序列中A在B前面，排序后A仍旧在B前面，则是稳定的。
数据元素全部放在内存中的排序称为内部排序。
数据元素过多而不能同时存放在内存中，需要根据排序过程的要求不断在内外存之间移动数据的排序称为外部排序。
插入排序
基本思想：把待排序的记录按其关键码值的代销逐个插入到一个已经排好的有序序列中，知道所有的记录插入完为止，得到一个新的有序序列。
直接插入排序
- 基本介绍：
在待排序的数组中，我们假设前n-1个元素已经是有序的了，然后将第n各元素逐一进行比较，然后将第n个元素放入合适的位置。
一个元素集合越接近有序，直接插入算法的时间效率就越高。 - 代码：
void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { 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; } }
3.时间复杂度与空间复杂度
插入排序的平均时间复杂度也是 O(n2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。
插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N-1次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n2)。
4.动图演示：
希尔排序
1.基本介绍：
希尔排序是一种插入排序，又称为缩小增量排序。希尔排序在直接插入排序的基础上引入了分组，先分组进行预排序，然后在通过直接插入排序完成最后的排序。
先选定一个数gap（小于这个待排序数据的总数）作为第一增量，元素之间相差gap的元素作为一组，然后分组进行直接插入排序，排序完成后缩小增量，在重复上述操作，直到gap=1，实现最终的排序。
2.代码：
void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1; for (int i = 0; i < n - gap; i++) { 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; } } }
3.时间复杂度与空间复杂度：
希尔排序时间复杂度是 O(n1.3-2)，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n2) 复杂度的算法快得多。
算法在执行过程中，只需要几个定义的临时变量，所以空间复杂度为常数级O(1)。
4.图示：
选择排序
基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，放在序列的起始位置，直到全部待排序的数据元素排完。
选择排序
1.基本介绍：
直接选择排序也是一种简单的排序方法，它的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，…，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，…，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
一个简单的优化就是，反正都要遍历一次，那就可以找出最大最小的值，分别放到结尾和开头，这样能够提高一些效率。
2.代码：
void SelectSort(int* a, int n) { 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; } int tmp = a[begin]; a[begin] = a[minI]; a[minI] = tmp; if (maxI == begin) maxI = minI; tmp = a[end]; a[end] = a[maxI]; a[maxI] = tmp; begin++; end--; } }
3.时间复杂度与空间复杂度：
直接选择排序的时间复杂度为 O(n2) ，所以当记录占用字节数较多时，通常比直接插入排序的执行速度快些；
对于空间复杂度来说，简单选择排序仅需一个存储空间用于记录交换的暂存单元，即空间复杂度为 O(1)；
由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。
4.图示：
堆排序
- 基本介绍：
堆排序是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它通过堆来进行数据选择。排升序要建大堆，降序要建小堆。 - 代码：
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { // 确认child指向大的那个孩子 if (child + 1 < n && a[child + 1] > a[child]) { ++child; } // 1、孩子大于父亲，交换，继续向下调整 // 2、孩子小于父亲，则调整结束 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapSort(int* a, int n) { // 向下调整建堆 -- O(N) // 升序：建大堆 for (int i = (n - 1 - 1) / 2; i >= 0; --i) { AdjustDown(a, n, i); } // O（N*logN） int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } }
3.时间复杂度与空间复杂度：
使用堆排序最坏的情况就是一直需要交换结点，则需要循环h - 1次（h为树的高度）。而h = log(N+1)（N为树的总结点数），则排序的时间复杂度为O(logN)。但是在进行堆排序之前需要先建堆，建堆的时间复杂度为O(N)。
对于空间复杂度来说，堆排序仅需几个存储空间用于记录一些下标位置，所以空间复杂度为 O(1)；
4.图示：
交换排序
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排
序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
冒泡排序
1.基本介绍：
冒泡排序是一个很形象的形容，因为它排序就像冒泡一样，元素是一个一个冒出来的。从第一个元素开始，两两比较，根据升序还是降序，将大的或小的元素向后移。
如果一次遍历完了，都没有发生交换，就说明遍历的序列是有序的，可以直接跳出。这样可以提高一点效率，但是效率还是比不上其他排序算法。
2.代码：
void BubbleSort(int* a, int n) { for (int i = 0; i < n; i++) { int exchange = 0; for (int j = 1; j < n - i; j++) { if (a[j - 1] > a[j]) { int tmp = a[j - 1]; a[j - 1] = a[j]; a[j] = tmp; exchange = 1; } } if (exchange == 0) break; } }
- 时间复杂度与空间复杂度：
- 图示：
快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想是：任取待排元素序列中的某元素作为其基准值（往往是取第一个元素或者最后一个元素），按照该排序码将待排序集合分为左右两个子序列，左子序列中的所有元素均小于基准值，右子序列中的所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
递归实现
Hoare版本
1.基本介绍：
选出一个key值，定义一个L和一个R，L向右走R向左走。（需要注意的是，如果key值是第一个元素，R先走。如果key值是最后一个元素，L先走）
R先移动，遇到比key值小的就停止，然后L开始移动，遇到比key值大的停止，然后将此时L与R的值交换，然后重复以上步骤。直到L和R相遇，此时的值一定是小于key值的，然后把它与key交换。而此时的key值就放在了它应该在的位置，同时将序列分成了左右两个子序列。
为什么R和L相遇时的值一定是小于key值的？R在遇到小于key值的值时会停止，等L移动，L移动有两个结果，一种是遇到比key值大的，两者交换，然后R继续移动；另一种是没有遇到必key值大的，直到相遇，这个是比key值小的值。L在停止前必然是R遇到一个比key小的值停止，两者会交换。所以造成R和L相遇的值一定小于key值的原因是R先走，这是非常巧妙的一步。如果是L先走，那必然相遇位置的值是大于key值的，此时的key值应该取的是最后一个元素。
2.代码：
void QuickSortHoare(int* a, int begin, int end) { if (begin >= end) return; int left = begin, right = end; int keyI = left; while (left < right) { // 右边先走，找小于key值的值 while (left < right && a[right] >= a[keyI]) right--; // 左边后走，找大于key值的值 while (right < right && a[left] <= a[keyI]) left++; int tmp = a[left]; a[left] = a[right]; a[right] = tmp; } int tmp = a[left]; a[left] = a[keyI]; a[keyI] = a[left]; keyI = left; // 左子序列[begin,keyI)，右子序列(keyI,end] QuickSortHoare(a, begin, keyI - 1); QuickSortHoare(a, keyI + 1, end); }
3.时间复杂度与空间复杂度：
对于快速排序来说，比较的次数是固定的，不会超过O(n)，那么划分的次数就非常重要了。如果初始序列是有序的，那么此时的排序过程就非常的像冒泡排序，时间复杂度为O(n)，则最差的情况时间复杂度为O(n2)。
如果每次key值都在中间，那么就有点像是二分法，则时间复杂度为O(logn)，此时的时间复杂度就是O(n*logn)了。
因为使用了递归，所以在执行过程中需要在栈中保存相关的信息，需要的空间和递归次数有关，递归与划分的次数有关系，也就是最好是O(logn)，最差是O(n)。
4.图示：
