《数据结构-排序.ppt》由会员分享，可在线阅读，更多相关《数据结构-排序.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Chapter 9Sorting1、插入排序（直接插入排序、希尔排序）、插入排序（直接插入排序、希尔排序）2、交换排序（起泡排序、快速排序）、交换排序（起泡排序、快速排序）3、选择排序（简单选择排序、堆排序）、选择排序（简单选择排序、堆排序）4、归并排序、归并排序排序：排序：将数据元素的一个任意序列，重新排列成一将数据元素的一个任意序列，重新排列成一 个个按关键字有序按关键字有序按关键字有序按关键字有序的序列。的序列。9.1 概述概述 假设含假设含 n 个记录的序列为个记录的序列为 R1,R2,Rn，其相，其相应的关键字序列为应的关键字序列为 K1,K2,Kn 这些关键字相互之间可以进行比较，
2、即在它们之间这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系存在着这样一个关系：Kp1Kp2Kpn 按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1,Rp2,Rpn 的操作称作的操作称作排序排序排序排序。例：将关键字序列：例：将关键字序列：52 49 80 36 14 58 61 23 调整为：调整为：14 23 36 49 52 58 61 80 设设 Ki=Kj(1in,1jn,ij)，且在排序前的且在排序前的序列中序列中 Ri 领先于领先于 Rj（即即 i j）。）。若在排序后的序列若在排序后的序列中中 Ri 仍领先于仍领先于 Rj，则称所用
3、的，则称所用的排序方法是稳定的排序方法是稳定的排序方法是稳定的排序方法是稳定的；反之，则称所用的反之，则称所用的排序方法是不稳定的排序方法是不稳定的排序方法是不稳定的排序方法是不稳定的。设排序前的关键字序列为：设排序前的关键字序列为：52,49,80,36,14,58,3636,23 若排序后的关键字序列为：若排序后的关键字序列为：14,23,36,3636,49,52,58,80，则则排序方法是稳定的排序方法是稳定的排序方法是稳定的排序方法是稳定的。若排序后的关键字序列为：若排序后的关键字序列为：14,23,3636,36,49,52,58,80，则则排序方法是不稳定的排序方法是不稳定的排序
4、方法是不稳定的排序方法是不稳定的。内部排序和外部排序内部排序和外部排序 若若整个排序过程不需要访问外存整个排序过程不需要访问外存便能完成，则称便能完成，则称此类排序问题此类排序问题为内部排序；为内部排序；反之，若参加排序的记录数量很大，整个序列的反之，若参加排序的记录数量很大，整个序列的排序过程排序过程不可能在内存中完成不可能在内存中完成，则称此类排序问题，则称此类排序问题为为外部排序外部排序。内部排序的方法内部排序的方法 逐步扩大记录的有序序列的过程逐步扩大记录的有序序列的过程 有序序列区有序序列区无无 序序 序序 列列 区区有序序列区有序序列区无无 序序 序序 列列 区区经过一趟排序经过一
5、趟排序 9.2 插入排序插入排序 有序序列有序序列 R1.i-1 Ri无序序列无序序列 Ri.n有序序列有序序列 R1.i无序序列无序序列 Ri+1.n实现实现“一趟插入排序一趟插入排序”可分可分三步三步进行：进行：3将将 Ri 插入（复制）到插入（复制）到 R j+1 的位置上。的位置上。2将将 R j+1.i-1 中的所有记录均后移一个位置；中的所有记录均后移一个位置；1在在 R1.i-1 中查找中查找 Ri 的插入位置，的插入位置，R1.j.key Ri.key R j+1.i-1.key；一趟直接插入排序的基本思路一趟直接插入排序的基本思路9.2.1 直接插入排序直接插入排序 初始状态
6、初始状态4938659776132749 R0 R1 R2 R3 R4 R5 R6 R7i=1 i=2 3849659776132749i=3 3849659776132749i=4 3849657697132749i=5 3849657697132749i=6 3849657697132749i=7 384965769713274949386597761327494938 排序过程：排序过程：先将序列中第先将序列中第 1 个记录看成是一个有序子序列，个记录看成是一个有序子序列，然后从第然后从第 2 个记录开始，逐个进行插入，直至整个序列有序。个记录开始，逐个进行插入，直至整个序列有序。tem
7、platevoid Insert(ElemTypeelem,int n)/在数组在数组elem中作插入排序中作插入排序 for(int i=1;i0&elemj.key elemj-1.key;j-)/将比将比elemj大的元素交换到后面大的元素交换到后面 Swap (elemj,elemj-1);当当elemj比它前面元素的关键字小时，就向前移动，比它前面元素的关键字小时，就向前移动，直到遇到一个关键字比它大或相等的为止直到遇到一个关键字比它大或相等的为止T(n)=O(n)算法评价算法评价 时间复杂度：时间复杂度：比较次数：比较次数：最好的情况：最好的情况：待排序记录按关键字从小到大排列（正
8、序）待排序记录按关键字从小到大排列（正序）比较次数：比较次数：最坏的情况：最坏的情况：待排序记录按关键字从大到小排列（逆序）待排序记录按关键字从大到小排列（逆序）一般情况：一般情况：待排序记录是随机的，取平均值。待排序记录是随机的，取平均值。直接插入排序是稳定排序直接插入排序是稳定排序 9.2.2 希尔排序（缩小增量排序）希尔排序（缩小增量排序）思路：思路：对待排序列先对待排序列先“宏观宏观”调整，再调整，再“微观微观”调整。调整。排序过程：排序过程：先取一个正整数先取一个正整数 d1 n，把所有相隔把所有相隔 d1 的记录放在一组内，组内进行直接插入排序；然后取的记录放在一组内，组内进行直接
9、插入排序；然后取 d2 0;i-)for(int j=0;jelemj+1.key)elem j elem j+1 9.3 交换排序交换排序 1、冒泡排序、冒泡排序 v 排序过程排序过程 初初 始始 关关 键键 字字 49 38 65 97 76 13 27 49 第第 一一 趟趟 排排 序序 38 49 76 97 13 97 27 97 49 9797 38 49 65 76 13 27 49 979738 49 65 13 27 49 76 76 第第 二二 趟趟 排排 序序 38 49 13 27 49 65 65 第第 三三 趟趟 排排 序序 38 13 27 49 4949 第第
10、四四 趟趟 排排 序序 13 27 3849 49 第第 五五 趟趟 排排 序序 13 13 2727 38 38 第第 六六 趟趟 排排 序序 时间复杂度时间复杂度时间复杂度时间复杂度T T(n n)=)=O O(n n2 2)13 13 27 27 第第 七七 趟趟 排排 序序 一般取第一个记录一般取第一个记录 基本思想：基本思想：任选任选任选任选一个记录，以它的关键字作为一个记录，以它的关键字作为“枢枢枢枢轴轴轴轴”，凡关键字小于枢轴的记录均移至枢轴之前，凡，凡关键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录均移至枢轴之后。关键字大于枢轴的记录均移至枢轴之后。2、一趟快速排序（
11、一次划分）、一趟快速排序（一次划分）lowhigh设设 Rs=52 为枢轴。为枢轴。例：例：52 52 52 49 80 36 14 58 61 97 23 75 high23 low low80highhighhighhigh14lowlow5252课本课本270页页 3、快速排序、快速排序 首先对无序的记录序列进行首先对无序的记录序列进行“一次划分一次划分”，之后分别对，之后分别对分割所得两个子序列分割所得两个子序列“递归递归”进行一趟快速排序。进行一趟快速排序。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴 一次划分一次划分
12、分别进行一趟快速排序分别进行一趟快速排序 有有 序序 的的 记记 录录 序序 列列 void QSort(elem,int low,int high)/对顺序表对顺序表 L 中的子序列中的子序列 L.rlow.high 进行快速排序进行快速排序 if(low high)/长度大于长度大于1 /QSortintint pivotlocpivotloc=Partition(elemPartition(elem,low,high);,low,high);/对对对对 L.rlow.high L.rlow.high 进行一次划分进行一次划分进行一次划分进行一次划分 QSort(elem,low,pivo
13、tloc-1);/对低子序列递归排序，对低子序列递归排序，pivotloc 是是枢轴位置枢轴位置 QSort(elem,pivotloc+1,high);/对高子序列递归排序对高子序列递归排序 第一次调用函数第一次调用函数 Qsort 时时，待排序记录序列的上，待排序记录序列的上下界分别为下界分别为 0 和和 n-1。void QuickSort(elem,int n)/对顺序表进行快速排序对顺序表进行快速排序 QSort(elem,0,n-1);/QuickSort 快速排序的时间分析快速排序的时间分析 若待排序列中记录的关键字是随机分布的，则若待排序列中记录的关键字是随机分布的，则 k 取
14、取 1 至至 n 中任一值的可能性相同。中任一值的可能性相同。由此可得快速排序所需时间的平均值为：由此可得快速排序所需时间的平均值为：结论：结论：结论：结论：快速排序的时间复杂度为快速排序的时间复杂度为 O(n log n)。一次划分所需时间和表长成正比一次划分所需时间和表长成正比 到目前为止快速排序是到目前为止快速排序是平均速度最大平均速度最大平均速度最大平均速度最大的一种排序方法。的一种排序方法。9.4 选择排序选择排序 9.4.1 简单选择排序简单选择排序 首先通过首先通过 n n 1 1 次关键字比较，从次关键字比较，从 n n 个记录中个记录中找出找出关键字最小关键字最小的记录，将它
15、与第一个记录交换。的记录，将它与第一个记录交换。再通过再通过 n n 2 2 次比较，从剩余的次比较，从剩余的 n n 1 1 个记录个记录中找出关键字次小的记录，将它与第二个记录交换。中找出关键字次小的记录，将它与第二个记录交换。重复上述操作，共进行重复上述操作，共进行 n n 1 1 趟排序后，排序趟排序后，排序结束。结束。例例 一趟一趟:13 38 65 97 76 49 27 i=0 二趟二趟:13 27 65 97 76 49 38 三趟三趟:13 27 38 97 76 49 65 四趟四趟:13 27 38 49 76 97 65 五趟五趟:13 27 38 49 65 97 7
16、6 六趟六趟:13 27 38 49 65 76 97 i=4 i=1 i=2 i=3 n-1 n-2 n-6 初始初始：49 38 65 97 76 13 27 jjjjjjk13 49 kki=5 排序结束排序结束比较次数比较次数 for(j=i+1;j n;j+)if(elemj.key elemk.key)k=j;elemielemk;/与第与第 i 个记录交换个记录交换void SelectSort(ElemType elem,int n)/SelectSort 比较次数：比较次数：时间复杂度：时间复杂度：时间复杂度：时间复杂度：O O(n n2 2)for(i=0;i n-1;+i
17、)int k=i;堆的定义：堆的定义：n 个元素的序列个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为当且仅当满足下列关系时，称之为堆堆堆堆。或或(i=1,2,n/2)ki k2i ki k2i+1 ki k2iki k2i+1 9.4.2 堆排序堆排序 可将堆序列看成完全二叉树，则：可将堆序列看成完全二叉树，则：k2i 是是 ki 的左孩子；的左孩子；k2i+1 是是 ki 的右孩子。的右孩子。例例(96,83,27,38,11,09)(13,38,27,49,76,65,49,97)9627091138831327384965764997所有非终端结点的值均不大所有非终端结
18、点的值均不大(小小)于其左右孩子结点的值。于其左右孩子结点的值。堆顶元素必为序列中堆顶元素必为序列中 n 个元素的最小值或最大值个元素的最小值或最大值。小顶小顶堆堆 大顶堆大顶堆 堆排序：堆排序：堆排序需解决的两个问题：堆排序需解决的两个问题：1、如何由一个无序序列建成一个堆？、如何由一个无序序列建成一个堆？2、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？将无序序列建成一个堆将无序序列建成一个堆将无序序列建成一个堆将无序序列建成一个堆，得到关键字最小（大）的，得到关键字最小（大）的 记录；记录；输出堆顶的最小（大）值后，将剩余的输出堆顶
19、的最小（大）值后，将剩余的 n-1 个元个元 素重又建成一个堆素重又建成一个堆，则可得到，则可得到 n 个元素的次小值；如此个元素的次小值；如此 重复执行，重复执行，直到堆中只有一个记录为止，每个记录出堆直到堆中只有一个记录为止，每个记录出堆 的顺序就是一个有序序列的顺序就是一个有序序列，这个过程叫，这个过程叫堆排序堆排序。堆堆堆堆筛筛选选所谓所谓“筛选筛选”指的是，对一棵左指的是，对一棵左/右子树均为堆的完右子树均为堆的完全二叉树，全二叉树，“调整调整”根结点使整个二叉树也成为一个根结点使整个二叉树也成为一个堆。堆。第二个问题解决方法第二个问题解决方法筛选：筛选：输出堆顶元素之后，输出堆顶元
20、素之后，以堆中最后一个元素替以堆中最后一个元素替代之代之；然后将根结点值与左、右子树的根结点值然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；进行比较，并与其中小者进行交换；重复上述操重复上述操作直至叶子结点，将得到新的堆，称这个从堆顶作直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为至叶子的调整过程为“筛选筛选筛选筛选”。132738496576499797972797499738979749656549764976979765762765493849971376对深度为对深度为 k 的堆，的堆，“筛选筛选”所需进行的关键字比较的所需进行的关键字比较的次数至多为
21、次数至多为 2(k-1)。817364279812第一个问题解决方法：第一个问题解决方法：建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程。的过程。例例:排序之前的关键字序列为：排序之前的关键字序列为：40554936123673499881984940 现在，左现在，左/右子树都已经调整为堆，最后只要调右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个整根结点，使整个二叉树是个“堆堆”即可。即可。817355 从无序序列的下标为从无序序列的下标为 (n-2)/2 的的元素（即无序序元素（即无序序列对应的完全二叉树的最后一个内部结点）起，至第列对应的完全二叉树的最后一个内
22、部结点）起，至第一个元素止，进行反复筛选。一个元素止，进行反复筛选。堆排序的时间复杂度：堆排序的时间复杂度：1.对深度为对深度为 k 的堆，的堆，“筛选筛选”所需进行的关键字比较的次数至所需进行的关键字比较的次数至多为多为 2(k-1)；3.调整调整“堆顶堆顶”n-1 次，总共进行的关键字比较的次数不超次，总共进行的关键字比较的次数不超过过 2(log2(n-1)+log2(n-2)+log22)2n(log2n)因此，堆排序的时间复杂度为因此，堆排序的时间复杂度为 O(nlog2n)，与简单选择与简单选择排序排序 O(n2)相比时间效率提高了很多。相比时间效率提高了很多。2.对对 n 个关键
23、字，建成深度为个关键字，建成深度为 h(=log2n+1)的堆，的堆，所需进所需进行行 的关键字比较的次数至多的关键字比较的次数至多 4n；堆排序是一种堆排序是一种速度快速度快速度快速度快且且省空间省空间省空间省空间的排序方法。的排序方法。不稳定。不稳定。不稳定。不稳定。将两个或两个以上的序列组合成一个新的有序表。将两个或两个以上的序列组合成一个新的有序表。在内部排序中，通常采用的是在内部排序中，通常采用的是 2-2-路归并排序路归并排序路归并排序路归并排序。即将。即将两个位置相邻的记录有序子序列归并为一个记录有序的两个位置相邻的记录有序子序列归并为一个记录有序的序列。序列。初始关键字：初始关
24、键字：49 38 65 97 76 13 27 一趟归并后：一趟归并后：38 49 65 97 13 76 27 9.5 归并归并排序排序 看成是看成是 n 个有序的子序列（长度个有序的子序列（长度为为 1），然后两两归并。），然后两两归并。得到得到 n/2 个长度为个长度为2 或或 1 的有序子序列的有序子序列每趟归并的时间复杂度为每趟归并的时间复杂度为O(n)，共需进行，共需进行 log2n 趟。趟。时间复杂度为：时间复杂度为：O(nlog2n)，稳定。稳定。二趟归并后：二趟归并后：38 49 65 97 13 27 76 三趟归并后：三趟归并后：13 27 38 49 65 76 97
25、一趟归并后：一趟归并后：38 49 65 97 13 76 27 排序方法分类：排序方法分类：1)、插入排序：、插入排序：直接插入排序、希尔排序直接插入排序、希尔排序 2)、交换排序：、交换排序：冒泡排序、快速排序冒泡排序、快速排序 3)、选择排序：、选择排序：简单选择排序、堆排序简单选择排序、堆排序 4)、归并排序：、归并排序：2-路归并排序路归并排序 基于不同的基于不同的“扩大扩大”有序序列长度的方法，内有序序列长度的方法，内部排序可分下列几种类型：部排序可分下列几种类型：将无序子序列中的一个或几个记将无序子序列中的一个或几个记录录“插入插入插入插入”到有序序列中，从而到有序序列中，从而增
26、加记录的有序子序列的长度。增加记录的有序子序列的长度。通过通过“交换交换交换交换”无序序列中的记录从而无序序列中的记录从而 得到其中得到其中关键字最小关键字最小或或最大最大的记录，并的记录，并 将它将它加入到有序子序列加入到有序子序列中，以此方法增中，以此方法增 加记录的有序子序列的长度。加记录的有序子序列的长度。从记录的无序子序列中从记录的无序子序列中“选择选择选择选择”关键字最小关键字最小或或最大最大的记录，并将它的记录，并将它 加入到有序子序列加入到有序子序列中，以此方法增中，以此方法增 加记录的有序子序列的长度。加记录的有序子序列的长度。通过通过“归并归并归并归并”两个两个 或两个或两
27、个以上的记录有以上的记录有 序子序列，逐步增序子序列，逐步增加加 记录有序序列的长度。记录有序序列的长度。一、时间性能一、时间性能 时间复杂度为时间复杂度为 O(nlogn)：快速排序、堆排序和快速排序、堆排序和 归并排序归并排序，其中以快速排序为最好。其中以快速排序为最好。时间复杂度为时间复杂度为 O(n2)：直接插入排序、起泡排序和简直接插入排序、起泡排序和简单选择排序，单选择排序，其中以直接插入为最好，特别是对那其中以直接插入为最好，特别是对那其中以直接插入为最好，特别是对那其中以直接插入为最好，特别是对那些对关键字基本有序的记录序列尤为如此。些对关键字基本有序的记录序列尤为如此。些对关
28、键字基本有序的记录序列尤为如此。些对关键字基本有序的记录序列尤为如此。时间复杂度为时间复杂度为 O(n)：基数排序。基数排序。1.按平均时间性能来分，有三类排序方法：按平均时间性能来分，有三类排序方法：各种排序方法的综合比较各种排序方法的综合比较 2.当待排序列按关键字顺序有序时，直接插入排序当待排序列按关键字顺序有序时，直接插入排序和起泡排序能达到和起泡排序能达到 O(n)的时间复杂度，快速排序的时间复杂度，快速排序的时间性能蜕化为的时间性能蜕化为 O(n2)。3.简单选择排序、堆排序和归并排序的时间性能不简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。随记录序列中
29、关键字的分布而改变。二、空间性能二、空间性能 指的是排序过程中所需的辅助空间大小。指的是排序过程中所需的辅助空间大小。1.所有的简单排序方法所有的简单排序方法(包括：直接插入、冒泡和包括：直接插入、冒泡和简单选择简单选择)和和 堆排序的空间复杂度为堆排序的空间复杂度为 O(1)；2.快速排序为快速排序为 O(logn)，为递归程序执行过程中，栈为递归程序执行过程中，栈3.所需的辅助空间；所需的辅助空间；3.归并排序所需辅助空间最多，空间复杂度为归并排序所需辅助空间最多，空间复杂度为 O(n)；三、排序方法的稳定性能三、排序方法的稳定性能 1.对于不稳定的排序方法，只要能举出一个实例说对于不稳定的排序方法，只要能举出一个实例说2.明即可。明即可。2.快速排序、堆排序和希尔排序是不稳定的排序方快速排序、堆排序和希尔排序是不稳定的排序方3.法法。教学要求教学要求 1、掌握排序的基本概念和各种排序方法的、掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用；特点，并能加以灵活应用；2、掌握、掌握插入排序插入排序、交换排序交换排序、选择排序选择排序、归并排序归并排序的方法及其性能分析方法；的方法及其性能分析方法；