前言
排序，就是使用一串记录，按照其中的某个或某些关键字的大小，递增或者递减的排序起来的一系列操作。
排序算法有着广泛的应用，因为有序的数据通常能够更高效地查找、分析和处理。
排序算法大致可以分为以下几种：
一、排序算法评价维度
运行效率：我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（时间复杂度中的常数项变小）。对于较大的数据量的情况，运行效率显得尤为重要。
就地性：顾明思义，原地排序通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从节省内存。通过情况，原地排序的数据搬运操作较少时，运行速度也更快。
稳定性：稳定排序在完成排序后，相等的元素在数组中的相对顺序不发生变化。
自适应性：自适应排序的时间复杂度会受输入数据的影响，即最佳时间复杂度、最差时间复杂度、平均时间复杂度并不完全相同。
是否基于比较：基于比较的排序依赖比较运算符（< 、= 、>）来判断元素的相对顺序，从而排序整个数组，理论最优时间复杂度为O(n * log n)。而非比较不使用比较运算符，时间复杂度可以达到O(n)，但其通用性相对较差。
现在来学习各种排序算法，并基于上述各种评价维度对各个算法的优缺点进行分析。
二、插入排序
2.1、直接插入排序
2.1.1、插入排序分析及代码实现
直接插入排序，当插入第i(i>=1)个元素，前面的数据已经有序，此时用arr[ i ]的数据与arr[ i - 1 ]，arr[ i - 2 ]，arr[ i - 3 ]，直到第一个数据，找到插入位置就将arr[ i ] 插入，原来位置上的元素顺序后移。
如上图所示，插入排序的过程，现在就来使用代码实现一下。
void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } void InsertSort(int* arr, int n) { for (int i = 0; i < n - 1; i++) { int end = i; while (end >= 0) { if (arr[end] > arr[end + 1]) { Swap(&arr[end], &arr[end + 1]); end--; } else { break; } } } }
这里也可以不使用交换函数，将arr[end+1]的值存起来，直接将end位置的值赋给end+1。
代码如下：
void InsertSort1(int* arr, int n) { for (int i = 0; i < n - 1; i++) { int end = i; 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.1.2、插入排序时间复杂度分析
最优情况：
数组已经有序为升序（这里排序为升序），此时只需要进行n次循环比较，时间复杂度为O(n)。
平均情况：
平均情况下，时间复杂度为O(n^2)，这里数组的每一个数据都需要与排序好的数据进行多次比较，平均下来一个数据比较n/2次，需要循环n次，时间复杂度就为O(n^2)。
最差情况：
最差情况就是数据有序为降序（我们要排序为升序），此时每一个数据都需要与已经排序完的数据一一进行比较并交换，时间复杂度为O(n^2)。
2.1.3、直接插入排序的优化
直接插入排序算法复杂度为O(n^2)，效率并不高，这里对其进行优化。
直接插入排序优化，可以将数组数据进行分组，先让部分数据有序，再逐渐减少每一组数据的个数，直到为1。
2.2、希尔排序
希尔排序，就是对直接插入排序的优化；
希尔排序又称缩小增量法。希尔排序的基本思想：
选定一个整数（通常情况下gap = n / 3 +1），把待排序数据分成各组，所以的距离相等的记录分别在同一组内，对每一组数据进行排序，然后gap = gap / 3 +1得到下一个整数，继续将数组分成各组，进行插入排序，当gap = 1 时，就相当于直接插入排序（但是此时，数组已经基本有序）。
代码实现：
//希尔排序 void ShellSort(int* arr, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1; for (int i = 0; i < n -gap; i++) { int end = i; while (end >= 0) { if (arr[end] > arr[end + gap]) { Swap(&arr[end], &arr[end + gap]); end = end - gap; } else { break; } } } } }
希尔排序时间复杂度：
内层循环
这里因为gap的取值不一样，（可以取2、3.......），希尔排序的算法复杂度就很难计算。
外层循环
这里外层循环复杂度取决于gap的取值，时间复杂度O(log2 n)或者(log3 n）时间复杂度可以表示为O(log n)。
对于希尔排序算法的时间复杂度，计算十分复杂
三、选择排序
选择排序的基本思想：
每一次从待排序的数据元素中选出最大（或者最小）的一个元素，存放在序列的其实位置，直到数组所有元素排序完。
3.1、直接选择排序
这里可以选最大的数据，放到数组末尾；也可以选最小的，放到数组开头。如下图所示：
这里只找最大或者最小的效率有点低，我们两个一起找。
这里两个一起找，就要注意，当找到最大值的小标maxi与left（排序左区间）相等时，我就要另加判断（因为需要将left的数据与最小值mini进行交换）。
//直接选择排序 void SelectSort(int* arr, int n) { int mini = 0, maxi = 0; int left = 0, right = n - 1; while (left < right) { for (int i = left; i < right; i++) { if (arr[i] < arr[mini]) { mini = i; } if (arr[i] > arr[maxi]) { maxi = i; } } if (maxi == left) { maxi = mini; } Swap(&arr[mini], &arr[left]); Swap(&arr[maxi], &arr[right]); left++; right--; } }
3.2、堆排序
在之前，数据结构堆中，提到了堆排序，这里实现堆排序就是利用堆的这种思维，这里使用堆排序前提数据是堆结构（所以这里就需要先堆数组进行建堆操作）。
在每次将堆顶数据与堆最后一个数据交换，再向下调整后，不将这个数据删除，而是留着堆的末尾；接下来接着让第一个数据与倒数第二个数据交换，再向下调整；直到调整完堆里的全部数据。
代码实现：
void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } //向下调整算法 void AdjustDown(int* arr, int parent, int n) { int child = 2 * parent + 1; while (child < n) { if (child< n - 1 && arr[child]>arr[child + 1]) { child++; } if (arr[child] < arr[parent]) { Swap(&arr[child], &arr[parent]); parent = child; child = 2 * parent + 1; } else { break; } } } //堆排序 void HeapSort(int* arr, int n) { //建堆 for (int i = (n-1-1)/2; i >= 0; i--) { AdjustDown(arr, i, n); } //堆排序 int end = n - 1; while (end > 0) { Swap(&arr[0], &arr[end]); AdjustDown(arr, 0, end); end--; } }
堆排序的算法复杂度：O(n*log n)。
到这里，插入排序和选择排序就结束了，对于排序算法还有交换排序，快速排序和归并排序，非比较排序等。
敬请期待后面的排序算法内容。
感谢各位大佬支持并指出问题，
如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！
