数据结构第7章排序

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

2、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-1Ri无序序列 Ai.n-1有序序列A0.i无序序列 Ai+1.n-1直接插入排序例7.1.1 直接插入排序 直接插入排序算法/ 直接插入排序,数组data用于存放待排序元素，n为待排序元素个数templatevoid 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 & dataj - 1 tmp;j-) dataj

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

5、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 2-路插入排序 将插入区域分成大致等

6、长的两段，选择性地插人到其中一段 排序过程 设置一个和原数组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=516282479 22345581996446设增量d=31622245528346446997981设增量d=116222428344655647981997.1.4 希尔排序 希尔排序算法templatevoid ShellSort(ElemType data, int inc

8、rements , 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 = tmp; 7.1.4 希尔排序 特点 子序列的构成不是简单的“逐段分割”，而是将

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

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

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

12、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），根据枢轴将待排序列划分为两个子列 这两个子列必须满足以下条件：一个子列的元素关键字都不大于枢轴的关键字，另一个子列的元素关键字都不小于枢轴的关键字。7.2.2 快速排序 首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无无

13、 序序 的的 元元 素素 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序7.2.2 快速排序 排序过程 对待排序列A进行快速排序的递归算法QuickSort(A)可以描述如下： 如果A中元素的个数为0或1，则返回；否则，继续 选取A中的一个元素p作为枢轴（pivot） 将A中剩下的元素“划分”成两个不相交的集合： QuickSort (A1), p, QuickSort (A2)12 | ., | .AxApxkeypkeyAxApxkeypkey一趟快速排序例7.2.2 快速排序/ 对datalow.high进行

14、分划，确定枢轴的位置，并返回其所在位置/ 子序列中，在枢轴之前（后）的元素均不大（小）于它templateint Partition(ElemType data , int low , int high) ElemType pivot = datalow; / 用子序列的头元素作为枢轴 while (low high) while (low = pivot) high-; datalow = datahigh;/ 比枢轴小的元素移到低端 while (low = datalow) low+; datahigh = datalow;/ 比枢轴大的元素移到高端 datalow = pivot;/

15、确定枢轴的合适位置 return low;/ 返回枢轴的位置 一趟快速排序算法7.2.2 快速排序 快速排序算法/ 对databegin.end进行快速排序templatevoid QuickSort(ElemType data, int begin, int end) if (begin = end) / data长度小于等于时返回 return; int pivot = Partition(data , begin , end); / 对databegin.end进行分划 QuickSort(data , begin , pivot - 1); / 对低端子列进行递归排序 QuickSor

16、t(data , pivot + 1, end); / 对高端子列进行递归排序 / 快速排序templatevoid QuickSort(ElemType data, int n) if (n 2) return; QuickSort(data, 0, n-1);7.2.2 快速排序 算法分析 最好情况 每次中间值作为枢轴 T(n)=O(nlog2n) 最坏情况 每次总选最大或最小元素作为枢轴 T(n)=O(n) 平均情况 T(n)= O(nlogn) 三数中值分割法7.3 选择类排序 选择类排序 逐趟扫描未排序的部分，从中选取一个元素移动到合适的位置 。 应用选择类排序思想的算法 简单选择排

17、序 树形选择排序 堆排序7.3.1 简单选择排序 假设排序过程中，待排记录序列的状态为：有序序列有序序列A1.i-1无序序列无序序列 Ai.n第第 i 趟简单选择排序趟简单选择排序从中选出关键字最小的从中选出关键字最小的元素元素有序序列有序序列A1.i无序序列无序序列 Ai+1.n7.3.1 简单选择排序 排序过程 第一趟扫描所有待排序元素，找出关键字最小的元素并将它与第一个元素进行交换； 第i趟，扫描待排序列中剩余n - i + 1个元素，找出关键字最小的元素与序列中第i个位置上的元素交换 重复上述操作,直到所有的元素都放到正确的位置上为止简单选择排序例 简单选择排序算法7.3.1 简单选择

18、排序templatevoid 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); / 将datai与第i小的元素交换 7.3.1 简单选择排序 算法分析 最好情况 比较次数： 移动次数：0 最坏情况 比较次数： 移动次数： 3(n - 1) T(n)=O(n)1211()()2nininn121

19、1()()2nininn7.3.2 树形选择排序 简单选择排序中一趟排序中的比较操作可能在前一趟中已经做过，但前一趟中未保存这些比较结果，因此在后一趟的排序中又重复执行了这些操作。为了解决这个问题，树形选择排序应运而生。 算法思想 先将n个元素的关键字两两比较，然后将其中 个较小者两两比较，如此重复，不断的淘汰较大者，最终选出关键字最小的元素树形选择排序例7.3.3 堆排序 堆的定义：堆是满足下列性质的数列a1, a2, ，an：或或221iiiiaaaa221iiiiaaaa(小顶堆)(大顶堆)12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49 小顶堆12,

