第九章 排序 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件

本章主要内容 排序的概念 插入排序 顺序插入排序 折半插入排序 希尔排序 快速排序 选择排序 归并排序 分配排序 内部排序算法分析

排序的概念 定义 数据表(dataList) 排序码(key) 将一组杂乱无章的数据按一定规律顺次排列 待排序数据元素的有限集合 通常数据元素有多个属性，作为排序依据的属性称为排序码 学生成绩表，按学号小到大排序，按成绩高到低排序

排序的概念 排序的稳定性 内排序和外排序 两数据元素排序码相同，排序前后两元素先后顺序 内排序 外排序 若相同，则是稳定的 若不同，则不稳定 所有元素都在存在内存的排序 外排序 数据太多，内存放不下，而存放在外部存储器，排序时需要经常在内、外存之间读写数据 初始 2(b) 1(a) 3(d) 2(c) 排序1 1(a) 2(b) 2(c) 3(d) 稳定的 排序2 1(a) 2(c) 2(b) 3(d) 不稳定

排序的概念 排序的时间开销 排序的空间开销 内排序一般用数据比较次数和数据移动次数衡量 外排序一般用外存的读写次数衡量(外存慢) 执行排序算法需要的存储空间

顺序插入排序 顺序插入排序算法 将待排序元素，从后向前寻找适当的插入位置，直到所有元素都插入为止 21 25 49 25* 16 08 初始 第1步 插入25，25 ≥ 21，无需移动 21 25 49 25* 16 08 第2步 插入49，49 ≥ 25，无需移动 21 25 49 25* 16 08 第3步 插入25*，25* < 49， 21 25 25* 49 16 08 49后移，25*填入 21 25 25* 49 16 08 第4步 插入16，16 < 49,25*,25,21， 16 21 25 25* 49 08 49,25*,25,21后移，16填入 16 21 25 25* 49 08 第5步 插入08，08 < 49,25*,25,21,16， 08 16 21 25 25* 49 49,25*,25,21,16后移，08填入

顺序插入排序 算法分析 最好情况(n个元素) 最坏情况(n个元素,i=0,1,…,n-1) 原数据是按小到大顺序排好的 每步只需与前一个数据比较一次，而不用移动数据 总比较次数n-1，总移动次数0 最坏情况(n个元素,i=0,1,…,n-1) 原数据按大到小顺序排好的 元素i需要比较i次，每比较1次移动1次，元素i移动2次 总比较次数和总移动次数 temp = a[i] a[0] = temp 比较和移动最坏最好平均值约为n2/4 时间复杂度O(n2)

顺序插入排序 算法分析 是稳定的算法，key相同元素原来的顺序不会打乱 需要额外一个存储空间 21 25 49 25* 16 08 初始 排序后 temp = a[i] a[0] = temp

折半插入排序 折半插入排序算法 将待排序元素，按折半搜索法寻找适当的插入位置，直到所有元素都插入为止 16 21 25 25* 49 23 1 2 3 4 5 low mid high 16 21 25 25* 49 23 1 2 3 4 5 low mid high mid>23,high=mid-1,mid=(low+high)/2 16 21 25 25* 49 23 1 2 3 4 5 low mid high low>high，49,25*,25后移，23填入 16 21 23 25 25* 49 mid≤23,low=mid+1,mid=(low+high)/2 16 21 25 25* 49 23 1 2 3 4 5 low mid high mid≤23,low=mid+1,mid=(low+high)/2

折半插入排序 算法分析 平均情况下，折半搜索比顺序搜索快 搜索元素i需比较log2i +1次 总比较次数 移动的时间复杂度O(n2) 是稳定的排序算法，需额外一个存储空间 比较的时间复杂度O(n*log2n)

