C++程序设计第七章排序

1、数 据 结 构 第7章 排序 概述 什么是排序？ 排序是计算机内经常进行的一种操作，其目的是将一 组“无序”的元素序列调整为“有序”的元素序列。 排序的分类 待排序元素关键字个数 单关键字排序 多关键字排序 待排序元素的存储介质 内部排序：排序过程不需要访问外存便能完成 外部排序：排序过程需要访问外存才能完成 概述 内部排序的类别 插入类：直接插入排序、折半排序、2-路插入排序、 希尔排序 分划类：冒泡排序、快速排序 选择类：简单选择排序、堆排序 归并类：2-路归并排序 其他方法：基数排序 概述 排序的两个基本操作 比较两个关键字大小 将记录从一个位置移动到另一个位置 稳定性 待排序列 a1,

2、 a2, an，其相应的关键字序列 k1, k2, kn，假设ki = kj ( 1i, jn且i j)，且在排序前的 序列中ai领先于 aj。 若在排序后的序列中ai仍领先于 aj，则称所用的排序方 法是稳定的，反之，则称其是不稳定的。 7.1 插入类排序 插入类排序 将待排序元素逐个插入到已排好序的有序表中，从而 得到一个新的有序表。 应用插入类排序思想的算法 直接插入排序 折半插入排序 2-路插入排序 希尔排序 7.1.1 直接插入排序 排序过程 整个排序过程为n-1趟插入，即先将序列中第1个记录看 成是一个有序子序列，然后从第2个记录开始，逐个进行 插入，直至整个序列有序 第i趟直接插

3、入排序的基本思想 有序序列A0.i-1 Ri 无序序列 Ai.n-1 有序序列A0.i无序序列 Ai+1.n-1 直接插入排序例 7.1.1 直接插入排序 直接插入排序算法 / 直接插入排序,数组data用于存放待排序元素，n为待排序元素个数 template void InsertSort(ElemType data, int n) ElemType tmp; int i, j; for (i = 1; i datai - 1) continue; tmp = datai; / 保存待插入的元素 datai = datai - 1; for ( j = i - 1; j 0 j-) data

4、j = dataj - 1;/ 元素后移 dataj = tmp; / 插入到正确位置 7.1.1直接插入排序 算法评价 时间复杂度 正序 元素移动次数：0 元素比较次数：n-1 逆序 元素移动次数： 元素比较次数： 平均情况 O(n2) 2 (1)(1)/ 2 n i in n 2 (1)(4)(1)/ 2 n i inn 7.1.2 折半插入排序 因为 A0.i-1 是一个按关键字有序的有序序列，则可以利 用“折半查找”实现“在A0.i-1中查找Ai的插入位置” ，如此实现的插入排序为折半插入排序。 减少元素关键字间的比较次数，但元素移动次数不变 折半插入排序例 折半插入排序算法 7.1.

5、2 折半插入排序 template void BInsertSort(ElemType data, int n) ElemType tmp; int i, j, mid, low, high; for (i = 1; i n; i+) tmp = datai, low = 0, high = i-1; while (low = high) / 在datalow.high中查找插入的位置 mid = (low + high) / 2; / 折半 if (tmp = low; j-) dataj + 1 = dataj; / 元素后移 datalow = tmp; / 插入到正确位置 7.1.3

6、2-路插入排序 将插入区域分成大致等长的两段，选择性地插人到其中一 段 排序过程 设置一个和原数组data 同类型，同规模的是数组d，并 将其视为循环数组（即位置n-1和0逻辑上相邻） d0 = data0，将d0看作为排好序中处于中间位置的 元素，从第二个元素data1开始做以下操作 如果dataid0，将datai插入d0之后的有序序列， 并保持插入后有序；反之，将其插入d0之前的有序序 列，并保持插入后有序 2-路插入排序例 7.1.3 2-路插入排序 算法评价 减少约为n2/8的元素移动次数 基准元素选取的好坏直接影响排序的效率 7.1.4 希尔排序 希尔排序又称缩小增量排序 将记录序

