数据结构-第8章-排序

8.1排序的基本概念第8章排序排序(sorting)，简单来讲，是指把一组任意顺序的数据序列重新排列成有序的序列。如某班的学生成绩，如表8-1所示，其中的声乐成绩本为一组任意排列的数据（62，66，70，58，58，75），经过一定的操作后得到一组有序的序列（58，58，62，66，70，75或75，70，66，62，58，58），此即为排序。所谓排序就是把序列中的记录按关键字非递减(或非递增)的顺序重新排列起来。假设含有n个记录的序列为｛R1，R2，…，Rn｝，其相应的关键字序列为｛K1，K2，…，Kn｝，对其进行排序是指将这n个记录按照K1，K2，…，Kn的大小顺序来重新排列。对表8-1中的记录而言，按照不同的科目来排序，可得到不同的有序序列。8.1排序的基本概念第8章排序内部排序的方法有很多，按策略可以分为五类：插入排序、交换排序、选择排序、归并排序和基数排序。这些排序方法各有优缺点，用于不同的场合，很难概括的来讲一种方法比另一种方法好，一定要根据待排序序列的初始状态、具体要求来选择合适的排序方法。通常评价排序方法好坏的标准主要有两条：时间复杂度和空间复杂度。时间复杂度主要是分析记录关键字的比较次数和记录的移动次数；空间复杂度为算法中使用的内存辅助空间的多少。另外稳定性也是评价排序性能的一方面。大多数排序算法都有两个基本的操作：比较两个关键字的大小；移动记录。其中移动记录的操作依赖于待排序记录的存储方式，不同的存储方式，移动记录操作的实现也不同。8.1排序的基本概念第8章排序待排序记录的存储结构和移动记录的实现方式主要有以下几种：以顺序表作为存储结构：对记录本身进行物理重排（将记录移到合适的位置）。以链表作为存储结构：无需移动记录，只要修改指针即可。用顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表)：这时只需对辅助表的表目进行物理重排（即只移动辅助表的表目），而不移动记录本身。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。8.2插入排序第8章排序插入排序的基本思想是：将记录分成两部分，一部分是有序序列，第二部分是待排序序列；初始时有序序列仅有第一个记录，依次将待排序序列中的记录取出、并插入到有序序列中的合适位置，使插入后的序列仍保持有序，直至全部待排序记录都插入到有序序列为止。常用的插入排序有直接插入排序和折半插入排序。8.2插入排序第8章排序8.2.1直接插入排序1．基本思想直接插入排序的基本操作是将一个记录插入到一个长度为m(假设)的有序序列中，使之仍保持有序，从而得到一个新的长度为m＋1的有序序列。假设待排序的记录存放在顺序表L[1..n]中，其中L[0]为哨兵。初始时，L[1]自成1个有序序列，L[2..n]为待排序序列。依次将L[i]（2≤i≤n）插入当前的有序序列L[1..i-1]中，生成含n个记录的有序序列。每个记录的一次插入成为一趟直接插入排序。我们用8.1节中学生记录的例子来说明直接插入排序的过程。其关键字序列（社会实践成绩）为{11，10，16，13，2，10}（用下划线对两个相同的关键字加以区分），按照上述思想，其直接插入排序的过程如图8-1所示。其中[]中的序列为已排好序的部分。8.2插入排序第8章排序8.2插入排序第8章排序2．算法实现直接插入排序的实现算法如下：void InsertSort(SortItemL[],intn){ inti,j;for(i=2;i<=n;i++) /*共进行n-1趟插入*/{L[0].key=L[i].key; /*L[0]为监视哨兵，也可做下面for循环结束的标志*/for(j=i–1;L[j].key>L[0].key;j--) /*移动记录、定位插入位置*/ L[j+1].key=L[j].key;L[j+1].key=L[0].key; /*将L[0]即原L[i]记录内容，插到L[j]后一位置*/}}其中L为待排序的顺序表，n为顺序表中记录的个数。8.2插入排序第8章排序3.性能分析算法的主要操作是比较关键字和移动记录（定位插入位置），由两个嵌套的for循环来实现。其中第一个for用于循环顺序表中的每个记录；对不同的顺序表，定位插入位置时需要移动记录的次数也不同。因此，算法的执行时间同记录的个数以及顺序表中记录的顺序有关。以下分析在极端情况下的时间复杂度并就一般情况作出评价。（1）最好情况下的时间复杂度从算法可以看出，当顺序表中的记录本身已经是非递减顺序时：对每趟插入，只做一次比较（L[j].key>L[0].key不成立，退出循环）；定位插入位置时不需要移动记录，只需对L[i]做两次移动操作。因此对n-1趟插入操作，总的比较次数为n-1，移动记录的次数为2(n-1)，所以算法的时间复杂度为O(n)。8.2插入排序第8章排序（2）最坏情况下的时间复杂度当顺序表中记录为非递增顺序时：第i趟插入要做i-1次比较，定位第i（2≤i≤n）个记录的插入位置需要移动记录的次数为i-1+2。所以i-1趟插入的比较次数为，插入次数为，所以总的时间复杂度为O(n2)。（3）平均时间复杂度若顺序表中记录顺序随机，关键字之间的比较次数约为n2/4，即时间复杂度为O(n2)。从所需的附加存储空间来看，直接插入排序只需一个监视哨兵，所以其空间复杂度为O(1)。直接插入排序只涉及到相邻两个记录之间的比较和移动位置，两个关键字相同的记录比较时不会交换位置，所以直接插入排序是稳定的。 8.3交换排序第8章排序8.3.1冒泡顺序1.基本思想冒泡排序是一种简单的排序方法，关键字较小的记录经过与其他记录的对比交换，一步步前移，其排序过程就像气泡从水底逐渐往上冒一样。假设有n个记录的待排序序列存放在顺序表L[1..n]中，首先将第n个记录的关键字和第n-1个记录的关键字相比较，如果为逆序（即L[n-1].key>L[n].key），则将两个记录相互交换，然后比较第n-1个记录和第n个记录的关键字。依次类推，直到第2个记录的关键字和第1个记录的关键字相比为止，这个过程称作一趟冒泡排序，其结果使得关键字最小的记录移到了最前面（存入L[1]中）。然后进行第二趟排序，对后n-1个记录进行排序，其结果使得关键字次大的记录交换到了L[2]中（后n-1个记录的最前面）。8.3交换排序第8章排序第i趟排序是从第n个记录开始，两两比较记录的关键字，若为逆序则交换两记录的位置，直到比较第i+1个记录和第i个记录的关键字位置。第i趟排序的结果使得关键字第i小的记录交换到了顺序表的第i个位置上（后n-i+1个记录的最前面）。整个排序过程需进行n-1冒泡趟排序。如果在一趟排序过程中没有交换记录，则说明序列的关键字已经有序，此时可以提前结束排序。8.3交换排序第8章排序同样以8.1节中的学生记录为例。对其关键字序列（社会实践成绩）{11，10，16，13，2，10}，图8-2给出了每一趟冒泡排序的过程，其中[]中的序列为已排好序的部分。第四趟排序并没有交换记录，说明整个序列都已有序，可以提前结束排序。8.3交换排序第8章排序2.算法实现冒泡排序的实现算法如下：voidBubbleSort(SortItemL[],intn){ inti,j,isChange;for(i=1;i<n;i++) /*共进行n-1趟冒泡*/{

isChange=0;

for(j=n;j>i;j--) /*对第i趟的后n-i+1个记录排序*/if(L[j-1].key>L[j].key) /*如果逆序，交换记录*/{L[0].key=L[j].key;

L[j].key=L[j-1].key;L[j-1].key=L[0].key; isChange=1; /*交换记录的标识置为1*/}

if(isChange==0) /*第i趟如果没有交换记录则退出循环*/

break;}}其中L为待排序的顺序表，n为顺序表中记录的个数。8.3交换排序第8章排序3.性能分析从冒泡排序的算法可以看出若待排序的序列本身就是非递减顺序，则只需进行一趟排序，这一趟排序中共进行n-1次关键字的比较，并且不需要交换记录。因此，最好情况下的时间复杂度为O(n)。若待排序的序列为逆序，则需进行n-1趟排序，共需的比较次数为=(n2-n)/2，记录的交换次数为

