排序：所谓排序，就是使一组杂乱无章的数据，按照其中的一定的规律或某些关键字
(如价格，销量，好评率，排名等)的大小，递增或递减地排列起来的操作。
为了方便，我们这里讲的排序和有序指的都是升序，降序反过来就行了。
1.插入排序
1.1直接插入排序
核心思想：
把一个数插入一个有序区间。
实现方法：假设0—end是已经有序的区间，我们用x存储end后面一个位置的元素，表示要把x存储到0—end的有序区间中。
如果end所指元素比x大，就把end所指的元素赋给后面一个位置的元素（相当于把end所指元素往后移动一个格子），然后end=end-1使end指向前一个元素，继续比较；
1.1.1单趟插入排序：（把x插入一个有序数组）
//单趟排序：（把x插入一个有序数组） // 1 2 3 5 9 10 12 x=4 void InsertSort(int* arr, int sz) { int end; int x; while (end >= 0) { if (arr[end] > x) { arr[end + 1] = arr[end]; end--; } else { break; } } arr[end + 1] = x;//插入在最头上和插入在中间都在这里处理 }
整个数组排序，如何控制呢？我们把上面的x赋值给arr[ end +1 ] 然后重复插入就是这样：
1.1.2完整插入排序代码：
void InsertSort(int* arr, int sz) { assert(arr != NULL); for (int i = 0;i <= sz - 2;i++) { int end = i;//把数组第一个元素当作有序，像打扑克牌摸牌排序一样 int x = arr[end + 1]; //x已经保存了a[end + 1] 所以后面再覆盖也可以 因此end只能落在n-2 while (end >= 0) { if (arr[end] > x) { arr[end + 1] = arr[end]; end--; } else { break; } } arr[end + 1] = x; } }
为了验证代码，我们像以前一样分文件写，先把部分Sort.c和Test.c放出来，后面再把完整的放出来
#include"Sort.h" 先写打印数组函数和交换函数（后面排序使用） void printArr(int* arr, int sz) { for (int i = 0;i <= sz - 1;i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = { 1,6,5,4,7,8,9,2,0,3 }; int sz = sizeof(arr) / sizeof(arr[0]); printArr(arr, sz); InsertSort(arr, sz); printArr(arr, sz); //输出：0 1 2 3 4 5 6 7 8 9 return 0; }
1.1.3插入排序复杂度分析：
直接插入排序最坏情况是逆序（每插入一个都要移动,从第二个元素开始，第二个元素需要移动1次，第三个元素需要移动2次，…，第n个元素需要移动n-1次）
取最大项就是O(N^2).
最好情况是已经有序或者基本有序，就只需要遍历一次数组（有序）或者偶尔几个元素需要移动几次格子再插入其他的直接插入在end所指元素后面就行（基本有序），故最好情况下时间复杂度是O(N)。
没有开辟额外的空间所以：插入排序的空间复杂度是O（1），时间复杂度是O（N^2）
我们之前写过冒泡排序
我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，
它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，
移动次数上都是原本数据的逆序度。
元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，
冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，
所以总的交换次数冒泡排序大于插入排序。
有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，
如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，
但是我们实际使用中还是优先选择插入排序。
对于插入排序还是可以优化的，对了，没错，就是下面的希尔排序
这里先说插入排序是比冒泡排序好的排序。（铺垫）
（我在最后的八大排序完整代码中放入了测试效率的测试，想测任何排序的时候可以去看看）
这里想到方便对比，所以讲完八大排序后再统一讲完八大排序的复杂度
1.2希尔排序
插入排序面对逆序或不太有序的情况下效率比较低，但是面对基本有序的情况它是非常棒的排序
（基本有序的话时间复杂度是O(N)，是排序算法的天花板，没有一个排序算法能比O(N)快）。
为了优化直接插入排序，一个叫希尔的人想出来了一种排序（希尔排序），核心思想：
希尔排序就是在直接插入排序上优化，既然对基本有序的情况直接插入排序很棒，
那我先分成gap组进行一个预排序（这个过程可以使数组基本有序），
然后再进行一个直接插入排序，那么怎么样进行预排序呢？
预排序步骤：
1.2.1单趟预排序：
按gap（缺口，缝隙，差距）分组，分成gap组，gap>1，对每个组进行插入排序，
使总体数组看起来接近有序
实际上就是把0，0+gap，0+2gap…视为一组，1，1+gap，1+2gap…视为一组...
对每一组进行直接插入排序，这样每一组都是有序的了，总体数组就比之前有有序多了。
那么对0,0+gap,0+2gap…这一组预排序的单趟排序代码如下（这里gap取3）：
//分组的单趟和前面单趟插入排序一样，间距是gap，前面可以认为gap=1 //按gap分组进行预排序 int gap = 3; int end = 0; int x = arr[end + gap]; while (end >= 0) { if (arr[end] > x) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = x;
1.2.2对所有组的预排序：
//依次排完gap组 int gap = 3; for (int j = 0; j < gap; j++) { for (int i = j; i < n - gap; i += gap) { int end = i; int x = arr[end + gap]; while (end >= 0) { if (arr[end] > x) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = x; } }
上面的代码虽然清楚，但是不够简洁，我们可以对多组同时进行预排序，
就好像把多组同时一锅炖了一样。对单趟多组预排序的代码改造如下：
1.2.3预排序代码简化：
int gap = 3; for (int i = 0; i < n - gap; i++) { int end = i; int x = arr[end + gap]; while (end >= 0) { if (arr[end] > x) { //如果end所指的元素比x大 //就把end所指元素往后移动，空出一个格子 arr[end + gap] = arr[end]; end -= gap; } else { //否则就跳出去， //这样可以同时处理end小于0的情况（插入在最头上的情况） break; } } arr[end + gap] = x; }
怎么取gap呢？讨论一下预排序的时间复杂度
与直接插入排序类似，最好情况是已经有序的时候，是O(N)（遍历一遍就行了）
最坏情况：每一组都是逆序的，每一组的元素个数是[N/gap]，这样的总共需要的循环次数是：gap*(1+2+3+…+[N/gap]-1)（套用最糟糕情况直接插入排序的循环次数，gap组）。
观察这个总共需要的循环次数的函数，发现:
gap越大 预排越快(gap=N，O(N)) ,但是因为分的组数太多了，排完后越接近无序；
gap越小 预排越慢(gap=1，O(N^2)),分的组数少排完后越接近有序。
多趟分组预排序与最后的直接插入排序
为了让最后进行插入排序的时候数组能更接近有序一些，我们可以加一个循环控制gap不断变化进行多趟分组预排序，并且把gap=1时，也就是最终进行直接插入排序耦合到while循环里，代码如下：
1.2.4完整希尔排序代码：
void ShellSort(int* arr, int sz) { int gap = sz; //多次预排序(gap > 1)+直接插入排序(gap == 1) while (gap > 1)//gap进去以后才除所以大于1就行 { //两种取gap的方法： //gap = gap / 2;//一次跳一半 gap = gap / 3 + 1; //加一是为了保证最后一次gap小于3的时候 //能够有gap等于1来表示直接插入排序 //多组同时搞： for (int i = 0; i < sz - gap; i++) { int end = i; int x = arr[end + gap]; while (end >= 0) { if (arr[end] > x) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = x; } } }
代码测试（依然输出0 1 2 3 4 5 6 7 8 9）
#include"Sort.h" int main() { int arr[] = { 1,6,5,4,7,8,9,2,0,3 }; int sz = sizeof(arr) / sizeof(arr[0]); printArr(arr, sz); //InsertSort(arr, sz); ShellSort(arr, sz); printArr(arr, sz); return 0; }
2.选择排序
2.1选择排序
- 在一个长度为 N 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
- 第二次从下一个数开始遍历 n-2个数，找到最小的数和第二个数交换。
- 重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。
2.1.1选择排序代码：
void SelectSort(int* arr, int sz) { //先假设第一个元素最小 for (int i = 0; i < sz; i++) { int begin = i; int minindex = i; while (begin < sz) { if (arr[begin] < arr[minindex]) { minindex = begin; } begin++; } Swap(&arr[minindex], &arr[i]); } }
2.1.2选择排序代码优化：
我们可以定义一个begin变量，一个end变量，用来记录数据首和尾的下标，我们一个可以找出两个值，一个最大值，一个最小值，最小值放在a[begin]中，最大值放在a[end]中，这样我们就比上面的快多了
void SelectSort(int* arr, int sz) { int begin = 0; int end = sz - 1; while (begin < end) { int mini = begin; int maxi = end; int i = 0; for (i = begin;i <= end;i++) { //选出[begin,end]中最大和最小的 if (arr[i] < arr[mini]) { mini = i; } if (arr[i] > arr[maxi]) { maxi = i; } } Swap(&arr[begin], &arr[mini]); //这里需要考虑第一个值放最大值的情况，如果第一个值为最大值,此时最大值位置被移动 if (begin == maxi) { maxi = mini;//最大的值被换到了mini的位置，更新最大值的位置 } Swap(&arr[end], & arr[maxi]); begin++; end--; } }
2.2堆排序
要学习堆排序，首先要学习基础的二叉树结构，学习堆的向下调整算法，使用堆排序之前，
我们得先建一个堆出来，堆的向下调整算法的前提是：根节点的左右子树均是大堆或小堆。
由于堆排序在向下调整的过程中，需要从孩子中选择出较大或较小的那个孩子，
父亲才与孩子进行交换，所以堆排序是一种选择排序。
堆排序的详解请移至博客：
数据结构与算法⑫(第四章_中_续一)堆排序（详解）_GR C的博客-CSDN博客
2.1.1堆排序代码：
void justDown(int* arr, int sz, int father_idx) { int child_idx = father_idx * 2 + 1; // 计算出左孩子的值（默认认为左孩子大） while (child_idx < sz) // 最坏情況：调到叶子（child_idx >= 数组范围时必然已经调到叶子） { if ((child_idx + 1 < sz) && (arr[child_idx + 1] > arr[child_idx])) { // 如果右孩子存在且右孩子比左孩子大 child_idx = child_idx + 1;// 让其代表右孩子 } if (arr[child_idx] > arr[father_idx])//如果孩子的值大于父亲的值（不符合大堆的性质） { Swap(&arr[child_idx], &arr[father_idx]); father_idx = child_idx; // 更新下标往下走 child_idx = father_idx * 2 + 1; // 计算出该节点路线的新父亲 } else // 如果孩子的值小于父亲的值（符合大堆的性质） { break; } } } //完整堆排序_升序 void HeapSort(int* arr, int sz) { //创建大堆，选出最大的数，时间：O(N) int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲 while (father >= 0) { justDown(arr, sz, father); father--; } //交换后调堆 时间：O(N * logN) int end = sz - 1; while (end > 0) { Swap(&arr[0], &arr[end]); justDown(arr, end, 0); end--; } }
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)（中）：https://developer.aliyun.com/article/1513587
