八大排序算法

八大排序算法

排序算法的稳定性

稳定性：在排序过程中，相等元素的相对顺序在排序前后保持不变。
也就是说，若在待排序序列里有两个元素a和b，它们的值相等，
且在排序前a位于b之前，那么排序后a依旧处于b之前。

比较排序

比较排序顾名思义就是通过元素之间的大小比较来排序的方法。

插入排序

插入排序：将待排序元素插入到有序序列中，从而得到一个新的有序序列。

实际生活中，我们玩扑克牌时就用到了插入排序的思想。

直接插入排序

用 end 记录有序序列的最后一个位置，tmp 保存待排序序列中的第一个元素，
结合插入排序的思想来排序。

void InsertSort(int* arr, int n)
{for(int i = 0; i < n - 1; i++){//i < n - 1是因为当end = n - 2时就是在将最后一个待排序元素插入到有序序列中int end = i;//end用来记录有序序列的最后一个位置int tmp = arr[end + 1];//tmp保存待排序序列中的第一个元素//找待排元素应该插入的位置//当end<0时，说明待排元素比有序序列的最小元素还要小while(end >= 0){if(arr[end] > tmp)//说明待排元素的位置在有序序列中该元素的前面{//把有序序列中该元素向后移，给待排元素的插入腾出位置arr[end + 1] = arr[end];//找有序序列中的前一个元素end--;}else//说明已经找到了待排元素应该插入的位置，跳出循环break;}//将待排元素插入到有序序列中arr[end + 1] = tmp;}
}

下面是直接插入排序图解

直接插入排序总结

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O（N^2）
3. 空间复杂度：O（1）
4. 稳定性：稳定

希尔排序

希尔排序（Shell Sort）是插入排序的一种改进版本，也被叫做缩小增量排序。
它的基本思路是通过一个初始增量gap（通常是gap = n / 3 + 1）将待排序列分
割成若干个子序列，分别对这些子序列进行直接插入排序；然后通过gap = gap / 3 + 1
使增量gap逐渐减小，子序列的长度逐渐增加，整个序列会变得越来越接近有序，
当增量gap减至1时，整个序列就被合并成一个，再进行一次直接插入排序，排序完成。

下面是希尔排序图解

void ShellSort(int* arr, int n)
{int gap = n;while(gap > 1){gap = gap / 3 + 1;//下面是直接插入排序的代码，只不过有小小的改变//因为直接插入排序每次移动1步，而希尔排序每次移动gap步for(int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while(end >= 0){if(arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;			}elsebreak;}arr[end + gap] = tmp;}}
}

希尔排序总结

1. 希尔排序是对直接插入排序的优化。
2. 当gap>1时都是预排序，目的是让数组更接近有序。当gap == 1时，
   数组已经很接近有序了，再进行直接插入排序会很快。
3. 时间复杂度：O(N^1.3)
4. 空间复杂度：O(1)
5. 稳定性：不稳定

希尔排序的时间复杂度计算

外层循环：while(gap > 1)
时间复杂度可以直接给出为：O(logN)
内层循环：
忽略+1的影响，gap = gap / 3

希尔排序时间复杂度不好计算，因为gap 的取值很多，导致很难去计算，因此很多书中给出的
希尔排序的时间复杂度都不固定。《数据结构(C语⾔版)》—严蔚敏书中给出的时间复杂度为：

选择排序

选择排序的基本思想：每一次从待排序列中选出最小（或最大）的一个元素，
存放在序列的起始位置，直到待排元素全部排完。

直接选择排序

1. 设begin和end分别为待排序列的首尾位置，在待排序列arr[begin]~arr[end]中找最大和最小元素。
2. 若最小和最大元素不是待排序列的首尾元素，就让最小和最大元素与待排序列的首尾元素交换。
3. begin++，end–为下一次选择排序做准备，重复上述步骤。

//直接选择排序
void SelectSort(int* arr, int n)
{//记录待排序列的首尾位置int begin = 0;int end = n - 1;//如果begin >= end说明序列已经排好序while (begin < end){//假设待排序列中最大和最小元素的位置都在首位置int maxi = begin, mini = begin;//找待排序列中最大和最小元素的位置for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[maxi])maxi = i;if (arr[i] < arr[mini])mini = i;}//让最小元素与首元素交换，最大元素与尾元素交换//如果最大元素就是首元素的话，第一次交换会把最//大元素交换到mini位置处，所以要让maxi = miniif (maxi == begin)maxi = mini;Swap(&arr[begin], &arr[mini]);Swap(&arr[end], &arr[maxi]);//为下一次选择排序做准备begin++;end--;}
}

下面是直接选择排序的图解

直接选择排序总结：
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定

堆排序

堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法，其基本思想是先将
待排序的序列构建成一个最大堆（对于升序排序），然后将堆顶元素（最大值）与堆的
最后一个元素交换，接着将剩余的元素重新调整为最大堆，重复这个过程，直到整个序列有序。

//向下调整算法 O(logN)
void AdjustDown(int* arr, int n, int parent)
{int child = parent * 2 + 1;//左孩子while (child < n){//小堆：<//大堆：>if (child + 1 < n && arr[child + 1] > arr[child])child++;//小堆：<//大堆：>if (arr[parent] > arr[child])break;//<=就交换了，所以稳定性：不稳定Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}
}//向上调整算法 O(logN)
void AdjustUp(int* arr, int child)
{int parent = (child - 1) / 2;while (parent >= 0){//大堆：>//小堆：<if (arr[parent] > arr[child])break;Swap(&arr[parent], &arr[child]);child = parent;parent = (child - 1) / 2;}
}//堆排序 
void HeapSort(int* arr, int n)
{//升序 - 建大堆//降序 - 建小堆//建堆 - 向下调整法 O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}建堆 - 向上调整法 O(NlogN)//for (int i = 1; i < n; i++)//{//	AdjustUp(arr, i);//}//堆排序 O(NlogN)int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}
}

堆排序总结：
时间复杂度：O(NlogN)
空间复杂度：O(1)
稳定性：不稳定

交换排序

交换排序基本思想：通过比较序列中元素的大小，根据比较结果
对元素位置进行交换操作，逐步让序列达到有序状态。

冒泡排序

void BubbleSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int flag = 0;for (int j = 0; j < n - 1 - i; j++){if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);flag = 1;}}if (flag == 0)break;}
}