=3(n2-n)/2。则最坏情况下的时间复杂度为O(n2)。通常情况下，可以认为冒泡排序的时间复杂度为O(n2)。整个序列越接近有序，需要的排序趟数越少。冒泡排序只在交换记录时需要一个临时记录空间，所以其空间复杂度为O(1)。另外，冒泡排序是稳定的排序方法。8.3交换排序第8章排序8.3.2快速排序 1.基本思想快速排序是一种基于分治法的排序方法。首先选取一个记录（通常可选第一个记录）作为枢轴，通过一趟排序将待排序记录分割成两子序列，其中枢轴左面记录的关键字都不大于枢轴的关键字，枢轴右面记录的关键字都不小于枢轴的关键字。对枢轴的左右两个子序列递归实施这一过程，将待排序的序列划分成更小的子序列，直至每个子序列只包含一个记录为止。最终使得整个序列都有序。8.3交换排序第8章排序2.算法实现8.3交换排序第8章排序2.算法实现8.3交换排序第8章排序3.性能分析从快速排序的算法可以看出，记录的移动次数通常小于记录的比较次数，因此讨论快速排序算法的时间复杂度只要按记录的比较次数来讨论即可。对长度为k的序列进行一趟排序，需要的比较次数为k-1。最坏情况下，当每次选取的枢轴都为其（子）序列中的最大（或最小）记录时，划分出来的两个子序列一个为空，另一个仅比原序列少一个枢轴记录。此时对包含n个记录的序列需要进行n-1趟快速排序，第i趟快速排序的比较次数为n-i，则总的比较次数为。此时算法的时间复杂度为O(n2)。8.3交换排序第8章排序4.枢轴的选取对于随机序列，选取第一个记录作为枢轴是一种简单有效的方法。但是若初始记录序列按关键字有序或基本有序时，用第一个记录作为枢轴，将会使大部分记录都划分到一个子区间中，快速排序将蜕化为冒泡排序。另一种改进的方法是依三者取中的原则来选取枢轴。即比较第一个、中间一个和最后一个记录的关键字，取关键字居中的记录作为枢轴。经验证明，采用三者取中的规则可大大改善快速排序中最坏情况下的性能。8.4选择排序第8章排序8.4.1简单选择排序

