八大排序算法
前言
排序是计算机科学中最基础、应用最广泛的算法之一。它将一组无序的数据元素（或记录）按照某种特定的顺序（如升序或降序）重新排列，是数据检索、统计分析、高效算法设计等众多领域的基石。本章总结了学习过程中八大排序算法，包括比较排序和非比较排序。如图所示：
一、插入排序
1.1直接插入排序
当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较，找到插⼊位置即将 array[i] 插⼊，原来位置上的元素顺序后移（归根结底就是前面数据都是顺序的，插入的与前面数据进行比较大小，然后交换，成为有序。进而继续将下一个数据为待插入数据，继续比较以此类推而得到有序排列）。
//直接插入排序void InsertSort(int* arr, int num){for (int i = 0; i 0){//tmp < arr[end-1]将end上的位置给end-1if (tmp = arr[end-1]不移动else{break;}}arr[end] = tmp;}}1. 元素集合越接近有序，直接插⼊排序算法的时间效率越⾼ 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1)
1.2希尔排序
希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n/3+1），把待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于直接插⼊排序（希尔排序用途就是为了将小的数据放到前面，顺便将大的数据放入后面，以达到直接插入排序排序次数大幅度减少）。 
void ShellSort(int* arr, int num){int gap = num;while (gap > 1){gap = gap / 3 + 1;//将数组后面小的数据移动到前面，大幅减少次数for (int i = 0; i = 0){if (arr[end] > tmp){arr[end+gap] = arr[end];//将大的数据arr[end]移动到end+gap位置上end -= gap;}else{break;}}arr[end+gap] = tmp;}}}1. 希尔排序是对直接插⼊排序的优化。 2. 当 gap > 1 时都是预排序，⽬的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体⽽⾔，可以达到优化的效果。
二、选择排序
2.1直接选择排序
每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 (在一段序列中不断寻找最大最小值，并将最大移到右边，将最小移到左边)。 
void Swap(int* change1, int* change2){int tmp = *change1;*change1 = *change2;*change2 = tmp;}void SelectSort(int* arr, int num){int right = num-1;int left = 0;while (left < right)//等于时跳出{//这里设置是为了后面改变right和left时可以把初始值改变int max = right;int min = left;//寻找最大值for (int i = left+1; i arr[max]){max = i;}if (arr[i] < arr[min]){min = i;}}//接下来就是分别插入到最大最小到right和leftSwap(&arr[left], &arr[min]);//这里发现只要arr[left]和max重合时才会使得max下标指的最小值，因此这里需要条件限制if (left == max){max = min;}Swap(&arr[right], &arr[max]);left++;right--;}}这里需要注意的是left和max相同时需要避免把最大值和最小值调换，但是这里还要顺序可言，不能把这个条件判断放到最小值交换过程（这里因为时未来避免最小值不在right上，但是max和min相同，导致排序错误）。
1. 直接选择排序思考⾮常好理解，但是效率不是很好。实际中很少使⽤ 2. 时间复杂度： O ( N 2 ) 3. 空间复杂度： O (1)
2.2堆排序
堆排序(Heapsort)是指利⽤堆积树（堆）这种数据结构所设计的⼀种排序算法，它是选择排序的一种。它是通过堆来进⾏选择数据。需要注意的是排升序要建⼤堆，排降序建⼩堆。（走个过程，详细 堆数据结构_堆 数据结构-CSDN博客 ）
void AdjustDown(int* arr,int parent,int num){int child = parent * 2 + 1;while (child < num){//建大堆 <if (child+1 < num && arr[child] < arr[child + 1]){child++;}//大堆 <if (arr[parent] = 0; i--){//利用堆思想筛选最值AdjustDown(arr, i,num);}//筛选最大值for (int i = num - 1; i > 0; i--){Swap(&arr[0], &arr[i]);//调整堆AdjustDown(arr, 0, i);}}1. 时间复杂度： O (n*log )以至于效率非常快 2. 空间复杂度： O (1)
三、交换排序
3.1冒泡排序
冒泡排序（Bubble Sort）是一种简单直观的排序算法。它通过重复地遍历要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就交换它们的位置。这个过程会一直重复，直到没有需要交换的元素为止，也就是说数列已经排序完成（不断比较当前下标和下边的下一个进行对比，把筛选的数据对换）
void Swap(int* change1, int* change2){int temp = *change1;*change1 = *change2;*change2 = temp;}void BubbleSort(int* arr, int num){for (int i = num - 1; i > 0; i--){int flag = 1;//表示排序完成for (int j = 0; j arr[j + 1]){Swap(&arr[j], &arr[j + 1]);flag = 0;}}if (flag == 1){break;}}}1. 时间复杂度： O ( N 2 ) 2. 空间复杂度： O (1)
3.2快速排序
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为⽌（寻找基准值，将小于基准值的放到左边，大于等于基准值的放到右边，然后不断寻找基准值重复，这样排序就完成了）。 
递归版本：
//快速排序void QuickSort(int* arr, int left, int right){//递归结束条件if (left > right){return;}int keyi = Find(arr,left,right);//寻找基准值//左子树QuickSort(arr, left, keyi-1);QuickSort(arr, keyi + 1, right);}非递归版本：
非递归版本需要保留左右子树的区间进行寻找基准值，这里我们可以使用数据结构栈和队列，为了便利，这里我们使用栈数据结构：
//快速排序（非递归）void QuickSort(int* arr, int left, int right){ST st;StackInit(&st);StackPush(&st,left);StackPush(&st,right);//跳出条件while (!StackEmpty(&st)){int end = StackTop(&st);StackPop(&st);int begin = StackTop(&st);StackPop(&st);//寻找基准值int key = begin;int prev = begin; int cur = prev + 1;while (cur arr[cur] && ++prev != cur){Swap(&arr[prev], &arr[cur]);}cur++;}//找到Swap(&arr[key], &arr[prev]);key = prev;//插入左子树if(begin < key-1){StackPush(&st, begin);StackPush(&st, key - 1);}if (key + 1 < end){StackPush(&st, key + 1);StackPush(&st, end);}}//执行完销毁StackDestory(&st);}3.2.1基准值寻找方法
hoare法:
//寻找基准值int Find(int* arr, int left, int right){int keyi = left;left++;while (left <= right){//left寻找比基准值大while (left <= right && arr[left] < arr[keyi]){left++;}//right寻找比基准值小的while (left arr[keyi]){right--;}//出现left >rightif (left right){return;}int keyi = Find(arr,left,right);//寻找基准值//左子树QuickSort(arr, left, keyi-1);QuickSort(arr, keyi + 1, right);}挖坑法（很少用）：
创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新 的\"坑\"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的\"坑\"，结束循环后将最开始存储的分界值放⼊当前的\"坑\"中，返回当前\"坑\"下标（即分界值下标）
//挖坑法int Find(int* arr, int left, int right){int keyi = left;int temp = arr[keyi];int hole = left;while (left < right){//right寻找比temp小while (left = temp)//这里要等于是为了怕temp=arr[right]时后续填坑无实际意义，反而会导致死循环{right--;}//找到后，插入到hole这个洞中arr[hole] = arr[right];hole = right;//接下来left寻找比temp大的(right位置为空)while (left < right && arr[left] right){return;}int keyi = Find(arr,left,right);//寻找基准值//左子树QuickSort(arr, left, keyi-1);QuickSort(arr, keyi + 1, right);}lomuto前后指针法：
创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边（和冒泡排序中的比较方法差不多，就是比较前（基准）后（数据）大小。在寻找比基准值小和基准值交换，然后把基准值移动，最前面的是试探指针，还有一个是用于把试探到比基准值小的数进行交换到） 
//lomuto前后指针法int Find(int* arr, int left, int right){int prev = left; int cur = prev + 1;int i = left;while (cur <= right){if (arr[cur] = right){return;}int keyi = Find(arr,left,right);//寻找基准值//左子树QuickSort(arr, left, keyi-1);QuickSort(arr, keyi + 1, right);}1. 时间复杂度： O ( nlogn ) 2. 空间复杂度： O ( logn ) 对于非递归时间复杂度：O(
)，而空间复杂度就变为o(1)
四、归并排序
4.1归并排序
归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divide and Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并（就是通过二分不断将无序变为一个数据，此时就是有序数据了，然后通过之前学到的合并两个有序序列，不断合并为有序）。 
递归版：
//归并排序void MergeSort(int* arr, int left, int right,int* tmp){//递归结束条件if (left >= right){return;}int mid = (left + right) / 2;MergeSort(arr, left, mid,tmp);MergeSort(arr, mid + 1, right,tmp);//合并有序int begin1 = left; int end1 = mid;int begin2 = mid + 1; int end2 = right;int index = left;//计数while (begin1 <= end1 && begin2 arr[begin2]){tmp[index++] = arr[begin2++];}else{tmp[index++] = arr[begin1++];}}//begin1 end1 还有没比较的数据while (begin1 <= end1){tmp[index++] = arr[begin1++];}//begin2 end2 还有没比较的while (begin2 <= end2){tmp[index++] = arr[begin2++];}//将tmp数组数据放入到arr中while (left <= right){arr[left]=tmp[left];left++;}}void test01(){int arr[] = { 10,6,7,1,3,9,4,2 };int size = sizeof(arr) / sizeof(arr[0]);int* newarr = malloc(sizeof(arr));if (newarr == NULL){return;}MergeSort(arr, 0, size - 1,newarr);//释放置空free(newarr);newarr = NULL;for (int i = 0; i < size; i++){printf(\"%d \", arr[i]);}}非递归版本 ：
void MergeSort(int *arr,int num){int* tmp = (int*)malloc(sizeof(int) * num);if (tmp == NULL){return;}int gap = 1;//一个区间元素个数while (gap < num){//寻找归并元素for (int i = 0;i = num)//没有右序列{break;}if (end2 >= num)//右序列不满gap个{end2 = num-1;}//偶数//归并while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}//begin1while (begin1 <= end1){tmp[index++] = arr[begin1++];}//begin2while (begin2 <= end2){tmp[index++] = arr[begin2++];}//放入原数组memcpy(arr + i, tmp + i, sizeof(int) * (end2-i+1));}gap *= 2;}free(tmp);tmp = NULL;}1. 时间复杂度： O ( nlogn) 2. 空间复杂度： O ( n )
五、计数排序
5.1计数排序
计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。 操作步骤： 1）统计相同元素出现次数 2）根据统计的结果将序列回收到原来的序列中 (这个计数排序就是通过记每个元素出现的个数放入一个数组中，这个数组的下标可以表示为排序数组中数据的元素，进而通过遍历记入出现元素个数的数组，遍历得到有序数组)。 
void CountSort(int* arr, int num){//寻找最值int min = arr[0]; int max = arr[0];for (int i = 0; i max){max = arr[i];}if (arr[i] < min){min = arr[i];}}//创造为max-min+1个空间用于存储arr出现元素个数int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror(\"calloc fail\");return;}//计数for (int i = 0; i < num; i++){count[arr[i]- min]++;}//排序int index = 0;for (int j = 0; j < range; j++){while (count[j]){arr[index++] = min+j;count[j]--;}}}1. 计数排序在数据范围集中时，效率很⾼，但是适⽤范围及场景有限(对于范围比较大的数据如1到1万中中间数据没有或者很少，效率会很慢)。 2. 时间复杂度： O ( N + range ) 3. 空间复杂度： O ( range )
六、排序复杂度和稳定性
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的（归根结底就是排序过程中遇到相同的元素时，看是否相对位置发生变化，如果第一个r[i]还在r[j]前面那就稳定的，反则不稳定）。
