您的位置:首页 > 数据 >
全球要闻:各种常见排序算法实现 常见排序算法汇总
来源:CSDN 2023-02-13 14:51:36

各种常见排序算法实现

排序算法算是最为简单经典的算法问题了,因此从这个开始学习记录,以加深印象。


(资料图)

其中常见的排序算法有:

选择排序冒泡排序插入排序合并排序快速排序堆排序

以上排序算法一定无法罗列全部排序算法的大家族,但是暂且讨论以上的算法。

选择排序和冒泡排序属于蛮力解决问题的表现; 插入排序则使用减治法; 合并排序和快速排序使用分治法; 堆排序使用变治法。

选择排序

蛮力法去解决排序问题没有那么多弯弯道,选择排序的思路:

n个元素,先找到最小的元素,然后将它交换到它该在的位置,对于升序来说即第一个位置,然后第一个元素就是有序元素了,随后再将从剩下的n-1个寻找最小的元素,放到第二个位置上,以此类推,交换n-1次就可以得到一个有序的集合了。

实现代码

int ChooseSort(arr* a) {//使用选择排序//输入:无序元素列表//输出:成功返回1,失败返回0for (int i = 0; i < a->length - 1; i++) {int min = i;for (int j = i; j < a->length; j++) {if (a->ite[min] > a->ite[j]) {min = j;}}if (!Swap(a, i, min)) {return 0;}}return 1;}

冒泡排序

冒泡排序很形象,过程也和冒泡一样,思路:

从第一个元素开始,比较相邻元素,若是有序,则不变,若是无序,则交换相邻元素,这样做的结果就是会将最大的元素给“顶”到最后一个位置,接着将上述过程在前n-1个元素中重复。以此类推,最后就会得到一个有序的集合。

代码实现:

int BubbleSort(arr * a){//使用冒泡排序得到有序列表//输入:无序元素的列表//输出:成功返回1,失败返回0for (int i = a->length; i > 0; i--) {for (int j = 0; j < i-1; j++) {if (a->ite[j] > a->ite[j + 1]) {if (!Swap(a, j, j + 1)) return 0;}}}return 1;}

插入排序

记得第一次看到插入排序,书上是拿扑克牌举例的,思路:

我们先认为列表的第一个元素是有序的,那么拿起第二个元素,寻找在前面第一个元素的合适的位置,插进去,现在有序的集合元素就变成两个了。以此类推,第三个找到合适的位置插入,一直到第n个元素,这样,就得到了有序元素的集合。

代码实现:

int InserSort(arr * a){//使用插入排序//输入:无序元素的列表//输出:返回1for (int i = 1; i < a->length; i++) {for (int j = 0; j < i; j++) {if (a->ite[j] >= a->ite[i]) {int temp = a->ite[i];for (int k = i - 1; k >= j; k--)a->ite[k + 1] = a->ite[k];a->ite[j] = temp;}}}return 1;}

合并排序

合并排序是使用递归的思路来做的,也即上文提到的分治法。思路:

将其中每一个元素都看作为有序的集合,虽然每个集合只有一个元素,然后将两个有序集合合并成一个,依次合并,最终就生成了最后的有序集合。

代码实现:

int MergeSort(arr * a){//使用合并排序//输入:无序元素列表//输出:成功返回1if (a->length > 1) {arr *a1 = Cut(a, 0, a->length / 2 - 1);arr *a2 = Cut(a, (a->length / 2), a->length - 1);MergeSort(a1);MergeSort(a2);arr* b = Merge(a1, a2);for (int i = 0; i < b->length; i++) {a->ite[i] = b->ite[i];}a->length = b->length;free(a1); free(a2); free(b);}return 1;}

这是上述代码中Merge函数,即合并有序集合的函数:

arr * Merge(arr * a1, arr * a2){//合并过程,将两个有序列表合并成一个有序列表,并释放这两个有序列表内存//输入:两个有序列表//输出:一个有序列表arr *a = (arr*)malloc(sizeof(arr));a->length = 0;int i, j, k;for (i = 0, j = 0, k = 0; i < a1->length && j < a2->length; k++) {if (a1->ite[i] > a2->ite[j]) {a->ite[k] = a2->ite[j];j++;}else{a->ite[k] = a1->ite[i];i++;}a->length++;}if (i == a1->length) {for (; j < a2->length; j++, k++) {a->ite[k] = a2->ite[j];a->length++;}}else{for (; i < a1->length; i++, k++) {a->ite[k] = a1->ite[i];a->length++;}}return a;}

快速排序

快速排序与前面的合并排序一样,也用到了递归的思想。但是在实际实现上与合并排序有很大的不同,合并排序在实现上倾向于合并上,即将每个有序元素集合合并成一个更大的有序元素集合。快速排序则是划分与交换,从线性集合的两端开始,选取基准数,用基准数将整个集合划分为两个区间,左边全部是比基准数小的数,右边全部是比基准数大的数。然后通过分治法继续划分下去,而划分则是通过交换来实现。

代码实现:

int QuickSort(arr * a, int l, int m){//实现快速排序算法//输入:无序元素列表a,列表开始区间坐标和结束区间坐标//输出:成功返回1int s;if (l < m) {s = PartPostion(a, l, m);QuickSort(a, l, s-1);QuickSort(a, s+1, m);}return 1;}

其中的ParPosition函数如下:

int PartPostion(arr* a, int l, int m) {//实现快速排序算法中的划分区间//输入:无序元素列表a,列表开始区间坐标和结束区间坐标//输出:作为中轴的下标int i = l, j = m;int key = a->ite[l];while (i < j) {while (key > a->ite[i] && i < m) {i++;}while (key < a->ite[j]) {j--;}Swap(a, i, j);}Swap(a, i, j);Swap(a, i, j);return j;}

堆排序

堆排序顾名思义,用到了堆,最大堆就是一棵完全二叉树,其中的每一个节点的值都要大于其子女的值。

堆排序的具体思路正是用到了这个最大堆:

使用这些数构造一个最大堆,然后删除堆的最大键。以此类推,便可得到有序元素的集合。其中删除最大键的操作其实就是删除最大堆的根,先将根与堆最后的元素进行交换,然后删除最后的元素,即交换后的根,然后把此时在根上的那个小数再拉下来,让大数顶上去即可。

代码实现:

int HeapSort(arr * a){//使用堆排序的算法排序//输入:无序元素列表//输出:成功返回1int size = a->length;BuildHeap(a, size);while (size != 1) {Swap(a, 0, size - 1); size--;BuildHeap(a, size);}return 1;}

以上实现的BuildHeap函数如下,作用为构造最大堆:

int BuildHeap(arr* a, int size) {//构造一个最大堆//输入:要转化成最大堆的无序元素列表和要生成最大堆的规模//输出:成功返回1for (int n = size/2; n > 0; n--)for (int i = size - 1; i > 0; i--)if (a->ite[(i - 1) / 2] < a->ite[i]) Swap(a, (i - 1) / 2, i);return 1;}

这里我使用了从底而上的构建堆的方法。

总结

这些排序前三个思路都比较简单,尤其是前两个蛮力法的选择排序与冒泡排序。那两个分治法的排序方法还是不太行,合并排序感觉上要比快速排序好懂点,快速排序在通过交换来划分区间的方法感觉还是不太理解,剩下的堆排序感觉上也比较简单。

关键词:
相关文章
俄中新铁路桥贾林达-漠河的年货运量可能会达到2000万吨至4000万-每日快播

俄中新铁路桥贾林达-漠河的年货运量可能会达到200

  据俄罗斯远东媒体援引阿穆尔州州长瓦西里·奥尔洛夫的话报道,俄罗斯和中国有必要签署一系列政府间文件,以进一步有效地开展俄中新铁路口更多

2023-02-13 10:01:35
今头条!印尼2023年将出口超5亿吨煤炭

今头条!印尼2023年将出口超5亿吨煤炭

  印尼能源和矿产资源部部长阿里芬·塔利夫(ArifinTasrif)1月30日表示,印尼今年计划生产695亿吨煤炭,出口518亿吨。  阿里芬·塔利夫称更多

2023-02-13 10:00:08
2月第一周福建省煤炭市场价格稳中微跌

2月第一周福建省煤炭市场价格稳中微跌

  根据商务部重要生产资料监测系统监测数据显示,上周(2023年1月30日-2023年2月5日)福建省监测样本企业的煤炭市场价格平均为162767元吨,更多

2023-02-13 10:00:50
2023年煤炭市场简析 每日简讯

2023年煤炭市场简析 每日简讯

  春节过后,随着各地煤矿生产企业的复工复产,煤炭市场供应偏紧的态势正在缓解,煤炭主产地、沿海港口及进口动力煤价均出现回落。  1、通更多

2023-02-13 09:58:22
当前观察:CCTD:沿海地区现货煤价何以跌势不止?

当前观察:CCTD:沿海地区现货煤价何以跌势不止?

  春节过后,沿海地区现货动力煤价格迅速进入下行通道,且降幅在2月上旬呈现扩大化趋势。  探究近期沿海地区现货煤价下行的原因,应该回归更多

2023-02-13 09:57:23
山西吕梁离石贾家沟煤业有限公司发生一起安全事故 死亡1人-今日热讯

山西吕梁离石贾家沟煤业有限公司发生一起安全事故

  2月8日,山西吕梁离石贾家沟煤业有限公司发生一起死亡1人的安全事故。  2月9日,山西省应急管理厅、山西省地方煤矿安全监督管理局下发通更多

2023-02-10 16:55:52
速讯:山西出现大范围降雪降温天气 相关部门多举措确保能源供应

速讯:山西出现大范围降雪降温天气 相关部门多举

  2月8日至9日,山西迎来大范围降雪降温天气。为应对降雪降温造成用电增加情况,太原铁路部门加大电煤运输保障力度,优化货物列车开行,挖掘更多

2023-02-10 12:08:21
湖北煤矿连续30个月实现安全生产“零事故”

湖北煤矿连续30个月实现安全生产“零事故”

  2月9日从国家矿山安监局湖北局获悉,一年来,湖北煤矿安全生产形势持续稳定向好,2022年再次实现安全生产,创造了煤矿连续30个月零事故零更多

2023-02-10 11:17:08
世界速讯:国铁南宁局管内电厂存煤平均可耗28天

世界速讯:国铁南宁局管内电厂存煤平均可耗28天

  根据2月7日统计数据,国铁南宁局管内10家电厂存煤21239万吨,平均可耗28天。  近期,随着节后返岗复工潮的到来,广西各地企业用电量持续更多

2023-02-10 09:54:28
当前观察:6.6万吨澳煤船在珠海台山边检站通关

当前观察:6.6万吨澳煤船在珠海台山边检站通关

  近日,一艘运载着66万吨进口煤的东方虎轮从澳大利亚入境我国,珠海边检总站台山出入境边防检查站迎来了2023年春节后第一艘入境的国际航行更多

2023-02-10 10:07:01