一 .直接插入排序
直接插入排序是从一段数据中将一个数据在合适的位置插入。
案例：
一张图弄懂直接插入排序
实现代码：
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(a[end]>tmp) { //把end往后挪 a[end+1] = a[end]; //end再往前走 end--; } else { break; } } //由于不管是在中间的任意地方插入还是在end的末尾插入（即tmp是最大的情况）， //都是在end后面的位置插入，所以来到这里进行合并 a[end+1] = tmp; } }
直接插入排序时间复杂度
直接插入排序的时间复杂度为：O(N^2)，因为最坏的情况是逆序的情况：
每一次插入需要挪动的次数为：1+2+3+4+…+n-2+n-1 = n*n/2
所以最坏情况下的时间复杂度为O(n^2)
二.希尔排序
希尔排序可以被认为是优化后的直接插入排序。
具体优化过程如下：
给定一个gap，这个gap是把待插入的数据分成gap组，每组之间的间隔为gap长度
给定一个gap，这个gap是把待插入的数据分成gap组，每组之间的间隔为gap长度
给定一个gap，这个gap是把待插入的数据分成gap组，每组之间的间隔为gap长度
重要的事情说三遍。
比如：
令gap = 3，即待插入的数据的间隔为3，不同于直接插入排序，直接插入排序是第一个和第二个数据的间隔永远为1，而对于希尔排序，当gap = 3时，第一个数据和第二个数据的间隔为3。
当我们把该组的元素两两比较时，大的元素就会更快地往后走。
第二轮是将待插入元素8和9比较，因为9后面的第一个元素不再是7，而是9+gap的位置处的数据，即8
再将9和8进行比较，将8插入到9位置处。
当然，这是每组组内的比较，
放眼整个希尔排序来说，是多组同时进行的。
可以发现，
当gap越大，大的元素越快挪到后面
当gap越小，小的元素越慢挪到后面
当gap == 1时，就相当于上面提到的直接插入排序。
回到上面的案例，gap = 3，所以需要将数据分成3组，每组的间隔为3个长度。
如上图：此时每个元素都可以被覆盖到。
相当于同时把gap组中大的元素更快挪到后面
我们把上面的过程成为：预排序
也就是说，完成上面的操作之后，整个数据并不是有序的，而是 接近有序
比如上面的案例，完成预排序后，整组数据为：
此时是接近有序，所以此时令gap = 1，即最后接近有序的时候进行直接插入排序即可。
注意：gap的取值是不确定的：
gap取值越大，大的数据越快挪到后面，但越不接近有序
gap取值越小，大的数据越慢挪到后面，但越接近有序
总之gap是一定不能固定，并且gap的取值最后必须为1。
gap的取值应该是从大逐渐到小过渡的。
gap的取值一般是：
初始化gap = n，
进入轮回时：
gap = gap/3+1 或者 gap = gap/2，每次轮完一轮后，gap都会减小。
当gap的取值是gap = gap/2时，时间复杂度为：O(N*logN)，logN是以2为底N的对数
最坏情况同样为逆序：
最后一轮gap = 1，此时为直接插入排序，则N/2/2/2/…/2 = 1，
每次轮回一次gap，gap都会/2，最后一次gap = 1，则需要比较的次数是logN(以2为底N的对数)
实现代码：
void ShellSort(int* a, int n) { //当gap越大，大的值越快到达最后的位置,但越不接近有序 //当gap越小，大的值越慢到达最后的位置，但越接近有序 //当gap值越接近1，排序越接近顺序 //刚gap == 1时，就是直接插入排序 int gap = n; while (gap > 1) { //两种方式均可，gap可以任取任何值，但是都必须保证gap最后一定为1 //gap = gap / 2; gap = gap / 3 + 1; //在这里就是把间隔多组的数据同时排列 for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end >= 0) { //小于的情况，需要挪动数据 if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } //大于或者等于的情况，直接插入end后面 else { break; } } //由于最终都需要插入end后面，所以在循环之外插入 a[end + gap] = tmp; } } }
总结：希尔排序是在直接插入排序的基础上引入一个gap，这个gap把数据分成了gap组，并且每组元素之间的间隔也为gap。
gap每次都会逐渐减小，并且最后gap一定为1，当gap为1时，代表完成了预排序，
最后一步进行直接插入排序。
希尔排序时间复杂度
总的时间复杂度为遍历整组元素的次数：O(N)*每次遍历进行插入的次数O(logN)
—> O(N * logN)
同理：当gap的变化是gap = gap/3-1时， 最坏情况下（逆序）每次轮回需要插入的次数是
(((N/3+1) /3+1)/3+1)… = 1
对于时间复杂度：可忽略掉+1项，所以每次轮回插入次数log3 (N) ,以3为底N的对数
总时间复杂度为O(N*log3 (N))
经过前人计算，希尔排序平均时间复杂度为：
O(N^1.3)
前文知识清单：
三、选择排序
直接选择排序通过每一轮的比较，找到最大值和最小值，将最大值的节点跟右边交换，最小值节点跟左边交换，达到排升序的效果。
假如最左边的数据的下标为left，最右边的数据的下标为right。
选择排序就是每一轮选出max和min两个数据，将max和right下标的数据交换，将min和left下标的数据交换。交换后，right–，left++，这样第二轮就会找第二小和第二大的数据，依次往后。
实现代码：
void SelectSort(ShellDataType* a, int n) { //左下标 和右下标 int left = 0; int right = n - 1; //不需要left <= right，最后一个元素不需要再交换,当然给<=也没问题 while (left < right) { //假设最小最大全部在left int mini = left, maxi = left; //单趟查找最小值和最大值下标 for (int i = left; i < right; i++) { //找到最小的，更新下标 if (a[i] < a[mini]) { mini = i; } //找到最大的，更新下标 if (a[i] > a[maxi]) { maxi = i; } } //maxi和right交换，mini和left交换 Swap(&a[left], &a[mini]); //这里存在特殊情况，如果maxi在left位置，left和mini交换了之后，最大值的下标就是mini了 //所以这里需要判断一下，如果真的是这种情况，就更新最大值下标。 if (maxi == left) { maxi = mini; } Swap(&a[right], &a[maxi]); //后面的不需要再更新了，因为后面就算mini是在right位置，这轮也已经结束了，所以不需要再管它 //更新left和right 的下标 left++; right--; } }
直接选择排序时间复杂度
每一轮比较都需要遍历数组，查找最大最小值，第一轮遍历N个数据，第二轮是N-2个数据，第三轮N-4 …，遍历次数为：N+N-2+N-4+…+1，一个等差数列求和
所以总的时间复杂度为O(N^2)
四、堆排序
向上调整算法和向下调整算法请参照：数据结构——堆
所谓堆排序，就是排序堆，要求是堆才能够进行排序，所以给任意一个连续数组对数组排序的话，需要先建堆。
使用向上调整法建堆如下图：
结果如下：
时间复杂度为O(N*logN)
使用向下调整建堆如下图：
时间复杂度O(N)
堆排序：
堆排序使用交换之后再向下调整原理：
在建了大根堆之后，堆顶的左右子树都是大根堆，不管最后一个元素是否是最小的，与堆顶元素交换后,
堆顶元素就被放到了堆尾，然后再让堆顶元素向下调整，因为此时堆顶元素是一个较小的元素，会向下调整，调整之后是第二大的元素在堆顶下一次再排序时，排的是堆尾的前一个了，那个最大的元素不用再排了，排的就是第二大的元素，
再让堆的最后一个元素与堆顶元素交换，再进行向下调整，调整完后第三大的元素就上来了。
建好堆后，对堆进行排序，堆排序过程图如下：
实现代码：
void HeapSort(int* a, int n) { assert(a); //1.先建堆，向上调整建堆,建堆的时间复杂度为O(N*logN) //也可以采用向下调整的方法建堆，向下调整的方法建堆的时间复杂度为O(N) //强烈建议采用向下调整的建堆方式 //for (int i = 0; i < n; ++i) //{ // AdjustUp(a, i); //} //向下调整建堆，是从第一个非叶子节点开始调整，因为所有的叶子节点都不需要进行向下调整 //child = (parent-1)/2 //此时parent就是n-1 for (int i = (n - 1 - 1) / 2; i >=0; -- i) { AdjustDown(a, n, i); } //现在是大根堆 //2.堆排序，采用向下调整算法进行排序,让最后一个节点和堆顶节点进行交换，然后堆顶节点向下调整 //调整完后继续倒数第二个节点和堆顶节点交换,以此类推 for (int i = n-1; i >0; --i) { swap(&a[0], &a[i]); //这里传参不能传n，传n-1,因为交换之后最后一个数字就不需要参与进来了，相当于size-- //堆排序使用交换之后再向下调整原理： //在建了大根堆之后，堆顶的左右子树都是大根堆，不管最后一个元素是否是最小的，与堆顶元素交换后 //堆顶元素就被放到了堆尾，然后再让堆顶元素向下调整，因为此时堆顶元素是一个较小的元素，会向下调整，调整之后是第二大的元素在堆顶 // //下一次再排序时，排的是堆尾的前一个了，那个最大的元素不用再排了，排的就是第二大的元素， //再让堆的最后一个元素与堆顶元素交换，再进行向下调整，调整完后第三大的元素就上来了。 AdjustDown(a, i, 0); } //总结：排升序的话，建大根堆 //排降序建小根堆 for (int i = 0; i < n; i++) { printf("%d ", a[i]); } }
堆排序时间复杂度
建堆的时间复杂度为O(N)
调整过程遍历N个数的时间复杂度为O(N)
每次调整一个数的时间复杂度为O(logN)
总的时间复杂度为O(N+N*logN)
综上：
堆排序的时间复杂度为：O(N*logN)
五、冒泡排序
冒泡排序（Bubble Sort）：一次比较两个元素，如果他们的顺序错误就把他们交换过来，重复道数列已经不用再交换。冒泡排序名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。相当于升序操作。
每一趟冒泡排序，就排序一个数，可以形象地认为把一个大的数字放到水底，把小的数放在水面，慢慢冒出泡泡来。
冒泡排序实现代码：
void bubble_sort(int* arr, int sz) { int i = 0; for (i = 0; i < sz - 1; i++) { //sz-1是冒泡排序的趟数 int j = 0; for (j = 0; j < sz - 1 - i; j++) { //sz-1-i是每一趟冒泡排序要比较的元素个数 if (arr[j] > arr[j + 1])//升序排序 { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } }
我们发现：当冒泡排序中只有某少数个数据是无序的时候，当进行完了一趟排序，整个数据就有序了，这时候就不需要再比较了。
当进行了一轮排序后，此时数据已经有序，就可以退出不再比较了。
所以冒泡排序还可以进行优化：
void buuble_sort(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { int j = 0; int flag = 1;//假设这一趟冒泡排序已经有序 for (j = 0; j < sz - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = 0;//如果没完全有序，则flag=0，我们才能知道是否完全有序 } } if (flag == 1) { break; } } }
冒泡复杂度
1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：稳定
