算法与数据结构：22-排序3.pdf

第二十二讲第二十二讲 排序排序 快速排序、归并排序快速排序、归并排序 Hore（东尼霍尔，1934-）是一位英国的计算机学家,1960年开始他的计算生涯,作为Elliott Brothers,一个小的科学计算机制造商的一名程序员快速排序算法仅仅是在计算机领域才能的第一次显露后来他受到了公司老板的赏识和重用，希望他为新机器设计一个新的高级语言，为此他参加了由Edsger Wybe Dijkstra举办的“ALGOL 60”培训班，设计了ALGOL 60的改进版本，在执行效率和可靠性上都首屈一指，受到了国际学术界的重视之后他又在“ALGOL X”的设计中还发明了“case”语句，后来也被各种高级语言广泛采用他还提出程序推理的方法，循环不变量来证明命令式语言的某些属性，被称为Hoare逻辑他还设计了并发系统非常有影响力的说明和分析工具CSP因为他在程序设计语言的定义和设计发面做出的基础性的贡献”，1980年获得图灵奖他在1968年成为Belfast 的Queens University的一名计算机科学的教授,并在1977年转到Oxford University1999年因为强制的年龄限制从牛津退休后,继续在英国剑桥的微软研究院从事计算机的研究.1962年年Charles Antony Richard Hoare提出提出Quicksort，之后又有许多人，之后又有许多人对此作了优化，至今为止仍对此作了优化，至今为止仍为最有效的排序算法。

为最有效的排序算法快速排序对冒泡排序的改进 冒泡冒泡排序排序 从后向前从后向前相邻相邻元素两两比较，小的上浮进行元素两两比较，小的上浮进行n n-1 1轮比较，完成轮比较，完成n n个元素排序个元素排序下标下标 0 1 2 3 4 5 6 7 8 r 49 38 65 97 65 13 27 69 快速排序对冒泡排序的改进 冒泡冒泡排序排序 从后向前从后向前相邻相邻元素两两比较，小的上浮进行元素两两比较，小的上浮进行n n-1 1轮比较，完成轮比较，完成n n个元素排序个元素排序下标下标 0 1 2 3 4 5 6 7 8 r 49 38 65 97 13 65 27 69 快速排序对冒泡排序的改进 冒泡冒泡排序排序 从后向前从后向前相邻相邻元素两两比较，小的上浮进行元素两两比较，小的上浮进行n n-1 1轮比较，完成轮比较，完成n n个元素排序个元素排序下标下标 0 1 2 3 4 5 6 7 8 r 49 38 65 13 97 65 27 69 快速排序对冒泡排序的改进 冒泡冒泡排序排序 从后向前从后向前相邻相邻元素两两比较，小的上浮进行元素两两比较，小的上浮进行n n-1 1轮比较，完成轮比较，完成n n个元素排序。

个元素排序下标下标 0 1 2 3 4 5 6 7 8 r 49 38 13 65 97 65 27 69 快速排序对冒泡排序的改进 冒泡冒泡排序排序 从后向前从后向前相邻相邻元素两两比较，小的上浮进行元素两两比较，小的上浮进行n n-1 1轮比较，完成轮比较，完成n n个元素排序个元素排序下标下标 0 1 2 3 4 5 6 7 8 r 49 13 38 65 97 65 27 69 快速排序对冒泡排序的改进 冒泡冒泡排序排序 从后向前从后向前相邻相邻元素两两比较，小的上浮进行元素两两比较，小的上浮进行n n-1 1轮比较，完成轮比较，完成n n个元素排序个元素排序下标下标 0 1 2 3 4 5 6 7 8 r 13 49 38 65 97 65 27 69 费时之处在费时之处在于交换于交换只存在于只存在于相邻两位相邻两位之间之间 改进改进快速排序快速排序 改进思路 示例示例 http:/ 设置设置一个一个基准基准值值（pivot），），将它放在表中合适的将它放在表中合适的位置位置以基准值为界，以基准值为界，序列序列分成两分成两部分部分：左边左边数据数据小于小于等于等于基准值基准值，右半部分数据大于右半部分数据大于等于等于基准值基准值。