7、列分成若干子序列，分别对每个子序列进行 插入排序。 例如：将 n 个记录分成 d 个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 其中，d 称为增量，它的值在排序过程中从大到小逐 渐缩小，直至最后一趟排序减为 1。 希尔排序例 34288179 22165524996446 设增量d=5 16282479 22345581996446 设增量d=3 1622245528346446997981 设增量d=1 1622242834465564798199 7.1.4 希尔排序 希尔排序算法 template

8、 void ShellSort(ElemType data, int increments , int n, int incrementsLength) int i, j, k; ElemType tmp; for ( k = 0; k incrementsLength; k+) / 进行以incrementsk为增量的排序 for ( i = incrementsk; i = incrementsk; j -= incrementsk) if ( tmp = dataj - incrementsk) break; dataj = dataj - incrementsk; dataj = tm

9、p; 7.1.4 希尔排序 特点 子序列的构成不是简单的“逐段分割”，而是将相隔 某个增量的元素组成一个子序列 希尔排序可提高排序速度，因为 分组后n值减小，n更小，而T(n)=O(n),所以T(n)从 总体上看是减小了 关键字较小的记录跳跃式前移，在进行最后一趟增 量为1的插入排序时，序列已基本有序 7.1.4 希尔排序 算法评价 算法效率依赖于增量序列的选择 时间复杂度 在O(n3/2)到O(n7/6)之间 增量序列的取法 最后一个增量必须为1 其他增量间保持“互质” 7.2 分划类排序 分划类排序 通过一趟划分确定一个元素在序列中的位置，保证在 它之前的一组元素不比它大，之后的不比它小，

10、接着 对两组元素继续分划，直至待排序列有序。 应用插入类排序思想的算法 冒泡排序 快速排序 7.2.1 冒泡排序 排序过程 将第一个和第二个元素的关键字进行比较，若为逆序 ，则将两元素互换；接着比较第二个和第三个元素的 关键字，依次类推，直至最后两个元素的完成比较， 这称为第一趟冒泡排序。第一趟排序分划出一组元素 个数为n-1的待排序列和一个关键字最大的元素。 第i趟对前n - i + 1个的元素进行类似的排序操作，得到 一组元素个数为n - i的待排序列和一个关键字次大的元 素。 这样不断分划直至一趟分划时无元素互换为止。 7.2.1 冒泡排序 假设在排序过程中，元素序列A1.n的状态为：

11、无序序列无序序列A1.n-i+1有序序列有序序列 An-i+2.n n-i+1 无序序列无序序列A1.n-i有序序列有序序列 An-i+1.n 比较相邻记录，将关键字最大比较相邻记录，将关键字最大 的记录的记录交换到交换到 n-i+1 的位置上的位置上 第第 i 趟起泡排序趟起泡排序 冒泡排序例 7.2.1 冒泡排序 冒泡排序算法 template void BubbleSort(ElemType data, int n) int lastSwapIndex = n - 1; / 用于记录最后一次交换的元素下标 int i, j; for (i = lastSwapIndex; i 0;i =

12、 lastSwapIndex) lastSwapIndex = 0; for (j = 0; j dataj + 1) Swap( dataj,dataj + 1); lastSwapIndex = j; 7.2.1 冒泡排序 算法评价 最好情况（正序） 移动次数：0 比较次数：n-1 最坏情况（逆序） 移动次数：3n(n-1)/2 比较次数：n(n-1)/2 T(n) = O(n2) 7.2.2 快速排序 一趟快速排序 选第一个待排序元素作为枢轴（或支点pivot），根据 枢轴将待排序列划分为两个子列 这两个子列必须满足以下条件：一个子列的元素关键 字都不大于枢轴的关键字，另一个子列的元素关

