[全国计算机等级考试四级含金量]2017年全国计算机等级考试四级复习纲要：排序

六、排序

1.直接插入排序

直接插入排序的基本思想是把表中元素依次插入一个已排好序的表中，就像人们打扑克摸牌时把牌插入手中的若干张牌里一样。表中n个元素依次插入的比较次数为1+2+3+…+（n-1）=n（n-1）/2。在插入时，元素的移动次数最多为1+2+3+…+（n-1）=n（n-1）/2。如果表中元素已排好序，则只需比较n-1次，而移动次数为0。

2.直接选择排序

直接选择排序的基本思想是在表的n个元素中，经过n-1次比较得到其值（或最小值，下同），这就排好了第一个元素;再经过n-2次比较得到余下元素中的值，这就排好了第二个元素…直到比较1次后排好第n-1个元素，第n个元素的位置也就自然确定了。所需的比较次数为（n-1）+（n-2）++1=n（n-1）/2。所需移动次数最多也为n（n-1）/2。如果表中元素排好序，也需要比较n（n-1）/2次，而移动次数为0。

3.冒泡排序

冒泡排序的基本思想是将表中元素两个相邻元素依次比较，若不符合排序要求，则交换位置，这样经过n-1次比较后，将确定出（或最小）元素的位置，这称为一趟扫描。经过n-1次扫描后，就完成了整个表的排序。第一趟扫描的比较次数是n-1，第二趟扫描的比较次数是n-2……，总的比较次数是（n-1）+（n-2）+……+1=n（n-1）/2。如果恰好表中元素按反序排列，则需要移动的次数为3×n（n-1）/2。如果表中元素已排好序，并采用交换标志来表示并未发生过交换，则只需一趟扫描，只比较n-1次，就够了;当然，移动次数也是0。

4.归并排序

归并排序的基本思想是表中元素两两比较排序，使表中的n个元素变成n/2个已排序的组，再两两组比较，而变成n/4个已排序的组……，直到表中只含有一个已排序的组，即完成排序。所需要的比较次数为nlog 2 n，移动次数为n。若表已排好序，则比较次数仍为nlog 2 n，但移动次数为0。

5.快速排序

快速排序的基本思想是把表中某元素作为基准，将表划分为大于该值和小于该值的两部分，然后用递归的方法处理这两个子表，直到完成整个表的排序。快速排序的比较次数为（n-1）+（n-2）+…+1=n（n-1）/2，移动次数最多也是n（n-1）/2。如果每次的基准元素刚好是表的中值，使表分为大小相等的两个子表，则比较次数为nlog 2 n;如果表已排好序，则移动次数为0。

6.常用排序方法的性能比较如下表所示:

常用排序方法的性能比较

排序方法 平均时间 最坏情况的时间 辅助存储

冒泡法、直接选择法、直接插入法 O（n2 ） O（n2 ） O（1）

快速排序 O（nlog2 n） O（n2 ） O（log2 n）

堆排序 O（nlog2n） O（nlog2 n） O（1）

归并排序 O（nlog2 n） O（nlog2 n） O（n）

注:在上表中，我们将n（n-1）/2也记为O（n2 ）。如果在待排序的表中含有多个码值相同的记录，经过排序后，这些记录的相对次序不变，则称这种排序方法是稳定的，否则是不稳定的。根据上述说法，可以看出直接插入法、归并法是稳定的;而直接选择法、冒泡法、快速排序法、堆排序法是不稳定的。

本文来源：https://www.wddqw.com/1toO.html