1.基本思想简单选择排序又称直接选择排序，是一种很简单的排序方法：首先在待排序序列的所有记录中选出关键字最小的记录，把它与第一个记录互换；然后在其余的记录中再选出关键字最小的记录与第二个记录互换；第i趟在后n-i+1(i=1,2,...,n-1）个记录中选取键值最小的记录与序列的第i个记录互换；依此类推，直至所有记录排序完成。8.4选择排序第8章排序对学生记录中的关键字序列（社会实践成绩）{11，10，16，13，2，10}进行简单选择排序，其过程如图8-5所示。图8-5简单选择排序过程示意图8.4选择排序第8章排序2.算法实现简单选择排序的算法如下：voidSelectSort(SortItemL[],intn){inti,j,k;for(i=1;i<n;i++) /*需进行n-1趟选择和交换*/{

k=i; /*用k记录当前最小记录的下标*/

for(j=i+1;j<=n;j++) if(L[j].key<L[k].key) /*查到关键字更小的记录*/k=j;

if(k!=i) /*L[i]和L[k]互换*/{L[0].key=L[i].key;L[i].key=L[k].key;L[k].key=L[0].key;}} }8.4选择排序第8章排序3.性能分析对n个记录序列进行简单选择排序，需进行n-1趟排序，第i趟排序需进行n-i-1次比较，每趟排序最多需要移动3次记录。所以总的比较次数为，记录的最大移动次数为3(n-1)。因此算法的时间复杂度为O(n2)。简单选择排序的空间复杂度为O(1)。简单选择排序会交换两个不相邻的记录，所以是不稳定的排序方法。8.4选择排序第8章排序8.4.2堆排序

1.算法描述堆排序的思想是：把待排序的序列存于顺序表中，此时关键字序列不一定符合堆的条件。首先建成一个初始堆（大根堆），然后输出堆顶记录，让堆中最后一个记录上移到原堆顶位置，再恢复堆。重复输出堆顶记录、堆尾记录上移、恢复堆的操作，直到堆中只有一个记录为止。由于每次都是从当前堆中输出关键字最大的记录，所以整个输出过程就完成了对序列的排序。堆顶定义如下：n个记录的序列{k1,k2,..ki,ki+1,..kn}，当且仅当其关键字满足条件如下条件时，才称之为堆。8.4选择排序第8章排序堆排序的关键操作为：初始化堆，每趟排序时的输出堆顶记录和恢复堆。堆顶记录是当前堆中关键字最大的记录，并且输出的堆顶记录，被依次从后往前存入顺序表中，所以如果要对序列进行非递减排序，则需对原序列建立一个大根堆。（1）初始化堆设待排序的n个记录存放在顺序表L[1..n]中，L中的n个记录可以对应一棵完全二叉树，但该完全二叉树并不一定满足大根堆的定义，因此要对完全二叉树中的每个结点进行调整。完全二叉树中的叶子节点都满足大根堆的定义，因此只需从最后一个非叶子结点（编号为n/2的结点）依次往前调整，直到调整到根结点。8.4选择排序第8章排序（2）堆排序堆排序的过程就是循环输出堆顶记录（关键字最大的记录）、并调整堆的过程，直到堆中仅有一个记录。具体步骤如下：① 首先利用上述HeapAdjust算法将待排序的序列调整为一个初始堆。② 将堆顶记录（L[1]）和堆尾记录（L[n]）相互交换，即输出堆顶记录。输出之后，堆中记录的个数减一，即n=n-1，新的堆尾记录的逻辑位置也前移一个位置。③ 交换后，新的堆顶记录可能不符合大根堆的定义；而其它所有结点均满足大根堆顶定义，因此只需对堆顶记录调用HeapAdjust算法重新调整。④ 重复步骤②、③，直至堆中只有一个记录位置。8.4选择排序第8章排序2.性能分析8.4选择排序第8章排序2.性能分析8.4选择排序第8章排序2.性能分析8.4选择排序第8章排序2.性能分析8.4选择排序第8章排序2.性能分析8.5归并排序第8章排序1.基本思想二路归并排序的基本思路：（1）把待排序序列中的n个记录看成n个长度length为1的有序子序列。（2）对这n个有序子序列进行两两归并使记录关键字有序，得到n/2个长度为2*length或为length（最后一个）的有序子序列。这一过程称为一趟二路归并。（3）重复步骤（2）直到所有待排序记录归并成一个长度为n的有序序列为止。8.5归并排序第8章排序对学生记录中的关键字序列（社会实践成绩）{11，10，16，13，2，10}，二路归并排序的过程如图8-9所示。8.5归并排序第8章排序2.算法实现（1）两两归并假定待归并的两个有序子序列分别存于顺序表L中下标low到下标mid的单元，和下标mid+1到下标up的单元，结果有序序列存于顺序表R中从下标low到下标up的单元。8.5归并排序第8章排序2.算法实现8.5归并排序第8章排序（2）一趟二路归并每一趟二路归并排序都是依次从前往后将相邻的两个子序列进行归并，并且每个子序列的长度都相等，设为len（最后一个子序列长度可能小于len），归并的结果存入顺序表R中。则一趟排序的过程为：① 从第一个子序列的第一个记录（i=