13、键字 都不小于枢轴的关键字。 7.2.2 快速排序 首先对无序的记录序列进行“一次划分”，之后分别对分 割所得两个子序列“递归”进行快速排序。 无无 序序 的的 元元 素素 序序 列列 无序记录子序列无序记录子序列(1)无序子序列无序子序列(2) 枢轴枢轴 一次划分一次划分 分别进行快速排序分别进行快速排序 7.2.2 快速排序 排序过程 对待排序列A进行快速排序的递归算法QuickSort(A)可 以描述如下： 如果A中元素的个数为0或1，则返回；否则，继续 选取A中的一个元素p作为枢轴（pivot） 将A中剩下的元素“划分”成两个不相交的集合： QuickSort (A1), p, Qui

14、ckSort (A2) 12 | ., | .AxApxkeypkeyAxApxkeypkey 一趟快速排序例 7.2.2 快速排序 / 对datalow.high进行分划，确定枢轴的位置，并返回其所在位置 / 子序列中，在枢轴之前（后）的元素均不大（小）于它 template int Partition(ElemType data , int low , int high) ElemType pivot = datalow; / 用子序列的头元素作为枢轴 while (low high) while (low = pivot) high-; datalow = datahigh;/ 比枢轴小

15、的元素移到低端 while (low = datalow) low+; datahigh = datalow;/ 比枢轴大的元素移到高端 datalow = pivot;/ 确定枢轴的合适位置 return low;/ 返回枢轴的位置 一趟快速排序算法 7.2.2 快速排序 快速排序算法 / 对databegin.end进行快速排序 template void QuickSort(ElemType data, int begin, int end) if (begin = end) / data长度小于等于时返回 return; int pivot = Partition(data , beg

16、in , end); / 对databegin.end进行分划 QuickSort(data , begin , pivot - 1); / 对低端子列进行递归排序 QuickSort(data , pivot + 1, end); / 对高端子列进行递归排序 / 快速排序 template void QuickSort(ElemType data, int n) if (n 2) return; QuickSort(data, 0, n-1); 7.2.2 快速排序 算法分析 最好情况 每次中间值作为枢轴 T(n)=O(nlog2n) 最坏情况 每次总选最大或最小元素作为枢轴 T(n)=O(

17、n) 平均情况 T(n)= O(nlogn) 三数中值分割法 7.3 选择类排序 选择类排序 逐趟扫描未排序的部分，从中选取一个元素移动到合 适的位置 。 应用选择类排序思想的算法 简单选择排序 树形选择排序 堆排序 7.3.1 简单选择排序 假设排序过程中，待排记录序列的状态为： 有序序列有序序列A1.i-1无序序列无序序列 Ai.n 第第 i 趟简单选择排序趟简单选择排序 从中选出关键字最小的从中选出关键字最小的 元素元素 有序序列有序序列A1.i无序序列无序序列 Ai+1.n 7.3.1 简单选择排序 排序过程 第一趟扫描所有待排序元素，找出关键字最小的元素 并将它与第一个元素进行交换；

18、 第i趟，扫描待排序列中剩余n - i + 1个元素，找出关键 字最小的元素与序列中第i个位置上的元素交换 重复上述操作,直到所有的元素都放到正确的位置上为 止 简单选择排序例 简单选择排序算法 7.3.1 简单选择排序 template void SelectionSort(ElemType data, int n) int i, j, min; for (i = 0; i n; i+) min = i; for (j = i + 1; j n; j+) / 选择datai+1.n-1中最小的元素 if ( dataj datamin) min = j; Swap(datai,datamin

19、); / 将datai与第i小的元素交换 7.3.1 简单选择排序 算法分析 最好情况 比较次数： 移动次数：0 最坏情况 比较次数： 移动次数： 3(n - 1) T(n)=O(n) 1 2 1 1 ()() 2 n i ninn 1 2 1 1 ()() 2 n i ninn 7.3.2 树形选择排序 简单选择排序中一趟排序中的比较操作可能在前一趟中已 经做过，但前一趟中未保存这些比较结果，因此在后一趟 的排序中又重复执行了这些操作。为了解决这个问题，树 形选择排序应运而生。 算法思想 先将n个元素的关键字两两比较，然后将其中 个较小者 两两比较，如此重复，不断的淘汰较大者，最终选出 关键

