排序

数据的排序有很多种比如：冒泡、选择、插入、快速、希尔、堆排序、双向冒泡、归并、分配、基数等等，其中目前复杂度为【N×(log2N)】的算法是认为比较好的算法，而上述几种算法中“快速排序”的复杂度是其中符合的算法之一，且对于N值比较大的情况下，大部分人会选择此排序算法。

有关快速排序法在网上有很多讲解，下面转载一些比较好的链接：

一：各个排序算法讲解链接（以下链接主要来自百度百科）

1、冒泡排序：http://baike.baidu.com/view/254413.htm

2、选择排序：http://baike.baidu.com/view/547263.htm

3、插入排序：http://baike.baidu.com/view/396887.htm

4、快速排序：http://baike.baidu.com/view/115472.htm

5、希尔排序：http://baike.baidu.com/view/178698.htm 和 http://baike.baidu.com/view/549624.htm

6、堆排序：http://baike.baidu.com/view/157305.htm

7、双向冒泡排序（与冒泡排序基本相同）：<略>

8、归并排序：http://baike.baidu.com/view/90797.htm 和 http://www.programfan.com/blog/article.asp?id=12677

9、分配排序：http://blog.chinaunix.net/u1/50617/showart_544048.html （含归并排序内容）

10、基数排序：http://baike.baidu.com/view/1170573.htm

二、几种排序算法的比较和选择
1. 选取排序方法需要考虑的因素：
(1) 待排序的元素数目n；
(2) 元素本身信息量的大小；
(3) 关键字的结构及其分布情况；
(4) 语言工具的条件，辅助空间的大小等。
2. 小结：
(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。
(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。

三、排序算法稳定性（以下内容转载自：http://baike.baidu.com/view/547325.htm）

　　若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。

　　假定在待排序的记录序列中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ki=kj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

　　对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

　　例如，对于如下起泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成r[j]>=r[j+1]，则两个相等的记录就会交换位置，从而变成不稳定的算法。