希尔排序 基本思想 设定不同gap值，距离gap的元素放一起插入排序 21 25 49 25* 16 08 初始 第1步 21 25 49 gap= n/3+1 = 3 21 25 49 25* 16 08 21 25 49 25* 16 08 结果 21 16 08 25* 25 49 第2步 21 16 08 25* 25 49 gap= gap/3+1 = 2 21 16 08 25* 25 49 结果 08 16 21 25* 25 49 第3步 08 16 21 25* 25 49 gap= gap/3+1 = 1 08 16 21 25* 25 49 最后1步是n个元素进行插入排序 是不是很慢？ 结果

希尔排序 算法分析 设定不同gap值，距离gap的元素放一起插入排序 …… 希尔排序复杂度分析很困难，还没有完整的数学分析 统计得出，平均比较和移动次数在[n1.25,1.6n1.25]内 是不稳定的排序算法

快速排序 基本思想 Partition：任取一元素x为基准(如选第1个)，小于x的元素放在x左边，大于等于x的元素放在x右边 对左、右部分递归执行上一步骤直至只有一个元素 初始 21 25 49 25* 16 08 第1层 08 16 21 25* 25 49 选21为基准 第2层 08 16 21 25 49 25* 左部选08，右部选25*为基准 第3层 08 16 21 25* 25 49 左部选16，右部选25为基准 第4层 08 16 21 25* 25 49 右部选49为基准

快速排序 Partition(low,high) 初始时基准坐标p = low, x=a[low]=21 从i=low+1位置开始判断，比x小的元素与p下一个位置交换，p自加1 循环直至i > high，最后a[low]与a[p]交换 21 25 49 25* 16 08 21 16 49 25* 25 08 p p i i a[i]与a[p+1]交换, p++ a[i]与a[p+1]交换, p++ 21 16 08 25* 25 49 08 16 21 25* 25 49 p p i>high,停止 a[low]与a[p]交换

作业： 对数据a[N]进行快速排序的程序 qsort(a[ ], 0, n-1)

快速排序 性能分析 快速排序是一个递归算法 08 16 21 25* 25 49 21 08 16 25* 25 49 递归树

快速排序 性能分析 快速排序的趟数取决于递归树的深度 21 08 16 25* 25 49 性能分析 快速排序的趟数取决于递归树的深度 若每次选取的基准可将序列划分成长度相近的左、右两部分，则下一层将对两个长度减半的序列排序 设原序列有n个元素，选基准和划分所需时间为O(n) 设整个快速排序所需时间为T(n)，则有： T(n) ≤ cn + 2T(n/2) // c 是一个常数 ≤ cn + 2(cn/2 + 2T(n/4)) = 2cn + 4T(n/4) ≤ 2cn + 4(cn/4 +2T(n/8)) = 3cn + 8T(n/8) ……… ≤ cn log2n + nT(1) = O(nlog2n )

快速排序 性能分析 快速排序平均计算时间为O(nlog2n) 平均计算时间是所有内部排序方法中最好的 递归算法每层需保存递归调用的指针和参数 平均情况下 最大递归层数为log2(n+1) 存储开销为O(log2n)

快速排序 性能分析 最坏情况 单枝树，每次划分只得到比上一次少一个元素的序列 比较次数 递归树有n层，存储开销为O(n) 21 08 16 25* 25 49 快速排序 性能分析 最坏情况 单枝树，每次划分只得到比上一次少一个元素的序列 比较次数 递归树有n层，存储开销为O(n) 快速排序是不稳定的算法

快速排序 改进算法 快速排序对长度很小的序列排序并不比直接插入快 长度取5~25时，直接插入法比快速排序法快10% 改进方法1： 在快速排序递归过程中，当序列长度小于一定值时，使用直接插入排序法 改进方法2： 在快速排序递归过程中，当序列长度小于一定值时，退出排序 得到一个整体上几乎已经排好序的序列 对这个几乎已经排好序的序列使用直接插入排序法