20、字最小的元素 树形选择排序例 7.3.3 堆排序 堆的定义：堆是满足下列性质的数列a1, a2, ，an： 或或 2 21 ii ii aa aa 2 21 ii ii aa aa (小顶堆)(大顶堆) 12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49 小顶堆 12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49 不是堆 7.3.3 堆排序 若将该数列视作完全二叉树，则 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子 ai a2i a2i+1 12 3627 65 49817355 403498 不是堆不是堆 1

21、4 7.3.3 堆排序 堆排序即是利用堆的特性对记录序列进行排序的一种排序 方法。 建大顶堆 98, 53, 55, 18, 4, 22, 24 24, 53, 55, 18, 4, 22, 98 交换 98 和 24 重新调整为大顶堆 55, 53, 24, 18, 4, 22, 98 22, 18, 53, 98, 4, 24, 55 经过筛选 7.3.3 堆排序 排序过程 将待排序列A0n-1调整为大顶堆； 将堆顶元素A0（即关键字最大的元素）与堆尾元素（ 即堆中最后一个元素）交换，从堆中除去堆尾元素(即 关键字最大的元素)，同时调整堆中剩余元素，使它们 恢复堆属性； 反复进行步骤2，直

22、至堆中元素个数为1。 7.3.3 堆排序 堆排序需解决的两个问题： 如何将初始的待排序列调整为一个堆？ 因堆顶元素与堆尾元素交换后，新的堆顶元素可能破 坏了堆属性，如何再调整成为堆？ 第二个问题解决方法 输出堆顶元素之后，以堆中最后一个元素替代之；然 后将根结点值与左、右子树的根结点值进行比较，并 与其中较大者进行交换；重复上述操作，直至叶子结 点，将得到新的堆，称这个从堆顶至叶子的调整过程 为“筛选” 例例 堆排序调整例 堆排序调整例 7.3.3 堆排序 第一个问题解决方法 从最后一个非叶子结点（即第 个元素）开始对所有非 叶子结点调整操作 建堆例 含7个元素的无序序列（22, 18, 53

23、, 98, 4, 24, 55） 22 18 5524498 22 5518 5324498 22 5598 5324418 98 5522 5324418 53 调整堆算法 7.3.3堆排序 / 将datai.n-1中的元素调整为大顶堆 template void HeapAdjust(ElemType data, int i, int n) ElemType tmp; int child; for ( tmp = datai; LeftChild(i) datachild) / 取较大的孩子结点 child+; if (tmp datachild) datai = datachild; e

24、lse break; datai = tmp; 7.3.3 堆排序 堆排序算法 / 堆排序 template void HeapSort(ElemType data, int n) int i; for (i = n/2; i = 0; i-)/ 建堆 HeapAdjust(data, i, n); / 将堆的根结点与最后的一个叶结点交换,并进行调整 for (i = n - 1;i 0; i-) Swap(data0,datai); HeapAdjust(data, 0, i); 7.3.3 堆排序 算法评价 最好情况：O(n) 最坏情况：O(nlogn) 平均： O(nlogn) 7.4

25、归并类排序 归并 将两个有序列合并成为一个新的有序列 2-路归并排序 将相邻的元素两两归并，得到 个长度为2或1的有序子 序列，再将这些子序列两两归并，如此重复，直至得 到一个长度为n的有序列为止 2-路归并排序例 “归并”算法 / 将数组data中，lptr.rptr-1rptr.rightEnd两部分的元素进行合并 / tmpArr为合并时的辅存空间 template void Merge(ElemType data, ElemType tmpArr, int lptr , int rptr, int rightEnd) int leftEnd = rptr - 1; int ptr,i;

