清华本科教程 续

第十章 排    序

10.1 概述

一、 什么是排序？

    排序是计算机内经常进行的一种操作，其目

的是将一组“无序”的记录序列调整为“有序”的记

录序列。

例如：将下列关键字序列

52, 49, 80, 36, 14, 58, 61, 23, 97, 75

其相应的关键字序列为

                { K

这些关键字相互之间可以进行比较，即在它们

之间存在着这样一个关系

            Kp

1

≤Kp

2

≤…≤Kp

n

按此固有关系将式(1)的记录序列重新排列为

                { Rp

1

, Rp

2

, …，Rp

n

排序问题为外部排序。

    在本章内先讨论内部排序的各种方法，然后

介绍外部排序的基本过程。

三、 内部排序的方法

    内部排序的过程是一个逐步扩大记录的有序

序列长度的过程。在排序的过程中，参与排序

的记录序列中存在两个区域：有序区和无序区。

使有序区中记录的数目增加一个或几个的操作

称为一趟排序。

        逐步扩大记录有序序列长度的方法大致有

下列几类：

度；

2. 交换类

通过“交换”无序序列中的记录从而得到其中

关键字最小或最大的记录，并将它加入到有序

子序列中，以此方法增加记录的有序子序列的

通过“归并”两个或两个以上的记录有序子序

列，逐步增加记录有序序列的长度;

5. 其它方法

下面将对每一类的排序算法介绍一至两个排序

算法。

10.2 插入排序

假设在排序过程中，记录序列 R[1..n]的状态为：

则一趟直接插入排序的基本思想为：将记录

R[i]插入到有序子序列 R[1..i-1]中，使记录的

有序序列从 R[1..i-1]变为 R[1..i]。

显然，完成这个“插入”需分三步进行：

1．查找 R[i]的插入位置 j+1；

2．将 R[j+1..i-1]中的记录后移一个位置；

    R[0] = R[i];                        // 设置“哨兵”

    for (j=i-1; R[0].key<R[j].key; --j);   

                                              // 从后往前找

    return j+1;          // 返回 R[i]的插入位置为

j+1

2．对于在查找过程中找到的那些关键字不小于

R[i].key 的记录，可以在查找的同时实现向后

移动；

    for (j=i-1; R[0].key<R[j].key; --j);   

          R[j+1] = R[j]

3．i = 2，3，…, n, 实现整个序列的排序。

    for ( i=2; i<=n; ++i )

    {

        R[0] = R[i];                        // 复制为监视哨

        for ( j=i-1; R[0].key < R[j].key;    --j )

            R[j+1] = R[j];                // 记录后移

        R[j+1] = R[0];                // 插入到正确位

置

    }

} // InsertSort

时间分析：

数 ：         “移

动” 的次数：

最坏的情况（关键字在记录序列中逆序有序）：

“比较”的次数：          “移动”的次数：

二、折半插入排序

    因为 R[1..i-1]是一个按关键字有序的有序序