学会控制自己是人生的必修课
一、插入排序
1.直接插入排序
1.直接插入排序思想： 假设现在已经有一个有序序列，如果有一个数字插入到这段序列的末尾，我们会选择拿这个数和它前面的每个数字都比较一遍，如果前面的数字比他大，那我们就让前面的数字赋值到这个被插入的数字位置，依次与前面的数字进行比较，最后我们把插入有序序列的数字放到他应该在的位置
void InsertSort(int* arr, int n) { for (int i = 0; i < n-1; i++) { int end = i;//end是指有序序列最后一个数字的下标 int tmp = arr[end+1];//需要暂存一下尾部位置的元素 while (end >= 0) { if (arr[end] > tmp) { arr[end + 1] = arr[end]; end--; } else { break; } } arr[end+1] = tmp; } }
2.代码细节说明：
一般来说，我们还是习惯将end定义为有序序列的最后一个数字的下标，如果我们将它定义为被插入数字的下标的话，比较的时候，我们就得往前比，end-1和end比，如果你喜欢这样定义的话，那也可以，后面的希尔排序，你也这样定义，比较的时候拿end-gap和end比较，也可以，没什么问题。
但是我个人觉得还是有些别扭的，我还是推荐大家将end定义为有序序列最后一个数字的下标，这样在逻辑思考上面还是对我们很有帮助的。
2.希尔排序
1.希尔排序思想： 将一整组数据分成gap组，我们先将这gap组进行组排序，将每组排好之后，可以让较大的数据尽快到后面，较小的数尽快到前面，然后我们逐渐减小gap直到1，进行最后的一次直接插入排序，最后的这次排序进行完毕，我们就可以得到一个有序序列了。
void ShellSort(int* arr, int n)//我的希尔排序一点问题都没有 { int gap = n; while (gap > 1)//当while循环里面gap为1时，排序一次之后，循环结束，排序结束 { gap = gap / 3 + 1;//保证我们的最后一次排序为直接插入排序，而不是预排序 for (int i = 0; i < n - gap; i++)//实现gap组并排，并且最后一次排序为直接插入排序 { int end = i;//end为最后一个有序数字的下标 int tmp = arr[end + gap]; while (end >= 0) { if (arr[end] > tmp) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = tmp; } } }
2.代码细节说明：
a. gap其实就是间距，希尔排序其实就是直接插入排序基础上的一种升华，gap/3+1是为了保证最后一次gap为1，而不是0.
如果你对于直接插入排序理解较好的话，那其实希尔排序也是很好理解的，我们只不过将数据进行了一个分组，然后进行组排序，这样会很节省时间，遍历数据的个数也会减少下来，等到最后一次排序的时候，我们也无需遍历大量的数据了，只需遍历个别不满足升序的数据即可，我们可以看到组成希尔排序的每个部分所消耗的时间其实都是短的，这也就是希尔排序效率高的一个原因，因为它可以很快的将数据归位，并且每次归位的时间消耗相比于直接插入排序，要优化很多，这也是希尔排序效率高的原因所在。
希尔排序=预排序+直接插入排序
3.希尔排序的时间复杂度：
分成gap组，每组N/gap个数据。
每组最坏的情况下的挪动次数：1 + 2 + 3 + …… + N / gap - 1 等差数列
总次数：(1 + 2 + 3 + …… + N / gap - 1) * gap次。这个次数没算外层的while循环
最开始gap很大：(N / 3 + 1)，代入到总次数可得(1 + 2 + …… 3)* (N / 3 + 1)，很接近于O(N)
……
快结束时，gap很小，带入到总次数可得总次数接近于等差数列，应该是O(N²)，但其实并不是，因为这是最后的一次预排序，接近有序，所以我们可以近似为O(N)
我们可以将每一次的预排序的运行次数看作O(N)
N/3/3/3/3……/3/3/3=1
N/2/2/2/2……/2/2/2=1
所以预排序的次数是logN，2和3作为log的底数我们不管。所以次数就是logN
那我们其实就可以毛估出来希尔排序的时间复杂度大概是O(N*logN)这个级别的。
但希尔排序的时间复杂度并不是我们毛估出来那样的，其实它的计算难度非常大，因为随着gap的减小，总次数左右两边都是较为趋近于N的，这个时候，他的时间复杂度其实是不可以看作O(N)这类的了，我们这里给出希尔排序时间复杂度的结论，O(N^1.3)，有关的严格数学证明，大家可以自己网上搜索或查阅资料
排序这个地方的时间复杂度有两个量级：一个是O(N^2)，一个是O(N*logN)，希尔排序，堆排序，快排，归并排序，等都是重量级的排序，自然学习的难度也是较大。
二、选择排序
1.直接选择排序
1.直接选择排序思想：我们每次将数组遍历一遍，每遍历一遍就选出最大和最小的数字将其放在序列的首尾，直到将序列遍历完毕或者遍历的只剩一个数字时，我们的序列也就变得有序了。
void SelectSort(int* arr, int n) { //选出来最大和最小的数分别放在左右两端 int begin = 0, end = n - 1; while (begin < end) { int mini = begin, maxi = begin; for (int i = begin; i <= end; i++) { if (arr[i] < arr[mini]) { mini = i; } if (arr[i] > arr[maxi]) { maxi = i; } } if (maxi == begin) //我们这里需要做一下调整，因为有可能最大元素的位置在begin的位置，这样我们以交换元素之后，maxi的位置就是最小元素了。 //所以如果maxi在begin的位置上，我们就需要事先把maxi的下标改为mini的下标，这样在交换元素过后，mini正好就是最大元素了。 maxi = mini; Swap(&arr[begin], &arr[mini]); Swap(&arr[end], &arr[maxi]); //下面那次不用调整的原因是，上面调整过后，maxi位置肯定不存在最小元素的情况，所以不存在交换最大元素和end位置时，出现最小元素在end //位置，因为我们是先交换begin和mini，所以下面再次交换时，肯定是不会出问题的，因为我们上面已经交换过了。 begin++; end--; } }
2.代码细节说明：
如果出现最大元素下标正好在left位置的时候，我们第二次交换max和right一定会出问题，所以我们需要对这样的情况做出调整，将max的下标改为min的下标。
当然也有人或许会有疑问，那最小元素如果出现在right位置时，你不需要做出调整么？答案是：不需要做出调整，只需要调整一次就够了。
因为我们交换元素的顺序是先交换小在交换大，所以只要交换小不出问题，后面的交换大肯定也不会出问题。
2.堆排序（已经建好堆的基础之上）
1.堆排序思想
升序建大堆，降序建小堆，不断的利用向下调整算法将堆顶元素依次放到堆尾。记得父节点和子节点之间的关系：parent=(child-1)/2不要给忘了。我们每重新调整堆时，传给向下调整算法的数组个数要减1，因为我们交换一次，数组的最后一个元素已经变得有序了，不需要我们调整了。
void AdjustDownTeach(HPDataType* array, int n, int parent) { int child = parent * 2 + 1;//上来我们就先假设最大的孩子是左孩子 while (child<n)//我们想的是循环结束的条件，写的是循环继续的条件 { //保证有右孩子的同时，看看我们的假设是否正确，错误就调整 if (child + 1 < n && array[child + 1] > array[child]) //如果假设错误，我们将孩子改为右孩子，并且你也有可能没有右孩子，没有右孩子，默认左孩子就是最大的 //这里其实不用担心没有孩子的问题，因为如果parent没有孩子，child被赋值过后肯定大于n了直接跳出循环了就。 { ++child;//将下标自增，左孩子就变为右孩子 } if (array[parent] < array[child])//我们这里建的是大堆 { Swap(&array[parent], &array[child]); parent = child; child = parent * 2 + 1;//这里再重新假设左孩子是大的，下一次循环就是先看看我们的假设是否正确，若不正确就进行调整。 } else { break; } } } void HeapSort(int* arr, int n) { for (int i = 1; i < n; i++) { Swap(&arr[0], &arr[n - i]); AdjustDownTeach(arr, n - i, 0);//我们传过去的数组大小是需要逐渐减小的，所以传的是n-i } }
2.代码细节说明：
a. 无论是建堆还是堆排序，其核心主要还是在于向下调整算法，既能帮助我们建堆，又能帮助我们对堆进行排序。我们主要说明一下向下调整算法的代码细节。
b. 由于每次判断左孩子和右孩子哪个大很费时间，并且代码写起来不够精炼，所以这里利用了一个代码技巧，就是上来就假设左孩子是最大的，如果我们假设错误，那就重新进行调整，在调整的那部分代码，有一个很坑的地方就是，有可能父节点没有右孩子，此时在if语句的条件判断部分就出现了越界访问的问题，所以我们还要加上一个判断条件，就是保证有右孩子的同时，去看一下我们的假设是否正确。
c. 另外有关于向下调整算法什么时候向下调整结束，我们这里也要说一下，一定是child>=n时，循环就要结束了，说一下为什么child==n循环就结束就可以了，因为child>n循环肯定是要结束的，这个应该是很好理解的，我也就不多说了
三、交换排序（Swap）
1.冒泡排序（大学牲最熟悉的排序）
1.冒泡排序思想：
每遍历一次序列就将最大的元素交换到序列的最后面，直到遍历的序列中元素仅剩1个时，冒泡排序结束。
void BubbleSort(int* arr, int n) { for (int i = 0; i < n; i++) { int exchange = 0; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { Swap(&arr[j], &arr[j + 1]); exchange = 1; } } if (exchange == 0) { break;//数组元素已经有序，不用继续排序了，跳出循环即可。 } } }
2.代码细节说明： 就简单的做了一个优化，如果我们排序的某一趟每个元素都不用交换，则说明这一趟要排序的元素已经有序，那后面的每趟排序其实就不用进行了，我们选择直接跳出循环。
2.快速排序（The fastest sort of all sorts有点儿装B，但确实挺快）
2.1 hoare版本
1.hoare排序思想： 我们默认序列左起第一个数为key，我们定义两个下标left和right分别从序列的左边和右边去找值，left找比key大的值，right找比key小的值，找到之后，交换left和right的值，等到left和right相遇的时候，此时的值一定是比key小的值，我们再把key和这个相遇位置的值进行交换，这样key就回到它应有的正确位置上，我们再递归处理key的左边区间和右边区间，递归结束之后，快排也就结束了。
int PartSort1(int* arr, int left, int right) { //1.默认左边的数为key值 //2.先让右边的数走，找小。再让左边的数走，找大，交换两个元素 //3.当两边相遇的时候，相遇位置一定是比key要小的值，交换key和相遇位置 int key = left; while (left<right) { while (left < right && arr[right] >= arr[key]) { right--; } while (left < right && arr[left] <= arr[key]) { left++; } Swap(&arr[left], &arr[right]); } Swap(&arr[key], &arr[left]); key = left; return key; void QuickSort(int* arr, int begin, int end) { if (begin>=end)//递归结束条件 { return; } int key = PartSort1(arr, begin, end); QuickSort(arr, begin, key - 1); QuickSort(arr, key + 1, end); } }
2.代码细节说明：
代码思路看起来比较简单，其实实现的时候，有很多坑人的地方。
a. 如果key后面的每个数都比key小或大的话，那left向后面找或right向前面找，就会产生越界访问的问题，为了防止这样情况的产生，我们选择在if语句的判断部分加个逻辑与&&保证left小于right，以免产生越界访问的问题。
b. 我们在if语句的判断部分，找的数一定得比key小或大，连相等都是不可以的，为什么呢？因为会产生死循环。
一旦序列中的左右出现相等的数字的时候，我们if语句如果写成＞或＜而不是>=或<=，程序就废了。
2.2 三数取中+小区间优化
三数取中就是为了让我们选取的key在序列中的位置尽量靠中间，让我们递归处理的效率更高。
int GetMidIndex(int *arr, int begin, int end) { int mid = (begin + end) / 2; if (arr[begin] > arr[end]) { if (arr[end] > arr[mid]) { return end; } else if (arr[begin] < arr[mid]) { return begin; } else { return mid; } } else// arr[begin] < arr[end] { if (arr[mid] < arr[begin]) { return begin; } else if (arr[end] > arr[mid]) { return mid; } else { return end; } } }
小区间优化是为了让递归深度不要太深，因为数据量过大以后，我们递归的深度就会增加，递归建立的栈帧数量会随着递归深度的增加而增加，又因为栈空间本身就小，很容易造成栈溢出的问题，这时我们就想到了一个办法，例如当递归区间的数据量较小的时候，我们不采用递归解决他们，而是换成直接插入的方法来解决较小数据量的排序。
void QuickSort(int* arr, int begin, int end) { if ((end - begin) < 1)//递归结束条件 { return; } if ((end - begin + 1) < 15) { InsertSort(arr + begin, end - begin + 1); } else { int key = PartSort1(arr, begin, end); QuickSort(arr, begin, key - 1); QuickSort(arr, key + 1, end); } }
2.3 挖坑法版本
1.挖坑法思想
挖坑法的思想还是要比hoare大佬的思想更加容易理解的，整体是一个什么思想呢？
我们先在序列的最左边挖一个坑，然后这个坑位的值就是key值，然后从右往左找比key小的值填到坑位上面去，这个时候坑位就变成right位置了，我们再从左向右找比key大的值，把这个值填到坑位上面去，再将坑位更新为left，循环进行这个工作，直到left和right相遇，他们相遇的位置也就是最后一次hole的位置，我们将key填到hole的位置，这样key就回到它本身的位置了。
剩下的工作我们还是交给递归，递归处理左区间和右区间。
int PartSort2(int* arr, int left, int right) { int mid = GetMidIndex(arr, left, right); Swap(&arr[left], &arr[mid]); int hole = left; int key = arr[left]; while (left<right) { while (left < right && arr[right] >= key) { --right; } arr[hole] = arr[right]; hole = right; while (left < right && arr[left] <= key) { ++left; } arr[hole] = arr[left]; hole = left; } arr[hole] = key; return hole; }
2.代码细节说明：
填好坑位的值之后，我们要记得将坑位进行更新，最后坑位的下标其实就是key应该在的位置的索引。
实现起来还是较为简单的，有了前面hoare版本的铺垫。
2.4 前后指针版本
1.前后指针思想：
我们定义两个指针一个cur一个prev，利用cur去找比key小的值，然后交换cur和prev++的值，让cur不断的向后找比key小的值，等到cur找完整个数组之后，prev位置的值肯定是比key要小的，所以prev的位置其实就是key最终应该待在的位置，这样我们就处理好key了。
剩下的还是交给递归处理。
int PartSort3(int* arr, int left, int right) { int mid = GetMidIndex(arr, left, right); Swap(&arr[left], &arr[mid]); int key = left; int prev = left, cur = left + 1; while (cur <= right) { if (arr[cur] < arr[key] && ++prev != cur)//逻辑与后面的条件就是为了防止交换同一个位置的元素，这时交换没有必要 { Swap(&arr[cur], &arr[++prev]); } cur++; } Swap(&arr[key], &arr[prev]); return prev; }
2.代码细节说明：
有的人可能看到++prev!=cur时，有些蒙，但其实这个就是为了避免同一位置的值交换多次所做的优化。
cur是需要一直向后走的，我们只需要判断cur的每一个位置的值和key的关系并将其处理即可。
2.5 三指针版本（快排的终极优化，可适用任何刁钻的数据分布）
1.三指针思想：
假设某个序列中几乎所有数据都是相同的，并且数据量极大的情况下，原来的快排就无法适用了，因为要建立很多栈帧，递归深度太深，运行时间过长，那些几乎所有相同的数据，我们完全可以将其集中起来，把他们放到他们应该在的位置，不对其作任何处理。
这时候就从原来的前后指针版本衍生出我们的三指针版本。
大体思路：
定义left，right，cur等三个下标，利用cur对序列的遍历，找出大于key，等于key，小于key的各个数字，将他们交换到left和right等下标位置，然后递归剩余的左右区间，完成我们的排序。
void QuickSortPlus(int* arr, int begin, int end) { if (begin >= end) { return; } if ((end - begin + 1) < 15) { InsertSort(arr + begin, end - begin + 1); } else { int mid = GetMidIndex(arr, begin, end); Swap(&arr[begin], &arr[mid]); int key = arr[begin]; int left = begin, right = end, cur = begin + 1; while (cur <= right) { if (arr[cur] < key) { Swap(&arr[left], &arr[cur]); left++; cur++; } else if (arr[cur] > key) { Swap(&arr[cur], &arr[right]); right--; } else//arr[cur]==key时 { cur++; } } QuickSortPlus(arr, begin, left - 1); QuickSortPlus(arr, right + 1, end); } }
2.代码细节说明：
因为我们是将left位置看作key，所以只有交换比key小的元素时，cur才可以++，或者遇到和key相等的值时，cur可以++，我们必须保证left左侧都是比key小的值，left和right中间都是和key相等的值，right右侧都是比key大的值。
然后我们递归begin到left-1，right+1到end两个区间，即可完成排序
3.快速排序（非递归）
1.快排非递归思想
我们可以利用栈结构来存储递归区间，然后再利用快排的随便一个算法模块儿对这个区间进行排序，之后再继续入栈剩余的区间，并进行排序。
void QuickSortNonR(int* arr, int begin, int end) { ST st; StackInit(&st); StackPush(&st, begin); StackPush(&st, end); while (!StackEmpty(&st)) { int right = StackTop(&st); StackPop(&st); int left = StackTop(&st); StackPop(&st); int key = PartSort3(arr, left, right); // [begin,key-1] [key+1,end] if (key + 1 < right)//key+1==right说明区间只剩一个值，无需入栈了，一个元素可以认为有序 { StackPush(&st, key+1); StackPush(&st, right); } if (left < key - 1) { StackPush(&st, left); StackPush(&st, key-1); } } StackDestroy(&st); }
2.代码细节说明：
只要区间长度大于等于2，我们就需要继续入栈剩余的区间，其实非递归还是延续了递归的思想，我们用入栈出栈模拟了递归的过程。
