<1>直接选择排序(Selection Sort):简单的选择排序,它的比较次数一定:n(n-1)/2。也因此无论在序列何种情况下,它都不会有优秀的表现(从上100K的正序和反序数据可以发现它耗时相差不多,相差的只是数据移动时间),可见对数据的有序性不敏感。它虽然比较次数多,但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。
# /*
# 2.直接选择排序 选择排序是这样实现的:
# 1.首先在未排序序列中找到最小元素,存放到排序序列的起始位置
# 2.然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。
# 3.以此类推,直到所有元素均排序完毕。
# */
<2>直接插入排序(Insertion Sort):简单的插入排序,每次比较后最多移掉一个逆序,因此与冒泡排序的效率相同。但它在速度上还是要高点,这是因为在冒泡排序下是进行值交换,而在插入排序下是值移动,所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较,在最坏情况下,将需要n(n-1)/2次比较。
# /*
# 1.直接插入排序 一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
#
# 1. 从第一个元素开始,该元素可以认为已经被排序
# 2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
# 3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
# 4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
# 5. 将新元素插入到该位置中
# 6. 重复步骤2
# */
<3>冒泡排序(Bubble Sort):将相邻的两个数据元素按关键字进行比较,如果反序,则交换。对于一个待排序的数据元素序列,经一趟排序后最大值数据元素移到最大位置,其它值较大的数据元素向也最终位置移动,此过程为一次起泡。然后对下面的记录重复上述过程直到过程中没有交换为止,则已完成对记录的排序。
# /*
# 3.冒泡排序 冒泡排序是这样实现的:
#
# 1. 首先将所有待排序的数字放入工作列表中。
# 2. 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。
# 3. 重复2号步骤(倒数的数字加1。例如:第一次到倒数第二个数字,第二次到倒数第三个数字,依此类推...),直至再也不能交换。
#
# 冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法
#
<4>快速排序(Quick Sort):是冒泡排序的改进,它通过一次交换能消除多个逆序,这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下,它的排序时间复杂度为O(nlog2n)。即每次划分序列时,能均匀分成两个子串。但最差情况下它的时间复杂度将是O(n^2)。即每次划分子串时,一串为空,另一串为m-1(程序中的100K正序和逆序就正是这样,如果程序中采用每次取序列中部数据作为划分点,那将在正序和逆时达到最优)。从100K中正序的结果上看“快速排序”会比“冒泡排序”更慢,这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”,在理论上讲,如果每次能均匀划分序列,它将是最快的排序算法,因此称它作快速排序。虽然很难均匀划分序列,但就平均性能而言,它仍是基于关键字比较的内部排序算法中速度最快者。
# /*
# 5.快速排序 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。
#
# 步骤为:
#
# 1. 从数列中挑出一个元素,称为 "基准"(pivot),
# 2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
# 3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
#
# 递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递回下去,但是这个演算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
# */
<5>希尔排序(Shell Sort):增量的选择将影响希尔排序的效率。但是无论怎样选择增量,最后一定要使增量为1,进行一次直接插入排序。但它相对于直接插入排序,由于在子表中每进行一次比较,就可能移去整个经性表中的多个逆序,从而改善了整个排序性能。希尔排序算是一种基于插入排序的算法,所以对数据有序敏感。
<6>归并排序(Merge Sort):归并排序是一种非就地排序,将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并,将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是 O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大,那将不适合。但可改造成索引操作,效果将非常出色。
排序方法的选择
因为不同的排序方法适应不同的应用环境和要求,所以选择合适的排序方法很重要
(1)若n较小,可采用直接插入或直接选择排序。
当记录规模较小时,直接插入排序较好,它会比选择更少的比较次数;
但当记录规模较大时,因为直接选择移动的记录数少于直接插人,所以宜用选直接选择排序。
这两种都是稳定排序算法。
(2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机,原因见上的快速排序分析);这里快速排序算法将不稳定。
(3)若n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。
快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。
归并排序是稳定的排序算法,但它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。
(4)特殊的箱排序、基数排序
它们都是一种稳定的排序算法,但有一定的局限性:
1>关键字可分解。
2>记录的关键字位数较少,如果密集更好
3>如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。
分享到:
相关推荐
2022整理python常用算法大全(各种算法说明写法)
概要说明书怎么写?这是一个算法类项目的概要说明书。非常详细。对于怎样写算分类问题的概要说明书可以说是个很好的范例。
svm算法源码和文献说明 svm算法源码和文献说明 svm算法源码和文献说明
给出详细的说明。 对于排序的算法我想先做一点简单的介绍,也是给这篇文章理一个提纲。 我将按照算法的复杂度,从简单到难来分析算法。 第一部分是简单排序算法,后面你将看到他们的共同点是算法复杂度为O(N*...
silan_mems_手环算法说明书
资源内容:基于凸优化各种算法的matlab仿真(完整源码+说明文档+数据).rar 代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 适用对象:工科生、数学专业、算法等方向学习者。 作者介绍:某...
CMMB接收机STiMi 算法说明书。用于说明STIMI接收机全部基带数字信号处理流程和算法。
Mifare One算法说明,详细说明加密算法、随机数算法及安全漏洞
DW1000 PDOA测距官方算法说明文档 AOA TDOA PDOA ....
排序算法大集合,包括各种算法,文档中包括各种算法的详细说明和例子。并比较他们的性能。
DES加密算法及有关说明 DES加密算法及有关说明
复权因子与复权价的计算,文档阐述的关键论点是各种经典复权算法和前复权算法后复权算法都没有任何利用价值,特别对于计算收益率曲线,而万得的涨跌幅复权算法才是正确的,这是文档的关键,可以学习,至于算法比较...
油藏工程软件包算法说明(储层流体物性参数计算)
华中科技大学牛逼老师主讲,对大家非常有用。 下载下来就晓得是好资料了!呵呵
哈夫曼算法压缩jpeg算法源码+项目说明.zip哈夫曼算法压缩jpeg算法源码+项目说明.zip哈夫曼算法压缩jpeg算法源码+项目说明.zip哈夫曼算法压缩jpeg算法源码+项目说明.zip哈夫曼算法压缩jpeg算法...
PID算法,深入浅出学习的好资料!详细推演比例P、微分I、积分D的过程。
会者不难,A*(念作A星)算法对初学者来说的确有些难度。 压缩包包括C++语言的A*算法源代码和技术说明文档,如果你只是想看看它的运行效果...技术说明文档描述了算法的原理,还有大量的图片帮助你更容易理解A Star算法。
著名的libsvm算法的说明
ST加密库文档说明 包含各种加密算法说明 例程 API简介,文档十分详细,需要在STM32端实现加密算法的可以下载研究学习
这个是一个关于DE算法的一个PDF论文,里面有关于这个算法的说明。