专注人工智能在金融领域的应用

排序算法总结

排序算法总结

一、 插入排序

1.直接插入排序

算法思路:设有一组关键字{K1,K2,…,Kn};认为Kl就是一个有序序列;让k2插入上述表长为1的有序序列中,使之成为一个表长为2的有序序列;让K3插入上述表长为2的有序序列中,使之成为一个表长为3的有序序列;以此类推,最后让Kn插入到表长为n-1的有序序列中,得到一个表长为n的有序序列。

2.折半插入排序

算法思路:与直接插入排序相近,只是在进行比较时,r[i].key首先与已排好序的中间记录进行比较,然后根据比较结果来确定r[i].Key继续与中间记录的前面记录比较,还是与中间记录的后面记录比较,找出应插入的位置,然后插入。

3.希尔排序

算法思路:先取一个正整数d1(d1<n),把全部记录分成d1个组,所有距离为dl的倍数的记录看成是一组,然后在各组内进行插入排序;接着取d2(d2<d1),重复上述分组和排序操作;直到di=1 (i>=1),即所有记录成为一个组为止。希尔排序对增量序列的选择没有严格规定,一般选d1约为n/2,d2为d1/2,d3为d2/2,…,di=1。

二、 交换排序

1.冒泡排序

算法思路:若有n个记录需要排序,首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序(即r[2].key<r[1].key),则两个记录交换之,然后比较第二个记录和第三个记录的关键字。依次类推,直至第n个记录和第n-1个记录的关键字进行比较/交换为此。

2.快速排序

(1)任选一个关键字(一般可先第一记录的关键字K1)为控制字,将[K1,K2,…,Kn]分成左、右两个子区,使左区所有关键字小于等于K1,右区所有关键字大于等于K1,最后控制字K1居两个子区中间的适当位置。在子区内数据尚处于无序状态。
(2)将右区首、尾指针〔记录的下标号〕保存入栈,对左区进行与第(1)步相类似的操作,又得到它的左子区和右子区,控制字居中。
(3)重复第(1)、(2)步,直到左区处理完毕。然后退栈,再对另一个子区进行相类同的处理,直到栈空。

三、 选择排序

1.简单选择排序

算法思路:对于一组关键字(Kl,K2,…,kn),将其由小到大进行排序,首先从Kl,K2,…,kn中选择最小值,假如它是Kk,则将Kk与k1对换;然后从K2,K3,…,kn中选择最小值Kk,再将Kk与K2对换。如此进行选择和调换,对第i趟选择排序,进行n-i次关键字比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1≤i≤n)个记录交换。令i从1至n-1,进行n-1趟选择排序,一个由小到大的有序序列就形成。

2.堆排序

堆排序的基本思路是:把n个记录存于向量r之中,把它看成完全二叉树,此时关键字序列不一定满足堆关系。堆排序大体分两步处理。

四、 归并排序

归并排序(Merging sort)是与插入排序、交换排序、选择排序不同的另一类排序方法。归并的含义是将两个或两个以上的有序表组合成一个新的有序表。归并排序可分为多路归并排序,两路归并排序;既可用于内排序,也可用于外排序。这里仅对内排序的两路归并方法进行讨论。
两路归并排序算法思路:假设初始序列含有n个记录,首先把n个记录看成n个长度为1的有序序列,进行两两归并,得到ë n/2」个长度为2的关键字有序序列,再两两归并直到所有记录归并成一个长度为n的有序序列为止。

五、 基数排序

基数排序(radix sort)是与已介绍的各类排序方法完全不同的一种排序方法。前面所介绍的排序方法主要是通过比较记录的关键字大小和移动记录来实现的,而基数排序法不必经过关键字的比较来实现排序,而是根据关键字每个位上的有效数字的值,借助于“分配”和“收集”两种操作来实现排序。

内部排序总结

排序方法

时间复杂度

特殊情况

辅助空间

稳定性

直接插入排序

O(n2)

原表有序O(n)

O(1)

稳定

简单选择排序

O(n2)

同左

O(1)

不稳定

冒泡排序

O(n2)

原表有序O(n)

O(1)

稳定

希尔排序

n1.3

/

O(1)

不稳定

快速排序

O(nlog2n)

原表有序O(n2)

O(nlog2n)或O(n)

不稳定

堆排序

O(nlog2n)

同左

O(1)

不稳定

两路归并排序

O(nlog2n)

同左

O(n)

稳定

基数排序

O(d(n+rd)

同左

O(rd)

稳定

本文介绍的内部排序方法,是最常用的几种排序方法,它们各有优缺点,没有哪一种排序方法是绝对最好的。在应用中,应根据不同情况、不同要求选择较合适的方法,甚至可将多种方法结合使用。下面提几点建议,供编程时参考。

  1. 当待排序的记录数n不大时(约n≤50),可选用表中前三种中的任一种排序方法。它们的时间复杂度虽为O(n2),但方法简单,容易实现。直接插入排序和冒泡排序在原文件记录按关键字“基本有序”时,排序速度比较快。其中直接插入排序更为常用。
  2. 当n值很大,不强求排序稳定性,并且内存容量不宽余时,应该选用快速排序或堆排序。一般来讲,它们排序速度非常快。但快速排序对原序列基本有序的情况,速度减慢接近O(n2),而堆排序不会出现最坏情况。
  3. 当n很大,对排序稳定性有要求,并存储容量较宽余时,用归并排序最为合适。排序速度很快,并且稳定性好。

当n值很大并且关键字位数较小时,采用静态链表基数排序较好。不仅速度较快而且稳定性好。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>