在上一篇文章中我们介绍了队列的相关知识点及进行了专项的练习,在这一篇中我们将学习排序算法。
冒泡排序
冒泡排序是一种简单的排序算法。它重复地比较相邻的两个元素,并将它们按照顺序交换,从而将最大(或最小)元素 “浮” 到数组的末尾。这个过程类似于气泡在水中上浮的过程,因而得名 “冒泡排序”。
适用说明
冒泡排序适用于小规模的数组排序。由于其算法复杂度较高(平均时间复杂度为 O(n^2)),当排序规模较大时,性能会明显下降。因此,对于大规模数据集,更推荐使用其他高效的排序算法,如快速排序或归并排序。
冒泡排序的空间复杂度为O(1)
冒泡排序的比较次数恒为n*(n-1)/2
冒泡排序是一种稳定的排序算法,即具有相同值的元素在排序后的相对位置保持不变。
举个例子:对序列28 19 33 30 26 31使用冒泡排序法进行升序排序,进行第一趟冒泡排序后得到的序列为? 冒泡排序是两个两个比较,比如1和2比、2和3比 28>19 所以变为 19 28 33 30 26 31 28<33,所以不动 19 28 33 30 26 31 33>30 所以变为 19 28 30 33 26 31 一直冒泡排序,最终就能得到 19 28 30 26 31 33
本文给出C语言冒泡排序的范例:
#include <stdio.h> void bubblesort(int a[],int n)//冒泡排序 { for(int i=0;i<n-1;i++) { for(int j=0;j<n-i-1;j++) { if(a[j]>a[j+1]) { int t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } } void print(int a[],int n) { for(int i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); } int main() { int a[]={12,11,13,5,6}; print(a,5);//输出原数组 bubblesort(a,5); print(a,5); }
插入排序
插入排序(InsertionSort),一般也被称为直接插入排序。
对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而生成一个新的、记录数增 1 的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动。
适用说明
插入排序的平均时间复杂度也是 O(n^2),空间复杂度为常数阶 O(1),具体时间复杂度和数组的有序性也是有关联的。
插入排序中,当待排序数组是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较 N-1 次,时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的,此时插入排序执行的比较和交换次数为n*(n-1)/2,即最坏的情况是 O(n^2)。
插入排序算法是稳定的。
过程图示
假设前面 n-1(其中 n>=2)个数已经是排好顺序的,现将第 n 个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。
按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序。
从小到大的插入排序整个过程如图示:
第一轮: 从第二位置的 6 开始比较,比前面 7 小,交换位置。
**第二轮:**第三位置的 9 比前一位置的 7 大,无需交换位置。
**第三轮:**第四位置的 3 比前一位置的 9 小交换位置,依次往前比较。
**第四轮:**第五位置的 1 比前一位置的 9 小,交换位置,再依次往前比较。
依次比较多次后到最后一个元素。
本文给出C语言插入排序的范例:
#include <stdio.h> void insertsort(int a[],int n)//插入排序 { int i,j,key; for(int i=1;i<n;i++) { key=a[i]; j=i-1; while(j>=0&&a[j]>key) { a[j+1]=a[j]; j=j-1; } a[j+1]=key; } } void print(int a[],int n) { for(int i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); } int main() { int a[]={12,11,13,5,6}; print(a,5);//输出原数组 insertsort(a,5); print(a,5);//输出排序后的数组 }
希尔排序
希尔排序(Shell Sort)是插入排序的一种,它是针对直接插入排序算法的改进。
希尔排序又称缩小增量排序,因 DL.Shell 于 1959 年提出而得名。
它通过比较相距一定间隔的元素来进行,各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。
适用说明
希尔排序时间复杂度是 O(n^(1.3-2)),空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ,因此对中等大小规模表现良好,但对规模非常大的数据排序不是最优选择,总之比一般 O(n^2 ) 复杂度的算法快得多。
过程图示
希尔排序目的为了加快速度改进了插入排序,交换不相邻的元素对数组的局部进行排序,并最终用插入排序将局部有序的数组排序。
在此我们选择增量 gap=length/2,缩小增量以 gap = gap/2 的方式,用序列 {n/2,(n/2)/2…1} 来表示。
如图示例:
(1)初始增量第一趟 gap = length/2 = 4
(2)第二趟,增量缩小为 2
(3)第三趟,增量缩小为 1,得到最终排序结果
本文给出C语言希尔排序的范例:
#include <stdio.h> void shellsort(int a[],int n)//希尔排序 { for(int gap=n/2;gap>0;gap/=2) { for(int i=gap;i<n;i++) { int t=a[i]; int j; for(j=i;j>=gap&&a[j-gap]>t;j-=gap) { a[j]=a[j-gap]; } a[j]=t; } } } void print(int a[],int n) { for(int i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); } int main() { int a[]={12,11,13,5,6}; print(a,5);//输出原数组 shellsort(a,5); print(a,5); }
快速排序
快速排序采用的是分治思想,即在一个无序的序列中选取一个任意的基准元素pivot,利用pivot将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到将无序序列排列成有序序列。
其思想基本上可以总结为以下几个步骤:
1.选择一个基准值:从待排序的数据中选择一个基准值(pivot),通常选择第一个元素、最后一个元素或者中间的元素。
2.分割:将序列中比基准值小的元素移到基准值的左边,比基准值大的元素移到右边。这个过程称为分割操作。
3.递归排序:对基准值左右两边的子序列分别进行递归排序。即重复上述步骤,直到各个子序列的长度为1,排序完成。
4.合并结果:当所有递归调用结束后,整个序列就变成了有序的序列。
快速排序算法不稳定。
举例
有组记录的排序码为{46,79,56,38,40,84 },采用快速排序(以位于最左位置的对象为基准)得到的第一次划分结果为: A.{40,38,46,56,79,84} B.{38,46,56,79,40,84} C.{38,79,56,46,40,84} D.{38,46,79,56,40,84} 选A,解析: 46,79,56,38,40,84 l r 因为以46为基准,所以l不动,对r进行分析 84大于46,所以不用动 接着r--,对应40 46,79,56,38,40,84 l r 40小于46,所以将40替换46 40,79,56,38,——,84 l r 接着l++ 40,79,56,38,——,84 l r l对应79,大于40,所以79替换到r的地方 40,——,56,38,79,84 l r 接着r--,对应38 40,——,56,38,79,84 l r 38小于40,所以38替换到l的地方 40,38,56,——,79,84 l r 接着l++ 40,38,56,——,79,84 l r l对应56,大于40,所以56替换到r处 40,38,——,56,79,84 l r 接着r-- 此时l与r位置相同 所以不用替换,直接把基准值46填进去就行
快速排序的平均时间复杂度为O(nlogn),最好情况下为O(nlogn),最坏情况下为O(n^2),空间复杂度O(logn)
代码
#include <stdio.h> // 交换数组中两个元素的值 void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // 对数组进行划分操作 int partition(int arr[], int low, int high) { int pivot = arr[high]; // 选择数组最后一个元素作为基准值 int i = (low - 1); // 初始化较小元素的索引 for (int j = low; j <= high - 1; j++) { // 如果当前元素小于或等于基准值 if (arr[j] <= pivot) { i++; // 较小元素的索引加1 swap(&arr[i], &arr[j]); // 交换arr[i]和arr[j] } } swap(&arr[i + 1], &arr[high]); // 将基准值放到正确的位置上 return (i + 1); } // 快速排序函数 void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); // 对数组进行划分 quickSort(arr, low, pi - 1); // 递归排序划分的左半部分 quickSort(arr, pi + 1, high); // 递归排序划分的右半部分 } } // 测试快速排序算法 int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); printf("Sorted array: \n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
桶排序
桶排序是一种线性时间复杂度的排序算法,适用于元素服从均匀分布的情况。
它的基本思想是将待排序的元素划分为若干个相同大小的区间(桶)。然后对每个桶内的元素进行排序,最后按照桶的顺序依次将各个桶中的元素合并起来。
首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中,那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值mx和最小值mn;
根据mx和mn确定每个桶所装的数据的范围 size,有
size = (mx - mn) / n + 1,n为数据的个数,需要保证至少有一个桶,故而需要加个1;
求得了size即知道了每个桶所装数据的范围,还需要计算出所需的桶的个数cnt,有
cnt = (mx - mn) / size + 1,需要保证每个桶至少要能装1个数,故而需要加个1;
求得了size和cnt后,即可知第一个桶装的数据范围为 [mn, mn + size),第二个桶为 [mn + size, mn + 2 * size),…,以此类推
因此步骤2中需要再扫描一遍数组,将待排序的各个数放进对应的桶中。
对各个桶中的数据进行排序,可以使用其他的排序算法排序,例如快速排序;也可以递归使用桶排序进行排序;
将各个桶中排好序的数据依次输出,最后得到的数据即为最终有序。
桶排序的时间复杂度为O(n+k),其中k是桶的数量。相当于桶排序的时间复杂度为O(n)
例如,待排序的数为:3, 6, 9, 1
1)求得 mx = 9,mn = 1,n = 4
size = (9 - 1) / n + 1 = 3
cnt = (mx - mn) / size + 1 = 3
2)由上面的步骤可知,共3个桶,每个桶能放3个数,第一个桶数的范围为 [1, 4),第二个[4, 7),第三个[7, 10)
扫描一遍待排序的数,将各个数放到其对应的桶中,放完后如下图所示:
3)对各个桶中的数进行排序,得到如下图所示:
4)依次输出各个排好序的桶中的数据,即为:1, 3, 6, 9
可见,最终得到了有序的排列。
代码
#include <stdio.h> #include <stdlib.h> // 桶排序函数 void bucketSort(int arr[], int n) { // 计算数组中最大值和最小值 int max_val = arr[0]; int min_val = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > max_val) { max_val = arr[i]; } if (arr[i] < min_val) { min_val = arr[i]; } } // 根据最大值和最小值计算桶的数量 int bucket_num = (max_val - min_val) / n + 1; int** buckets = (int**)malloc(bucket_num * sizeof(int*)); for (int i = 0; i < bucket_num; i++) { buckets[i] = (int*)malloc(n * sizeof(int)); } // 将数组中的元素分配到对应的桶中 for (int i = 0; i < n; i++) { int index = (arr[i] - min_val) / n; buckets[index][i] = arr[i]; } // 对每个桶中的元素进行排序 for (int i = 0; i < bucket_num; i++) { int* bucket_arr = buckets[i]; for (int j = 0; j < n; j++) { for (int k = 0; k < n - j - 1; k++) { if (bucket_arr[k] > bucket_arr[k + 1]) { int temp = bucket_arr[k]; bucket_arr[k] = bucket_arr[k + 1]; bucket_arr[k + 1] = temp; } } } } // 将所有桶中的元素按顺序合并起来 int index = 0; for (int i = 0; i < bucket_num; i++) { int* bucket_arr = buckets[i]; for (int j = 0; j < n; j++) { if (bucket_arr[j] != 0) { arr[index] = bucket_arr[j]; index++; } } } // 释放桶内存空间 for (int i = 0; i < bucket_num; i++) { free(buckets[i]); } free(buckets); } // 测试桶排序算法 int main() { int arr[] = {5, 2, 9, 4, 7, 6, 1, 3, 8}; int n = sizeof(arr) / sizeof(arr[0]); bucketSort(arr, n); printf("Sorted array: \n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
这篇文章中我们介绍了冒泡排序、插入排序、希尔排序、快速排序及桶排序,在下一篇文章中我们将介绍基数排序、计数排序等算法。