20、 36, 27, 65, 40, 14, 98, 81, 73, 55, 49 不是堆7.3.3 堆排序 若将该数列视作完全二叉树，则 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子aia2i a2i+1 1236276549817355403498不是堆不是堆147.3.3 堆排序 堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。建大顶堆98, 53, 55, 18, 4, 22, 2424, 53, 55, 18, 4, 22, 98交换 98 和 24重新调整为大顶堆55, 53, 24, 18, 4, 22, 98 22, 18, 53, 98, 4, 24, 5

21、5经过筛选7.3.3 堆排序 排序过程 将待排序列A0n-1调整为大顶堆； 将堆顶元素A0（即关键字最大的元素）与堆尾元素（即堆中最后一个元素）交换，从堆中除去堆尾元素(即关键字最大的元素)，同时调整堆中剩余元素，使它们恢复堆属性； 反复进行步骤2，直至堆中元素个数为1。7.3.3 堆排序 堆排序需解决的两个问题： 如何将初始的待排序列调整为一个堆？ 因堆顶元素与堆尾元素交换后，新的堆顶元素可能破坏了堆属性，如何再调整成为堆？ 第二个问题解决方法 输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中较大者进行交换；重复上述操作，直至叶子结点，将得到

22、新的堆，称这个从堆顶至叶子的调整过程为“筛选”例例堆排序调整例堆排序调整例7.3.3 堆排序 第一个问题解决方法 从最后一个非叶子结点（即第 个元素）开始对所有非叶子结点调整操作建堆例 含7个元素的无序序列（22, 18, 53, 98, 4, 24, 55）2218552449822551853244982255985324418985522532441853 调整堆算法7.3.3堆排序/ 将datai.n-1中的元素调整为大顶堆templatevoid HeapAdjust(ElemType data, int i, int n) ElemType tmp; int child; for

23、( tmp = datai; LeftChild(i) datachild) / 取较大的孩子结点 child+; if (tmp datachild) datai = datachild; else break; datai = tmp;7.3.3 堆排序 堆排序算法/ 堆排序templatevoid 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(d

24、ata0,datai); HeapAdjust(data, 0, i); 7.3.3 堆排序 算法评价 最好情况：O(n) 最坏情况：O(nlogn) 平均： O(nlogn)7.4 归并类排序 归并 将两个有序列合并成为一个新的有序列 2-路归并排序 将相邻的元素两两归并，得到 个长度为2或1的有序子序列，再将这些子序列两两归并，如此重复，直至得到一个长度为n的有序列为止2-路归并排序例“归并”算法/ 将数组data中，lptr.rptr-1rptr.rightEnd两部分的元素进行合并/ tmpArr为合并时的辅存空间templatevoid Merge(ElemType data, El

25、emType tmpArr, int lptr , int rptr, int rightEnd) int leftEnd = rptr - 1; int ptr,i; ptr = i = lptr; while (lptr = leftEnd & rptr = rightEnd) if (datalptr = datarptr) tmpArrptr+ = datalptr+; else tmpArrptr+ = datarptr+; while (lptr = leftEnd) tmpArrptr+ = datalptr+; while (rptr = rightEnd) tmpAr

26、rptr+ = datarptr+; for (;i = rightEnd; i+) datai = tmpArri;2-路归并排序算法templatevoid MPass(ElemType data, ElemType tmpArr, int n, int mergeLength) int i = 0; while (i = n - 2 * mergeLength) Merge(data, tmpArr, i, i+mergeLength, i+2*mergeLength-1); i = i + 2 * mergeLength; if (i + mergeLength n) Merge(da

27、ta, tmpArr, i, i + mergeLength, n - 1);/ 2-路归并算法非递归实现templatevoid MergeSortNonRecursion(ElemType data, int n) int mergeLength = 1; / mergeLength记录每趟归并的步长 ElemType* pArr = NULL; pArr = new ElemTypen;/ pArr为合并时的辅存空间 while (mergeLength n) MPass(data, pArr, n, mergeLength); mergeLength *= 2; delete pArr