26、 ptr = i = lptr; while (lptr = leftEnd else tmpArrptr+ = datarptr+; while (lptr = leftEnd) tmpArrptr+ = datalptr+; while (rptr = rightEnd) tmpArrptr+ = datarptr+; for (;i = rightEnd; i+) datai = tmpArri; 2-路归并排序算法 template void MPass(ElemType data, ElemType tmpArr, int n, int mergeLength) int i = 0;

27、 while (i = n - 2 * mergeLength) Merge(data, tmpArr, i, i+mergeLength, i+2*mergeLength-1); i = i + 2 * mergeLength; if (i + mergeLength n) Merge(data, tmpArr, i, i + mergeLength, n - 1); / 2-路归并算法非递归实现 template void MergeSortNonRecursion(ElemType data, int n) int mergeLength = 1; / mergeLength记录每趟归并

28、的步长 ElemType* pArr = NULL; pArr = new ElemTypen;/ pArr为合并时的辅存空间 while (mergeLength n) MPass(data, pArr, n, mergeLength); mergeLength *= 2; delete pArr; 7.4 归并类排序 算法评价 T(n)= O(nlogn) 缺点 空间复杂度为O(n) 算法中需要较多的拷贝工作 7.5 基数排序 无须比较关键字 通过“分组”和“收集”两个过程来完成排序任务 借助“多关键字排序”的思想 7.5.1 多关键字的排序 假设待排序列 a1, a2, an中每个元素a

29、i有d个关键字 ， 该序列对关键字 有序是指： 对序列中任意两个元素ai和aj(1 i j n)都满足下列有 序关系： 当两个元素的所有关键字都相等时，则必须保持其稳 定性。其中 称为最主位关键字， 称为最次位关键 字。 12 (,.,) d iii k kk 1212 (,.,)(,.,) dd iiijjj k kkk kk 1 k d k 7.5.1 多关键字的排序 排序方法 最高位优先法（MSD） 先对最高位关键字k1排序，将序列分成若干子序列 ，每个子序列有相同的k1值 接着让每个子序列对次关键字k2排序，又分成若干 更小的子序列 依次重复，直至就每个子序列对最低位关键字kd排 序；

30、最后将所有子序列依次连接在一起成为一个有 序序列 最低位优先法（LSD） 从最低位关键字kd起进行排序，然后再对高一位的 关键字排序，依次重复，直至对最高位关键字 k1排序后，便成为一个有序序列 7.5.1 多关键字的排序 MSD与LSD不同特点 按MSD排序，必须将序列逐层分割成若干子序列，然 后对各子序列分别排序 按LSD排序，不必分成子序列，对每个关键字都是整个 序列参加排序；并且可不通过关键字比较，而通过若 干次分配与收集实现排序 7.5.2 基数排序 基数排序依次根据各关键字分量进行“分配”、“收集” 完成排序 在单关键字排序中，一个关键字可以看作由若干个关键字 分量复合而成，如整数

31、可视为若干数位的集合。 基数排序例 7.5.2 基数排序 用数组实现的基数排序算法 void RadixSort(int data, int n) const int radix = 10; const int digits = 10; int i,j,k,factor; queue queuesradix; for ( i = 0,factor = 1; i digits;i+,factor *= radix) for ( j = 0;j n; j+) queues(dataj/factor)%radix.push(dataj); / 分配 for ( k = j = 0; j radix;

32、 j+,k+) / 收集 while (!queuesj.empty() datak = queuesj.front(); queuesj.pop(); 7.5.2 基数排序 用数组实现基数排序的缺点 虽然不需要进行“比较”操作，但仍需要大量的元素 移动操作 还需要额外的空间来存放10个队列 链式基数排序 用链表作存储结构的基数排序 7.5.2 基数排序 链式基数排 设置10个队列，fronti和reari分别为第i个队列的头指 针和尾指针 第一趟分配对最低位关键字（个位）进行，改变元素 的指针值，将链表中的元素分配至10个链队列中，每 个队列记录的关键字的个位相同 第一趟收集是改变所有非空队

33、列的队尾记录的指针域 ，令其指向下一个非空队列的队头记录，重新将10个 队列链成一个链表 重复上述两步，进行第二趟、第三趟分配和收集，分 别对十位、百位进行，最后得到一个有序序列 链式基数排序（第一趟）例 静态链表 class SLList struct Node int keyDIGITS; int info; int next; ; friend ostream public: SLList():data(NULL),length(0); SLList(); void Arrange(); /重排 void Init(int arr,int n); void RadixSort(); /链

34、式基数排序 private: void Distribute(int, int, int); /分配 void Collection(int, int, int); /收集 Node *data; int length; ; 7.5.2 基数排序 void SLList:Distribute(int front, int rear, int digit) int i, index; for (i = 0; i 0; i = L.datai.next) index = datai.key / (int)pow(10.0, digit) - datai.key / (int)pow(10.0, d

35、igit + 1) * 10; if (frontindex = 0) frontindex = i; else datarearindex.next = i; rearindex = i; 链式基数排序 “分配”算法 链式基数排序 “收集”算法 7.5.2 基数排序 void SLList:Collection(int front, int rear, int digit) int i, current; for (i = 0; fronti = 0; i+);/ 找到第一个非空子表 data0.next = fronti;/ 头结点指向第一个非空子表中第一个结点 current = rea

36、ri+; for (; i RADIX; i+) if (fronti = 0) continue; datacurrent.next = fronti;/ 链接两个非空子表 current = reari; datacurrent.next = 0; 链式基数排序 算法 7.5.2 基数排序 / 用SLList实现的基数排序 void SLList:RadixSort() int i; int frontRADIX,rearRADIX; / 从最低位优先依次对各关键字进行分配收集 for ( i = 0; i DIGITS; i+) Distribute(front, rear, i); C

37、ollection(front, rear, i); 7.5.2 基数排序 重排 链式基数排序产生的是一个有序循环链表，只能对它 进行顺序访问，无法进行随机访问，因此有时需要对 元素重新排列，将元素按照链表结点中next域的值调整 位置使其顺序存储 具体做法 顺序扫描有序链表，将链表中第i个结点移动至静态 链表中的第i个分量 重排例 重排算法 7.5.2 基数排序 void SLList:Arrange() int i, tmp; int current = data0.next;/ current存放第一个元素的当前位置 for (i = 1; i length; i+) while (cu

38、rrent i) / 找到第i个元素，并用current存放其在静态 / 链表中当前位置 current = datacurrent.next; tmp = datacurrent.next; if (current != i) Swap(datacurrent, datai); / 第i个元素调整到位 datai.next = current; / 指向被移走的元素 current = tmp; / 为找第i + 1个元素做准备 7.5.2 基数排序 算法分析 空间复杂度 O(r + n) 时间复杂度 T(n)= O(d (n + r) 其中，n为待排序元素个数，d为元素的关键字分量数 ，r

39、为基数 7.6 内部排序的比较 排序方法平均情况最好情况最坏情况 基数排序O(d(n + r)O(d(n + r)O(d(n + r) 2-路归并排序O(n log n)O(n log n)O(n log n) 堆排序O(n log n)O(n)O(n log n) 快速排序O(n log n)O(n log n)O(n2) 希尔排序O(n) 直接插入排序O(n2)O(n)O(n2) 简单选择排序O(n2)O(n2)O(n2) 7.6 内部排序的比较 从平均性能而言，快速排序最佳，但最坏情况下不如堆排 序和归并排序 直接插入排序、简单选择排序、冒泡排序是O(n2)的排序， 不适合处理n较大的情况 从空间复杂度角度考虑 归并排序需要与待排序列等量的辅助存储空间，其空 间复杂度为O(n)； 基数排序次之，空间复杂度为O(r + n)； 快速排序最坏情况下需要的栈空间为O(n)，最好情况下 需要的栈空间为O(log