冒泡排序总结：
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

快速排序

快速排序（Quick Sort）是一种高效的排序算法，它采用分治法（Divide and Conquer）策略。
基本思想是从待排序序列中挑选一个元素作为基准（pivot），然后将序列划分为两部分，
使得左边部分的所有元素都小于等于基准，右边部分的所有元素都大于等于基准，接着
分别对左右两部分递归地进行快速排序，最终得到一个有序序列。

递归

void QuickSort(int* arr, int left, int right)
{//递归出口if(left >= right)return;//接收一个基准值的位置int pi = _QuickSort(arr, left, right);//将序列划分成两部分：[left, pi-1] [pi+1, right]//递归左右序列QuickSort(arr, left, pi - 1);QuickSort(arr, pi + 1, right);
}

_QuickSort有以下三个写法

hoare版本

hoare版本的基本思路

1. 假定首元素为基准值，让left++
2. 在[left,right]中，先从右向左找不大于基准值的值，再从左向右找不小于基准值的值，
   找到后，进行交换，再让left++和right–。
3. 循环结束，交换基准值和right指向的值,使得左边部分的所有元素都小于等于基准值，
   右边部分的所有元素都大于等于基准值。

int _QuickSort(int* arr, int left, int right)
{//假设首元素是基准值，记录其位置int pi = left;//让left指向下一个元素的位置left++;while (left <= right){//从右向左找不大于基准值的值while (left <= right && arr[right] > arr[pi])right--;//从左向右找不小于基准值的值while (left <= right && arr[left] < arr[pi])left++;//找到后，进行交换，更新left和rightif (left <= right)Swap(&arr[left++], &arr[right--]);}//交换基准值和right指向的值//使得左边部分的所有元素都小于等于基准，右边部分的所有元素都大于等于基准Swap(&arr[pi], &arr[right]);//返回基准值的下标return right;
}

问题一：为什么循环的条件是 left<=right ?

问题二：为什么跳出循环时，交换基准值和right指向的值？
当left>right时，即right走到left的左侧，而left扫描过的数据均不大于基准值，
因此right指向的数据一定不大于基准值,且是序列中最右边的不大于基准值的元素。

挖坑法

挖坑法的基本思路

1. 假设首元素是基准值，并保存基准值，“坑”的位置就是基准值的位置。
2. 从右向左找比基准值小的值，将小于基准值的元素填入坑，保存新的“坑”的位置，
   丛左向右找比基准值大的值，将大于基准值的元素填入坑，保存新的“坑”的位置。
3. 当left==right时，跳出循环，此时left和right都指向坑的位置，将基准值放入该位置。

int _QuickSort(int* arr, int left, int right)
{//假设首元素是基准值，并保存基准值int pivot = arr[left];//“坑”的位置就是基准值的位置int hole = left;while (left < right){//从右向左找比基准值小的值while (left < right && arr[right] >= pivot)right--;//将小于基准值的元素填入坑if (left < right){arr[hole] = arr[right];//保存新的“坑”的位置hole = right;}//丛左向右找比基准值大的值while (left < right && arr[left] <= pivot)left++;//将大于基准值的元素填入坑if (left < right){arr[hole] = arr[left];//保存新的“坑”的位置hole = left;}}//当left==right时，跳出循环，此时left和right都指向坑的位置//将基准值放入该位置，使得左边部分的所有元素都小于等于基准，//右边部分的所有元素都大于等于基准arr[hole] = pivot;//返回基准值的位置return hole;
}