快速排序 改进算法 基准元素的选取对算法性能有很大影响 改进方法1： 改进方法2： 可随机选择一个元素作为基准，避免最坏情况发生 取左端点、右端点、中点(mid=(left+right)/2)这三个元素中的中间值作为基准 21 25 49 25* 16 35 08 左端点 中点 右端点 取21，25*，08三个元素中的21为基准

选择排序 直接选择排序 在待排序序列中选择最小的元素x x与第一个元素对换 剔除x，对剩下元素执行以上步骤 初始 21 25 49 25* 16 08 第1步 08 25 49 25* 16 21 第2步 08 16 49 25* 25 21 第3步 08 16 21 25* 25 49 第4步 08 16 21 25* 25 49 第5步 08 16 21 25* 25 49

选择排序 直接选择排序 算法分析 设有n个元素，第i趟比较次数为n-i-1次 总比较次数为 移动次数 直接选择排序是不稳定算法 最好情况为0

堆排序 算法思想 建立最大堆 循环执行以下步骤，直至所有元素出堆 每次堆顶元素(即最大元素)与堆中最后一个元素交换 剔除最大元素后调整为最大堆 i=0 49 08 25 25* 16 21 i=2 i=1 49 08 25 25* 16 21 49 08 25 25* 16 21 21 08 25 25* 16 49 21 25 49 25* 16 08 21 25 49 25* 16 08 21 25 49 25* 16 08 49 25 21 25* 16 08 最后一元素的父节点 i=2开始调整 调整i=1 调整i=0 形成最大堆

堆排序 算法思想 建立最大堆 循环执行以下步骤，直至所有元素出堆 每次堆顶元素(即最大元素)与堆中最后一个元素交换 剔除最大元素后调整为最大堆 49 25 25* 25 21 25* 21 16 21 25* 16 08 08 16 49 08 25 49 49 25 21 25* 16 08 25 25* 21 08 16 49 25* 16 21 08 25 49 堆顶49与堆尾08交换 堆顶25与堆尾16交换 堆顶25*与堆尾08交换 虚线内调整为最大堆 虚线内调整为最大堆 虚线内调整为最大堆

堆排序 算法思想 建立最大堆 循环执行以下步骤，直至所有元素出堆 每次堆顶元素(即最大元素)与堆中最后一个元素交换 剔除最大元素后调整为最大堆 21 16 08 16 08 08 21 16 21 25* 25 49 25* 25 49 25* 25 49 21 16 08 25* 25 49 16 08 21 25* 25 49 08 16 21 25* 25 49 堆顶21与堆尾08交换 堆顶16与堆尾08交换 虚线内调整为最大堆 虚线内调整为最大堆 虚线内调整为最大堆

堆排序 堆排序算法分析 建立最大堆 循环弹出堆顶元素 堆排序算法的计算时间复杂度为O(nlog2n) 是不稳定排序 设堆中有n个元素, 对应完全二叉树有k层(2k-1≤n＜2k) 第i层向下调整移动距离最大为(k-i), 第i层节点数为2i-1 总移动次数 循环弹出堆顶元素 执行n-1次向下调整，每次调整距离log2(n+1) 总调整时间O(nlog2n) 堆排序算法的计算时间复杂度为O(nlog2n) 是不稳定排序

归并排序 算法思想 将序列分成两个长度相等的子序列 分别对两个子序列排序 将排好序的两个子序列合并 21 25 49 25* 16 08 31 41 08 16 21 25 25* 31 41 49 21 25 49 25* 16 08 31 41 21 25 25* 49 08 16 31 41 21 25 49 25* 16 08 31 41 21 25 25* 49 08 16 31 41 21 25 49 25* 16 08 31 41 21 25 49 25* 16 08 31 41

归并排序 算法分析 计算时间包括 T(n) = cn+2T(n/2) = O(nlog2n) 对两个子序列分别排序时间 归并的时间 T(n) = cn+2T(n/2) = O(nlog2n) 最好、最坏、平均时间复杂度均为O(nlog2n) 是稳定排序

