更新时间:2022-09-17 10:17:25
名称 | 数据对象 | 稳定性 | 时间复杂度 | 空间复杂度 | 描述 | ||
---|---|---|---|---|---|---|---|
平均 | 最坏 | ||||||
插入排序 | 数组、链表 | √ | O(1) | (有序区,无序区)。把无序区的第一个元素插入到有序区的合适的位置。对数组:比较得少,换得多。 | |||
直接选择排序 | 数组 | × | O(1) | (有序区,无序区)。在无序区里找一个最小的元素跟在有序区的后面。 对数组:比较得多,换得少。 | |||
链表 | √ | ||||||
堆排序 | 数组 | × | O(nlogn) | O(1) | (最大堆,有序区)。从堆顶把根卸出来放在有序区之前,再恢复堆。 | ||
归并排序 | 数组、链表 | √ | O(nlogn) | O(n) +O(logn) , 如果不是从下到上 | 把数据分为两段,从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。 | ||
快速排序 | 数组 | × | O(nlogn) | O(logn) ,O(n) | (小数,枢纽元,大数)。 | ||
Accum qsort | 链表 | √ | O(nlogn) | O(logn) ,O(n) | (无序区,有序区)。把无序区分为(小数,枢纽元,大数),从后到前压入有序区。 | ||
决策树排序 | √ | O(logn!) | O(n!) | O(n) <O(logn!) <O(nlogn) | |||
计数排序 | 数组、链表 | √ | O(n) | O(n+m) | 统计小于等于该元素值的元素的个数 i,于是该元素就放在目标数组的索引 i位。(i≥0) | ||
桶排序 | 数组、链表 | √ | O(n) | O(m) | 将值为 i 的元素放入i 号桶,最后依次把桶里的元素倒出来。 | ||
基数排序 | 数组、链表 | √ | 一种多关键字的排序算法,可用桶排序实现。 |
冒泡排序的主要思想就是通过一趟排序,将数组中的最大值转移到的数组最后一个元素。一个有n个元素的数组,那么经过(n-1)趟排序以后,就能够完成排序。因为如果(n-1)个元素的位置确定了,那么最后的那一个元素的位置也就确定了。还有需要注意的是每一趟排序都能确定数组中的一个元素位置,因此经过一趟排序以后,需要进行排序比较的元素就减少一个。
在每一趟排序过程中,都是从数组元素第一个开始,依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。
冒泡排序法存在的不足及改进方法:
第一,在排序过程中,执行完当前的第k趟排序后,可能数据已全部排序完备,但是程序无法判断是否完成排序,会继续执行剩下的(n-1-k)趟排序。为了解决这一不足,可以设置一个标志位flag,将其初始值设置为非0,表示被排序的数组是一个无序的数组。每一次排序开始前设置flag值为0,表示假设已经完成排序,如果这一趟排序过程中都没有数据发生交换,则flag的值就为0;但是当这一趟排序过程中存在数据交换时,修改flag为非0,表示这一趟仍然有数据没有完成排序。在新一轮排序开始时,检查此标志,若此标志为0,表示上一次没有做过交换数据,则表示经过上一趟的排序,已经完成了对数组的排序,排序结束;否则继续进行排序;
根据上述思路进行改进的冒泡排序代码实现如下:
第二,当排序的数据比较多时排序的时间会明显延长。改进方法:快速排序:具体做法:任意选取某一记录(通常取第一个记录),比较其关键字与所有记录的关键字,并将关键字比它小的记录全部放在它的前面,将比它大的记录均存放在它的后面,这样,经过一次排序之后,可将所有记录以该记录所在的分界点分为两部分,然后分别对这两部分进行快速排序,直至排序完。也就是说,利用快速排序过程中的Partition()方法返回的index将需要排序的元素分为两段,在index前面的数据都比index位置的数据小,在index后面的元素都比index位置的数据大。然后对前后两段数据进行冒泡排序,这样缩小的冒泡排序的数据量。
局部冒泡排序算法对冒泡排序的改进:
在冒泡排序中,一趟扫描有可能无数据交换,也有可能有一次或多次数据交换,在传统的冒泡排序算法及近年来的一些改进的算法中,只记录一趟扫描有无数据交换的信息,对数据交换发生的位置信息则不予处理。为了充分利用这一信息,可以在一趟全局扫描中,对每一反序数据对进行局部冒泡排序处理,称之为局部冒泡排序。局部冒泡排序与冒泡排序算法具有相同的时间复杂度,并且在正序和逆序的情况下,所需的关键字的比较次数和移动次数完全相同。由于局部冒泡排序和冒泡排序的数据移动次数总是相同的,而局部冒泡排序所需关键字的比较次数常少于冒泡排序,这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序有所改进,当比较次数较少的优点不足以抵消其程序复杂度所带来的额外开销,而当数据量较大时,局部冒泡排序的时间性能则明显优于冒泡排序。
参考前面写的博文:
c++实现
java实现(ps:2012-10-8)
此处使用异或方法交换两个元素的值存在一些bug,建议还是使用常规的交换元素方法。
参考文献:白话经典算法系列之五 归并排序的实现
在这里我们看到我们merge的分段是arry[start...mid]跟arry[mid+1...end],我们不能分成arry[start...mid-1]跟arry[mid...end],这是因为mid=(start+end)/2,假如start=1,end=2,则mid=1,此时调用MergeSort(arry,start=1,end=3,temp);会就变成了MergeSort(arry,mid=1,end=3,temp)的死循环了。
本文转自xwdreamer博客园博客,原文链接:http://www.cnblogs.com/xwdreamer/archive/2012/04/06/2435123.html,如需转载请自行联系原作者