《数据结构各种排序方法的综合比较.docx》由会员分享，可在线阅读，更多相关《数据结构各种排序方法的综合比较.docx（7页珍藏版）》请在三一办公上搜索。
1、数据结构各种排序方法的综合比较数据结构各种排序方法的综合比较 结论: 排序方法 平均时间 最坏时间 辅助存储 简单排序 O(n2) O(n2) O(1) 快速排序 O(nlogn) O(n2) O(logn) 堆排序 O(nlogn) O(nlogn) O(1) 归并排序 O(nlogn) O(nlogn) O(n) 基数排序 O(d(n+rd) O(d(n+rd) O(rd) PS:直接插入排序、冒泡排序为简单排序，希尔排序、堆排序、快速排序为不稳定排序 一、时间性能 按平均的时间性能来分，有三类排序方法： 时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最
2、好； 时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为 最好，特别是对那些对关键字近似有序的记录序列尤为如此； 时间复杂度为O(n)的排序方法只有，基数排序。 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 二、空间性能 指的是排序过程中所需的辅助空间大小。 1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)； 2.
3、 快速排序为O(logn)，为栈所需的辅助空间; 3. 归并排序所需辅助空间最多，其空间复杂度为O(n ); 4.链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。 三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。 3. 对于不稳定的排序方法，只要能举出一个实例说明即可。 4. 快速排序和堆排序是不稳定的排序方法 - 二、插入排序 1、直接插入排序 基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增
4、1的有序表。排序过程： 38 38 13 13 13 27 38 49 49 65 76 97 . 27 38 49 65 76 97 49 . 38 49 65 76 97 27 49 . 49 65 76 97 13 27 49 . 49 65 97 76 13 27 49 . 2、折半插入排序 在直接插入排序中，为了找到插入位置，采用了顺序查找的方法。为了提高查找速度，可以采用折半查找，这种排序称折半插入排序。 3、2路插入排序 为减少排序过程中移动记录的次数，在折半插入排序的基础上加以改进： 49 i=1 i=2 i=3 i=4 i=5 i=6 i=7 i=8 49 first 49
5、49 49 49 49 49 49 65 65 65 65 65 49 97 76 76 76 65 97 97 97 76 97 13 first 13 13 first 27 27 38 first 38 first 38 first 38 first 38 38 38 38 65 97 78 13 27 49 . final final final final final final final first 三、快速排序 1、起泡排序 首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第n-1个记录和第n个记录
6、的关键字进行过比较为止。 然后进行第二趟起泡排序，对前n-1个记录进行同样操作。 .直到在某趟排序过程中没有进行过交换记录的操作为止。 49 38 65 97 76 13 27 49 初始 38 49 65 76 13 27 49 97 第一趟 38 49 65 13 27 49 78 第二趟 38 49 13 27 49 65 第三趟 38 13 27 49 49 第四趟 13 27 38 49 第五趟 13 27 38 第六趟 2、快速排序 通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
7、初始关键字 1次交换之后 2次交换之后 3次交换之后 4次交换之后 初始状态 一次划分 分别进行 有序序列 49 i 27 i 27 27 27 49 27 13 结束 13 38 38 38 38 38 38 38 38 27 27 65 65 i i 13 i 13 13 65 13 38 结束 38 97 97 97 97 i ij 49 97 49 49 76 76 76 76 76 76 76 76 49 49 49 13 13 13 j j 97 j 97 13 97 65 65 结束 65 27 j j 65 j 65 65 65 27 65 76 76 49 j 49 49 49 49 49 49 49 97 结束 完成一趟排序 27
