几种排序算法的思想

秒速五厘米 2022-06-11 04:20 201阅读 0赞

# **一、冒泡排序** #

已知一组无序数据a\[1\]、a\[2\]、……a\[n\]，需将其按升序排列。首先比较a\[1\]与a\[2\]的值，若a\[1\]大于a\[2\]则交换两者的值，否则不变。再比较a\[2\]与a\[3\]的值，若a\[2\]大于a\[3\]则交换两者的值，否则不变。再比较a\[3\]与a\[4\]，依此类推，最后比较a\[n-1\]与a\[n\]的值。这样处理一轮后，a\[n\]的值一定是这组数据中最大的。再对a\[1\]~a\[n-1\]以相同方法处理一轮，则a\[n-1\]的值一定是a\[1\]~a\[n-1\]中最大的。再对a\[1\]~a\[n-2\]以相同方法处理一轮，依此类推。共处理n-1轮后a\[1\]、a\[2\]、……a\[n\]就以升序排列了。

优点：稳定，比较次数已知；

缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。

# 二、选择排序 #

已知一组无序数据a\[1\]、a\[2\]、……a\[n\]，需将其按升序排列。首先比较a\[1\]与a\[2\]的值，若a\[1\]大于a\[2\]则交换两者的值，否则不变。再比较a\[1\]与a\[3\]的值，若a\[1\]大于a\[3\]则交换两者的值，否则不变。再比较a\[1\]与a\[4\]，依此类推，最后比较a\[1\]与a\[n\]的值。这样处理一轮后，a\[1\]的值一定是这组数据中最小的。再将a\[2\]与a\[3\]~a\[n\]以相同方法比较一轮，则a\[2\]的值一定是a\[2\]~a\[n\]中最小的。再将a\[3\]与a\[4\]~a\[n\]以相同方法比较一轮，依此类推。共处理n-1轮后a\[1\]、a\[2\]、……a\[n\]就以升序排列了。

优点：稳定，比较次数与冒泡排序一样，数据移动次数比冒泡排序少；

缺点：相对之下还是慢。

# 三、插入排序 #

已知一组升序排列数据a\[1\]、a\[2\]、……a\[n\]，一组无序数据b\[1\]、b\[2\]、……b\[m\]，需将二者合并成一个升序数列。首先比较b\[1\]与a\[1\]的值，若b\[1\]大于a\[1\]，则跳过，比较b\[1\]与a\[2\]的值，若b\[1\]仍然大于a\[2\]，则继续跳过，直到b\[1\]小于a数组中某一数据a\[x\]，则将a\[x\]~a\[n\]分别向后移动一位，将b\[1\]插入到原来a\[x\]的位置这就完成了b\[1\]的插入。b\[2\]~b\[m\]用相同方法插入。（若无数组a，可将b\[1\]当作n=1的数组a）

优点：稳定，快；

缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

# 四、缩小增量排序 #

由希尔在1959年提出，又称希尔排序。

已知一组无序数据a\[1\]、a\[2\]、……a\[n\]，需将其按升序排列。发现当n不大是，插入排序的效果很好。首先取一增量d(d<n)，将a\[1\]、a\[1+d\]、a\[1+2d\]……列为第一组，a\[2\]、a\[2+d\]、a\[2+2d\]……列为第二组……，a\[d\]、a\[2d\]、a\[3d\]……列为最后一组依此类推，在各组内用插入排序，然后取d'<d，重复上述操作，直到d=1。

优点：快，数据移动少；

缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。

# 五、快速排序 #

快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。

已知一组无序数据a\[1\]、a\[2\]、……a\[n\]，需将其按升序排列。首先任取数据a\[x\]作为基准。比较a\[x\]与其它数据并排序，使a\[x\]排在数据的第k位，并且使a\[1\]~a\[k-1\]中的每一个数据<a\[x\]，a\[k+1\]~a\[n\]中的每一个数据>a\[x\]，然后采用分治的策略分别对a\[1\]~a\[k-1\]和a\[k+1\]~a\[n\]两组数据进行快速排序。

优点：极快，数据移动少；

缺点：不稳定。

经过一段时间的学习和编程，我已对上述几种排序方法熟练掌握或有所了解。在此基础上，经过我的思考和实践，我研究出了一种新的排序[算法][Link 1]：分段插入排序。

## 分段插入排序 ##

已知一组升序排列数据a\[1\]、a\[2\]、……a\[n\]，一组无序数据b\[1\]、b\[2\]、……b\[m\]，需将二者合并成一个升序数列。先将数组a分成x等份（x<<n)，每等份有n/x个数据。将每一段的第一个数据先储存在数组c中：c\[1\]、c\[2\]、……c\[x\]。运用插入排序处理数组b中的数据。插入时b先与c比较，确定了b在a中的哪一段之后，再到a中相应的段中插入b。随着数据的插入，a中每一段的长度会有变化，所以在每次插入后，都要检测一下每段数据的量的标准差s，当其大于某一值时，将a重新分段。在数据量特别巨大时，可在a中的每一段中分子段，b先和主段的首数据比较，再和子段的首数据比较，可提高速度。

优点：快，比较次数少；

缺点：不适用于较少数据的排序，s的临界值无法确切获知，只能凭经验取。

我设计的算法或许优于某些算法，但它也有它的优点、缺点和适用范围。不仅排序算法如此，任何算法都一样。没有任何一个人干说自己的算法是最好的。设计新算法的过程其实就是增加其优点，减少其缺点和拓宽其适用范围的过程。我最崇尚的一句话就是：“没有最好，只有更好。”

[Link 1]: http://lib.csdn.net/base/datastructure