然后，对左右两部分分别进行递归处理，直至排好然后，对左右两部分分别进行递归处理，直至排好序为止序为止如何查找基准值位置？如何查找基准值位置？基准数位置的搜索 设两个设两个指针指针low low 和和high,high,开始分别指向表的开开始分别指向表的开始与始与结束结束,分别从两端进行探测分别从两端进行探测 选择第一个记录作为基准值任选择第一个记录作为基准值任一时刻一时刻，基准，基准值或在值或在low low 处处,或或在在highhigh处处 基准值基准值在在lowlow处处：若：若rhigh=rlow,high rhigh=rhigh,low+rlow=rhigh,low+;否则，二者交换否则，二者交换，highhigh -如此循环，直到如此循环，直到low=high,low=high,此处即为基准数此处即为基准数位置位置 例例 L=49,38,65,97,65,13,27,69 初始：49 38 65 97 65 13 27 69 low high 27 38 65 97 65 13 49 69 low high high low low 27 38 49 97 65 13 65 69 high low 27 38 13 97 65 49 65 69 low high low high 27 38 13 49 65 97 65 69 low high high high 一趟排序：27 38 13 low high 13 38 27 low high low 13 27 38 high low high 13 27 38 low high 13 27 38 low high 65 97 65 69 同上同上 快速排序的算法步骤 选取基准选取基准值值pivot,确定其位置确定其位置 当当lowhighlowhigh时时，从表的两端交替向中间从表的两端交替向中间扫描扫描 先先从右向左，当从右向左，当low low=pivothigh&rhigh=pivot时，时，high high-；将将小于基准点的记录交换到左边小于基准点的记录交换到左边；再从左向右，当再从左向右，当lowhigh&rlow=pivotlowhigh&rlow=pivot时，时，low+low+；将将大于基准点的记录交换到大于基准点的记录交换到右边右边；当当low=highlow=high时，时，lowlow的值即为的值即为pivotpivot的最终的最终位置位置 递归快排左子递归快排左子表表 递归快递归快排排右右子表子表 算法实现 void QSort(SqList L,int low,int high)int pivot;/基准值位置 if(lowhigh)pivot=Partition(L,low,high);/将L一分为二，返回基准值位置 QSort(L,low,pivot-1);/左子表递归排序 QSort(L,pivot+1,high);/右子表递归排序 int Partition(SqList L,int low,int high)int pivotkey;/基准值 pivotkey=L.rlow;/第一个记录作为基准值 while(low high)while(low=pivotkey)high-;swap(L,low,high);/将小者交换到左端 while(lowhigh&L.rlow=pivotkey)low+;swap(L,low,high);/将大者交换到右端 return low;快速排序算法性能分析 时间复杂度时间复杂度 与递归深度有关与递归深度有关 最好情况（最好情况（每次基准值都在中间）：每次基准值都在中间）：O()最差情况（正序或逆序）：最差情况（正序或逆序）：O(n2)平均情况：平均情况：O()49 27 65 13 38 69 97 65 快速排序算法性能分析 空间复杂度：空间复杂度：需要栈需要栈空间以实现递归空间以实现递归 最好情况：最好情况：O()最差最差情况：情况：O(n)平均平均情况情况：O()稳定性：跳跃式移动，不稳定（见前例）稳定性：跳跃式移动，不稳定（见前例）快速排序的优化 1.基准点的优化基准点的优化 最坏情况最坏情况下时间复杂性退化为下时间复杂性退化为 O(n2)例：例：10 10 20 30 40 50 60 70 80 20 30 40 50 60 70 80 1020 30 40 50 60 70 801020 30 40 50 60 70 80 原因原因：基准值基准值选择不当选择不当 优化优化 随机选取基准值随机选取基准值 三数取中：最三数取中：最左、最右、中间三个元素左、最右、中间三个元素中取中中取中间值作为基准值，间值作为基准值，通常可以避免最坏通常可以避免最坏情况情况 九九数取中：三次采样，分别三数取中后再取中数取中：三次采样，分别三数取中后再取中 int Partition(SqList L,int low,int high)int pivotkey;/基准值 /选取选取low、mid、high三个记录，将中间值交换到三个记录，将中间值交换到 low处处 pivotkey=L.rlow;/第一个记录作为基准值 while(low high)while(low=pivotkey)high-;swap(L,low,high);/将小者交换到左端 while(lowhigh&L.rlow=pivotkey)low+;swap(L,low,high);/将大者交换到右端 return low;思考：算法如何修改？思考：算法如何修改？快速排序的优化 2.优化不必要的交换优化不必要的交换 一一趟排序过程中，基准点的位置趟排序过程中，基准点的位置变化多变化多次次 原因：每次都要进行两数交换原因：每次都要进行两数交换 优化：改交换为替换，待优化：改交换为替换，待找到找到基准点的最终基准点的最终位置后，一次性位置后，一次性地放到地放到该位置该位置 下标下标 0 1 2 3 4 5 6 7 8 r 49 49 38 65 97 65 13 27 69 low high 快速排序的优化 2.优化不必要的交换优化不必要的交换 一一趟排序过程中，基准点的位置趟排序过程中，基准点的位置变化多变化多次次 原因：每次都要进行两数交换原因：每次都要进行两数交换 优化：改交换为替换，待优化：改交换为替换，待找到找到基准点的最终基准点的最终位置后，一次性位置后，一次性地放到地放到该位置该位置 下标下标 0 1 2 3 4 5 6 7 8 r 49 49 38 65 97 65 13 27 69 low high 快速排序的优化 2.优化不必要的交换优化不必要的交换 一一趟排序过程中，基准点的位置趟排序过程中，基准点的位置变化多变化多次次 原因：每次都要进行两数交换原因：每次都要进行两数交换 优化：改交换为替换，待优化：改交换为替换，待找到找到基准点的最终基准点的最终位置后，一次性位置后，一次性地放到地放到该位置该位置 下标下标 0 1 2 3 4 5 6 7 8 r 49 27 38 65 97 65 13 27 69 low high 快速排序的优化 2.优化不必要的交换优化不必要的交换 一一趟排序过程中，基准点的位置趟排序过程中，基准点的位置变化多变化多次次 原因：每次都要进行两数交换原因：每次都要进行两数交换 优化：改交换为替换，待优化：改交换为替换，待找到找到基准点的最终基准点的最终位置后，一次性位置后，一次性地放到地放到该位置该位置 下标下标 0 1 2 3 4 5 6 7 8 r 49 27 38 65 97 65 13 27 69 low high 快速排序的优化 2.优化不必要的交换优化不必要的交换 一一趟排序过程中，基准点的位置趟排序过程中，基准点的位置变化多变化多次次 原因：每次都要进行两数交换原因：每次都要进行两数交换 优化：改。