十大排序:插入/希尔/选择/堆/冒泡/快速/归并/计数/基数/桶排序 汇总(C语言)
目录
- 前言
- 非线性时间比较类
- 插入排序
- (1) 直接插入排序
- (2) 希尔排序
- 选择排序
- (3) 选择排序优化版
- (4) 堆排序
- 交换排序
- (5) 冒泡排序
- (6) 快速排序
- hoare版本
- 挖坑版
- 前后指针版
- 非递归版
- 归并排序
- (7) 归并排序
- 递归版
- 非递归版
- 线性时间比较类
- (8) 计数排序
- 基数排序与桶排序
- 总结
前言
在计算机科学中，排序算法是一种重要的算法类别，用于将一组元素按照特定的顺序进行排列。排序算法的应用非常广泛，从日常生活中的字典排序到大规模数据处理中的并行排序，都离不开排序算法的支持。
本博客将介绍十种常见的排序算法，包括冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序、希尔排序、计数排序、(桶排序和基数排序,稍作了解)。每种算法都会详细讲解其原理、时间复杂度、空间复杂度等关键知识点，以及对比不同算法的优劣势。
通过学习这十种常见的排序算法，读者将能够深入理解算法设计和分析的思想，提升自己的编程能力和解决问题的能力。无论是面试、竞赛还是实际项目开发，掌握好排序算法都是非常有帮助的。
希望本博客能对读者有所帮助，让大家能够更好地应用排序算法解决实际问题。如果对于排序算法还有疑问或者建议，欢迎留言交流。让我们一起进入排序算法的世界，开拓自己的算法视野！
博客主页: 酷酷学!!! 感谢关注! 您的支持是我的极大动力
非线性时间比较类
插入排序
更多详情点击: 博客链接
(1) 直接插入排序
时间复杂度：O(N^2)
最坏：逆序
最好：顺序有序，O(N)
// 插入排序
void InsertSort(int* a, int n)
{//默认升序for (int i = 0; i < n - 1; i++)//最后一次将最后一个元素记录下来,就不要循环到n{//int end = 0;//先写内层循环,定义下标end,假设第一个元素有序int end = i;//进行改写,假设前i个位置有序int tmp = a[end + 1];//记录后一个位置的元素while (end >= 0)//从end下标位置开始依次比较{if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;//此时a[end+1]位置就是需要插入的位置,跳出循环再插入是为了防止end=0时,//循环无法进入,此时无法进行赋值}
}
(2) 希尔排序
希尔排序是一种排序算法，属于插入排序的一种改进版本。它通过将数组分成若干个子序列，对每个子序列进行插入排序，然后逐步减少子序列的长度，最终完成排序。希尔排序的核心思想是将数组按照一定间隔分组，然后对每组进行插入排序。这样可以减少比较和交换的次数，从而提高排序的效率。
时间复杂度: O(N ^ 1.3)
// 希尔排序
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//每次缩小三倍效率是比较高的,+1是为了防止gap==0循环进不来for (int i = 0; i < n - gap; i++)//对每个组进行排序{int end = i;int tmp = a[end + gap];//保存某组数据的后一个数据while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}
选择排序
更多详情点击: 博客链接
(3) 选择排序优化版
这里直接给出优化版代码, 采用双指针法, 同时选出到最大与最小的元素位置.
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}// 选择排序
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){//双指针法int min = begin, max = begin;//假设a[begin]为最大和最小值for (int i = begin + 1; i <= end; i++)//选出最大最小元素,保存下标{if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}Swap(&a[min], &a[begin]);if (max == begin)//如果begin位置还是max,最大值就被交换到了min位置,故需要判断{max = min;}Swap(&a[max], &a[end]);begin++;end--;}
}
(4) 堆排序
堆排序（Heap Sort）是一种效率较高的排序算法，它的基本思想是将待排序的序列构建成一个大顶堆，然后将堆顶元素与末尾元素交换，再重新调整堆，直到整个序列有序
//向上调整算法,假设建小堆
//比如插入一个新元素,还需要保证是堆的结构就需要进行调整
void AdjustUP(int* a, int child)
{//首先需要找到它的父亲结点int parent = (child - 1) / 2;//不管是左孩子还是右孩子都能算出父节点while (child > 0)//这里用child进行条件判断,用parent<=0会进入死循环,然后巧合结束,不规范{if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;//让父节点等于孩子结点,继续找父节点parent = (child - 1) / 2;}else{break;}}
}
// 堆排序
//如果要删除堆顶元素,不可以直接删除,这样会破坏堆的结构,应该先把堆顶数据与最后一个数据交换
//然后删除最后一个数据,此时再将堆顶元素进行向下调整,直到满足堆的性质,调整要保证左右子树也都是堆
void AdjustDwon(int* a, int n, int root)
{//排升序,建大堆//先假设左孩子大int child = root * 2 + 1;while (child < n)//到最后一个孩子就结束{//右孩子存在且比左孩子大if (child + 1 < n && a[child + 1] > a[child]){child = child + 1;}if (a[child] > a[root]){Swap(&a[child], &a[root]);root = child;child = root * 2 + 1;}else{break;}}
}
//这里用向下调整建堆,效率更高
void HeapSort(int* a, int n)
{//从最后一个非叶子结点开始建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDwon(a, n, i);}//建堆完毕,将第一个元素与最后一个元素交换,再次调整int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDwon(a, end, 0);//此时调整最后一个元素之前的数组end--;}
}
交换排序
更多详情点击: 博客链接
(5) 冒泡排序
冒泡排序是一种简单的交换排序算法，它通过不断地比较相邻的元素，如果顺序不对就交换它们的位置，直到整个列表或数组排好序。
快速排序是一种高效的交换排序算法，它通过选择一个基准元素，将小于基准元素的元素放在它的左边，大于基准元素的元素放在它的右边，然后再对左右两部分进行递归调用快速排序，直到整个列表或数组排好序。
交换排序的时间复杂度通常是O(n^2)，但在最好情况下，快速排序的时间复杂度可以达到O(nlogn)
//冒泡排序
void BubbleSort(int* a, int n)
{//先写内层循环//先找出最大的for (int i = 0; i < n - 1 ; i++){int flag = 1;//两两比较,先找最大的,然后找次大的for (int j = 0; j < n - 1 - i; j++)//i代表找到了几个最大的{if (a[j] > a[j + 1]){flag = 0;Swap(&a[j], &a[j + 1]);}}if (flag == 1)//如果flag==1说明没有进行交换则说明已经有序了break;}
}
(6) 快速排序
hoare版本
int GetMidi(int* a, int left, int right)
{int midi = (right - left) / 2;if (a[left] < a[midi]){if (a[midi] < a[right]){return midi;}else if (a[left] < a[right]){return right;}else{return left;}}else//a[left] > a[midi]{if (a[left] < a[right]){return left;}else if (a[midi] > a[right]){return midi;}else{return right;}}
}// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{//三数取中,取中等的值作为基准值int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left, end = right;while (begin < end){//要保证keyi的值小于相遇位置,所以end先走while (begin < end && a[end] >= a[keyi]){end--;}while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[begin], &a[keyi]);//相遇位置与keyi交换此时这个位置就排好了return begin;
}
为了方便, 我们单独将hoare版本写为函数PartSort1,需要使用的时候直接调用
// 快速排序递归实现
void QuickSort(int* a, int left, int right)
{if (left >= right){return;}if ((right - left + 1) < 10){InsertSort(a + left, right - left + 1);}//int keyi = left;//选取基准值//int begin = left, end = right;//begin找找大,end找小,然后交换//小区间优化,优化递归//if ((right - left + 1) < 10)//{// InsertSort(a + left,right - left + 1);//}//else//{// //三数取中,取中等的值作为基准值// int midi = GetMidi(a, left, right);// Swap(&a[left], &a[midi]);// int keyi = left;// int begin = left, end = right;// while (begin < end)// {// //要保证keyi的值小于相遇位置,所以end先走// while (begin < end && a[end] >= a[keyi])// {// end--;// }// while (begin < end && a[begin] <= a[keyi])// {// begin++;// }// Swap(&a[begin], &a[end]);// }// Swap(&a[begin], &a[keyi]);//相遇位置与keyi交换此时这个位置就排好了// keyi = begin;// QuickSort(a, left, keyi - 1);// QuickSort(a, keyi + 1, right);//}//int keyi = PartSort1(a, left, right);//int keyi = PartSort2(a, left, right);int keyi = PartSort3(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}
挖坑版
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{//三数取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left, end = right;//先挖个坑,保存a[keyi]的值int tmp = a[keyi];while (begin < end){//让对面先走,找小while (begin < end && a[end] >= a[keyi]){end--;}a[keyi] = a[end];keyi = end;while (begin < end && a[begin] <= a[keyi]){begin++;}a[keyi] = a[begin];keyi = begin;}//相遇之后把tmp填坑a[keyi] = tmp;return keyi;
}
前后指针版
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{//三数取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;//定义前后指针,这样不需要考虑是begin先走还是end先走//初始prev在前,cur在后一个位置,如果cur小于keyi则与++prev进行交换int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)//如果在同一个位置就不需要交换{Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[prev], &a[keyi]);return prev;
}
非递归版
可以使用队列进行存储区间
//非递归版
#include"stack.h"
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort1(a, begin, end);//[begin,keyi-1] keyi [keyi+1,end]//先压入右区间if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}Destroy(&st);
}归并排序
更多详情点击: 博客链接
归并排序是一种经典的排序算法，它基于分治的思想。
归并排序的时间复杂度是O(nlogn)，其中n是待排序数组的元素个数。
归并排序是一种稳定的排序算法，适用于各种数据规模。它的主要缺点是需要额外的空间来存储临时数组。
(7) 归并排序
递归版
void _MergeSort(int* a, int* tmp, int begin,int end)//传递区间递归调用
{if (begin >= end){return;}int mid = (begin + end) / 2;_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int j = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}// 归并排序递归实现
void MergeSort(int* a, int n)
{int* tmp = malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}非递归版
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1; //11归并while (gap < n){for (int i = 0; i < n; i += gap*2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int j = i;if (begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tmp);tmp = NULL;
}
线性时间比较类
(8) 计数排序
时间复杂度:O(N+range)
只适合整数/适合范围集中
空间范围度：O(range)
// 计数排序
void CountSort(int* a, int n)
{//找数的范围int max = a[0], min = a[0];for (int i = 1; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1;//需要开辟的空间大小int* count = (int*)calloc(range, sizeof(int));//malloc需要手动初始化,而calloc默认初始化为0if (count == NULL){perror("calloc fail");return;}//开始计数for (int i = 0; i < n; i++){count[a[i] - min]++;}//开始排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}free(count);
}
基数排序与桶排序
这两种排序只需要稍作了解, 面试一般没有.
基数排序是一种非比较排序算法，它根据数字的位数进行排序。基数排序的基本思想是将整数按照个位、十位、百位等位数进行排序，最终得到有序的结果。
基数排序的步骤如下：
首先找到待排序数组中的最大值，并确定其位数，记为max_digits。
创建10个桶，分别代表数字0-9。
从个位开始，将所有数字放入对应的桶中。
依次取出桶中的数字，并按照顺序放回原数组中。
重复步骤3和步骤4，直到按照最高位排序完毕。
基数排序的时间复杂度为O(n*k)，其中n是待排序数组的长度，k是最大位数。需要注意的是，基数排序只适用于整数排序，且要求待排序数字必须是非负数。
桶排序是一种排序算法，它将数据按照一定的范围划分为多个桶，然后对每个桶中的数据进行排序，最后将每个桶中的元素按照顺序依次取出来得到有序序列。
具体的桶排序算法如下：
创建一个定量的空桶数组。
遍历输入数据，并将每个元素放入对应的桶中。
对每个非空桶中的元素进行排序。
依次将非空桶中的元素取出，并放入输出序列。
桶排序的时间复杂度取决于对每个桶中的元素进行排序的算法，通常采用的是快速排序或插入排序，所以整体的时间复杂度为O(n+k)，其中n为待排序序列的长度，k为桶的数量。
桶排序适用于数据分布较均匀的情况，当数据分布不均匀时，不同的桶中的数据量差别较大，可能会导致某些桶中的数据在排序后仍然不是有序的，因此对于不同的数据分布情况，桶的数量和每个桶的容量需要适当调整。
总结
稳定性 :三稳四不稳
稳定性指的是, 相同的值,其相对位置排序后保持不变,作用一般在排列结构体数据时,比如高考总分排列,但是总分相同,就按照语文成绩高低排列, 此时可以使用稳定排序, 先排语文成绩,在排总成绩.
计数排序,基数排序和桶排序因为排列数据具有局限性,所以这里不探讨其稳定性
选择排序为什么不是稳定的?
比如下列情况
{ 6 , 1 , 1} 这种情况将第二个1换到前面, 相对位置不变
{ 6, 6, 1}但是这种情况相同的6却因为选择发生了变化, 所以是不稳定的.
为什么快速排序具有空间消耗?
因为递归会创建栈帧空间.
冒泡排序:
比较相邻的元素，如果前一个比后一个大，则交换位置，直到将最大的元素移到最后。
时间复杂度：平均O(n^ 2)，最好情况O(n)，最坏情况O(n^2)。
选择排序:
每次从未排序的元素中选择最小的元素，放到已排序的末尾。
时间复杂度：平均O(n^ 2)，最好情况O(n^2)，最坏情况O(n ^2)。
插入排序:
将未排序的元素逐个插入到已排序的序列中的正确位置。
时间复杂度：平均O(n^ 2)，最好情况O(n)，最坏情况O(n^2)。
希尔排序:
根据间隔将序列划分为多个子序列，对子序列进行插入排序，然后缩小间隔直至最后一次插入排序。
时间复杂度：平均O(n log n)，最好情况O(n log^ 2 n)，最坏情况O(n^2)。
归并排序:
将序列递归地拆分成两个子序列，然后将两个有序子序列合并为一个有序序列。
时间复杂度：平均O(n log n)，最好情况O(n log n)，最坏情况O(n log n)。
快速排序:
选择一个基准元素，将序列分为两部分，小于基准的放在左边，大于基准的放在右边，然后递归地对两个部分进行快速排序。
时间复杂度：平均O(n log n)，最好情况O(n log n)，最坏情况O(n^2)。
堆排序:
将序列构建成一个最大堆，然后不断将堆顶元素与最后一个元素交换，并重新调整堆，直到所有元素都有序。
时间复杂度：平均O(n log n)，最好情况O(n log n)，最坏情况O(n log n)。
计数排序:
统计每个元素的出现次数，然后根据统计结果将元素放回原数组。
时间复杂度：平均O(n+k)，最好情况O(n+k)，最坏情况O(n+k)。
桶排序:
将元素分到不同的桶中，然后对每个桶进行排序，最后按顺序将元素取出。
时间复杂度：平均O(n+k)，最好情况O(n)，最坏情况O(n^2)。
基数排序:
根据元素的位数依次进行排序，从最低位到最高位。
时间复杂度：平均O(nk)，最好情况O(nk)，最坏情况O(n*k)。
完