28、;7.4 归并类排序 算法评价 T(n)= O(nlogn) 缺点 空间复杂度为O(n) 算法中需要较多的拷贝工作7.5 基数排序 无须比较关键字 通过“分组”和“收集”两个过程来完成排序任务 借助“多关键字排序”的思想7.5.1 多关键字的排序 假设待排序列 a1, a2, an中每个元素ai有d个关键字 ，该序列对关键字 有序是指： 对序列中任意两个元素ai和aj(1 i j n)都满足下列有序关系： 当两个元素的所有关键字都相等时，则必须保持其稳定性。其中 称为最主位关键字， 称为最次位关键字。12(,.,)diiik kk1212(,.,)(,.,)ddiiijjjk kkk kk1k

29、dk7.5.1 多关键字的排序 排序方法 最高位优先法（MSD） 先对最高位关键字k1排序，将序列分成若干子序列，每个子序列有相同的k1值 接着让每个子序列对次关键字k2排序，又分成若干更小的子序列 依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列 最低位优先法（LSD） 从最低位关键字kd起进行排序，然后再对高一位的关键字排序，依次重复，直至对最高位关键字k1排序后，便成为一个有序序列7.5.1 多关键字的排序 MSD与LSD不同特点 按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序 按LSD排序，不必分成子序列，对每个关键

30、字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序7.5.2 基数排序 基数排序依次根据各关键字分量进行“分配”、“收集”完成排序 在单关键字排序中，一个关键字可以看作由若干个关键字分量复合而成，如整数可视为若干数位的集合。基数排序例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

31、;i+,factor *= radix) for ( j = 0;j n; j+) queues(dataj/factor)%radix.push(dataj); / 分配 for ( k = j = 0; j radix; j+,k+) / 收集 while (!queuesj.empty() datak = queuesj.front(); queuesj.pop(); 7.5.2 基数排序 用数组实现基数排序的缺点 虽然不需要进行“比较”操作，但仍需要大量的元素移动操作 还需要额外的空间来存放10个队列 链式基数排序 用链表作存储结构的基数排序7.5.2 基数排序 链式基数排 设置10个

32、队列，fronti和reari分别为第i个队列的头指针和尾指针 第一趟分配对最低位关键字（个位）进行，改变元素的指针值，将链表中的元素分配至10个链队列中，每个队列记录的关键字的个位相同 第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表 重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列链式基数排序（第一趟）例静态链表class SLList struct Node int keyDIGITS; int info; int next;friend ostream& operator(ost

33、ream& os, SLList &s);public: SLList():data(NULL),length(0); SLList(); void Arrange(); /重排 void Init(int arr,int n); void RadixSort(); /链式基数排序private: void Distribute(int, int, int); /分配 void Collection(int, int, int); /收集 Node *data; int length;7.5.2 基数排序void SLList:Distribute(int front, int

34、 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, digit + 1) * 10; if (frontindex = 0) frontindex = i; else datarearindex.next = i; rearindex = i; 链式基数排序 “分配”算法 链式基数排序 “收集”算法7.5.2 基数排序void SLList:Collection(int f

35、ront, int rear, int digit) int i, current; for (i = 0; fronti = 0; i+);/ 找到第一个非空子表 data0.next = fronti;/ 头结点指向第一个非空子表中第一个结点 current = reari+; for (; i RADIX; i+) if (fronti = 0) continue; datacurrent.next = fronti;/ 链接两个非空子表 current = reari; datacurrent.next = 0; 链式基数排序 算法7.5.2 基数排序/ 用SLList实现的基数排序v

36、oid SLList:RadixSort() int i; int frontRADIX,rearRADIX; / 从最低位优先依次对各关键字进行分配收集 for ( i = 0; i DIGITS; i+) Distribute(front, rear, i); Collection(front, rear, i); 7.5.2 基数排序 重排 链式基数排序产生的是一个有序循环链表，只能对它进行顺序访问，无法进行随机访问，因此有时需要对元素重新排列，将元素按照链表结点中next域的值调整位置使其顺序存储 具体做法 顺序扫描有序链表，将链表中第i个结点移动至静态链表中的第i个分量重排例 重排算

37、法7.5.2 基数排序void SLList:Arrange() int i, tmp; int current = data0.next;/ current存放第一个元素的当前位置 for (i = 1; i length; i+) while (current i) / 找到第i个元素，并用current存放其在静态/ 链表中当前位置 current = datacurrent.next; tmp = datacurrent.next; if (current != i) Swap(datacurrent, datai); / 第i个元素调整到位 datai.next = current;

38、 / 指向被移走的元素 current = tmp; / 为找第i + 1个元素做准备 7.5.2 基数排序 算法分析 空间复杂度O(r + n) 时间复杂度T(n)= O(d (n + r)其中，n为待排序元素个数，d为元素的关键字分量数，r为基数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)，