桶式排序 基本思想 输入：在[0,1)区间内均匀分布的随机序列 将区间[0,1)划分成一系列桶(等长子区间)，如[0, 0.1), [0.1, 0.2), …, [0.9, 1) 对属于桶内的序列分别排序，按桶的编号依次输出 .78 .17 .39 .26 .72 .94 .21 .12 .23 .68 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 .17 .12 .12 .17 .26 .21 .23 .21 .23 .26 .39 .39 .68 .68 .78 .72 .72 .78 .94 .94

桶式排序 算法分析 整个桶排序时间复杂度为 极限情况下，每个桶放一个元素，桶排序最好效率为O(n) 假设每个桶中序列使用直接插入排序，时间复杂度为O(ni2) 极限情况下，每个桶放一个元素，桶排序最好效率为O(n)

基数排序 多排序码排序 花色：       面值：2<3<4<5<6<7<8<9<10<J<Q<K<A 排成以下序列就是多排序码排序 2, …, A, 2, …, A, 2, …, A, 2, …, A 排序后的有序序列称为字典有序序列 可先按花色排序，再按字母排序 也可先按字母排序，再按花色排序

基数排序 多排序码排序 最高位优先(MSD, Most Significant Digit first) 按第1排序码排序，会分成若干组 递归对各组按第2,3,…,d排序码排序 最后把所有子组元素依次连接起来形成有序序列 最低位优先(LSD, Least Significant Digit first) 按第d排序码(最低位)排序 对上一排序结果按第d-1排序码(次低位)排序 对上一排序结果按第d-2排序码排序，以此类推，直到按第1排序码完成排序，可得最终排序结果

基数排序 多排序码排序 最高位优先(MSD, Most Significant Digit first) 按第1排序码排序，会分成若干组 最后把所有子组元素依次连接起来形成有序序列 332 633 059 589 232 664 179 457 825 714 405 361 179 232 332, 361 457, 405 589 633,664 714 825 059 1 2 3 4 5 6 7 8 9 332 361 1 2 4 3 5 6 7 8 9 457 405 1 2 3 4 6 5 7 8 9 633 664 1 2 4 3 5 6 7 8 9

基数排序 最低位优先(LSD) 按第d排序码(最低位)排序 对上一排序结果按第d-1排序码(次低位)排序 332 633 589 232 664 179 457 825 405 361 1 2 3 4 5 6 7 8 9 361 332 232 633 664 825 405 457 589 179 1 2 3 4 5 6 7 8 9 405 405 825 332 232 633 457 361 664 179 589 1 2 3 4 5 6 7 8 9 179 232 332 361 405 457 589 633 664 825 361 179 332 232 825 232 633 332 232 633 332 361 664 405 457 825 405 457 589 361 664 633 664 457 179 589 825 589 179

基数排序 算法性能分析 n：记录数，d：排序码数，r：基数 时间复杂度：分配操作：O(n),收集操作O(r)，需进行d趟分配和收集。时间复杂度：O(d(n+r)) 空间复杂度：所需辅助空间为队首和队尾指针2r个，此外还有为每个记录增加的链域空间n个。空间复杂度O((n+r))

各排序方法时间复杂度比较 排序方法 平均情况 最好情况 最坏情况 直接插入排序 O(n2) O(n) 希尔排序 O(nlog2n) 起泡排序 O (n) 快速排序 直接选择排序 堆排序 O (nlog2n) (二路)归并排序 基数排序 O(d(n+r))

各排序方法空间和稳定性比较 排序方法 辅助空间 稳定性/不稳定举例 直接插入排序 O(1) 是 希尔排序 否/3,2,2*(d=2,d=1) 起泡排序 快速排序 O(log2n) ~O(n) 否/2,2*,1 直接选择排序 堆排序 否/2,1*,1(最大堆) (二路)归并排序 O(n) 基数排序 O(n+r)