lomuto前后指针

lomuto前后指针的基本思路

1. 假设首元素是基准值，记录其位置
2. 创建前后指针prev和cur
3. 从左向右找比基准值小的进行交换，使得小的都在基准值左边
4. 交换基准值和prev指向的值

int _QuickSort(int* arr, int left, int right)
{//假设首元素是基准值，记录其位置int pi = left;//创建前后指针prev和curint prev = left, cur = left + 1;//只有cur遍历完数组才会出循环while (cur <= right){//从左向右找比基准值小的进行交换，使得小的都在基准值左边if (arr[cur] < arr[pi] && ++prev != cur)Swap(&arr[cur], &arr[prev]);cur++;}//交换基准值和prev指向的值//使得左边部分的所有元素都小于基准，右边部分的所有元素都大于等于基准Swap(&arr[pi], &arr[prev]);//返回基准值的下标return prev;
}

快速排序总结：

1. 时间复杂度：O(NlogN)
2. 空间复杂度：O(logN)
3. 稳定性：不稳定

非递归

非递归版本的快速排序需要借助数据结构：栈

void QuickSortNonR(int* arr, int left, int right)
{//借助数据结构 - 栈//创建栈ST st;//初始化STInit(&st);//让首尾元素下标入栈，注意入栈和出栈顺序STPush(&st, right);STPush(&st, left);//栈非空进循环while (STSize(&st)){//保存首尾元素下标int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);//利用lomuto前后指针思想int pi = begin;int prev = begin, cur = begin + 1;while (cur <= end){if (arr[cur] < arr[pi] && ++prev != cur)Swap(&arr[cur], &arr[prev]);cur++;}Swap(&arr[prev], &arr[pi]);//更新基准值的位置pi = prev;//为下一次排序排序做准备//[begin, pi - 1] pi [pi + 1, end]if (begin < pi - 1){STPush(&st, pi - 1);STPush(&st, begin);}if (pi + 1 < end){STPush(&st, end);STPush(&st, pi + 1);}}//销毁STDestroy(&st);
}

归并排序

归并排序（Merge Sort）是一种采用分治法（Divide and Conquer）的经典排序算法。
它的基本思想是将一个大问题分解为多个小问题，分别解决这些小问题，最后将小问题
的解合并起来得到原问题的解。具体来说，归并排序将一个数组分成两个子数组，分别
对这两个子数组进行排序，然后将排好序的子数组合并成一个最终的有序数组。

下面是归并排序图解

void _MergeSort(int* arr, int left, int right, int* tmp)
{//1.分解//递归出口if (left >= right)return;int mid = left + (right - left) / 2;//递归分解左右序列：[left, mid] [mid+1, right]_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);//2.合并//合并左右两个有序序列//为了防止合并时覆盖有效数据，需要一个临时数组tmpint begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;//[begin1, end1] [begin2, end2]int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])tmp[index++] = arr[begin1++];elsetmp[index++] = arr[begin2++];}while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//3.将tmp中有序的数据导入到原数组中//[left, right]for (int i = left; i <= right; i++){arr[i] = tmp[i];}
}void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(1);}_MergeSort(arr, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

归并排序总结：

1. 时间复杂度：O(NlogN)
2. 空间复杂度：O(N)
3. 稳定性：稳定

排序性能对比

void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}

非比较排序

非比较排序不需要通过元素之间的大小比较来排序。

计数排序

计数排序又称为鸽巢原理，其核心思想是通过统计每个元素在序列中出现的次数，
进而确定每个元素在排序后序列中的位置。该算法适用于整数序列，且当待排序元素
的值范围较小时，计数排序的效率较高。

void CountSort(int* arr, int n)
{//找arr数组中的最大值和最小值，用来确定申请的新数组的空间大小int max = arr[0], min = arr[0];for (int i = 1; i < n; i++){if (arr[i] > max)max = arr[i];if (arr[i] < min)min = arr[i];}//所以新数组的大小为rangeint range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail");return;}memset(count, 0, range * sizeof(int));//初始化为0//统计原数组中每个元素出现的次数for (int i = 0; i < n; i++){count[arr[i] - min]++;}//排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[j++] = i + min;}}
}

计数排序总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(N + range)
3. 空间复杂度：O(range)
4. 稳定性：稳定

比较排序算法总结