10.快速排序归并排序.ppt

快速排序 * 分治策略的基本思想 1、分解：将原问题分解为若干个规模更小但结构与原问题相似的子问题 2、求解：递归求解子问题 3、组合：将子问题的解组合为原问题的解 比如试卷整理，按高分到低分顺序排序试卷， 先可以定个 60 分及格标准， 及格的从高分到低分排好，不及格也排好，二叠放一起则所有试卷有序； 而不及格的又可以分高于 30 分和低于 30 分二个档次； 及格的也可以再以 80 分为界限去分； ………… 快速排序 4 8 3 6 9 2 5 7 a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 待排序段 左位置 L = 1 ，右位置 R = 8 取中间一个基准值 x = a[(L+R)/2] = a[4] = 6 然后以 x = 6 为标准，将这段数分成二段，左段各数 ≤ x 右段各数 ≥ x 若能将左段各数有序， 右段各数有序， 则整个 L ～ R 段就会变得有序 前面指定 60 分基准值，这里变成随手抽张试卷的 x 分去做基准值 L - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - R 4 8 3 6 9 2 5 7 a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] L - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - R i ↓ j ↓ x = 6 左右位置指示，初始为 i = L j = R 4 8 3 6 9 2 5 7 a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] L - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - R while(a[i]x) i++; i 停在 a[i]≥x 位置 保证 i 左边的 ≤ x i ↓ j ↓ x = 6 while(a[j]x) j--; j 停在 a[i]≤x 位置 保证 j 右边的 ≥ x 4 8 3 6 9 2 5 7 a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] L - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - R i ↓ j ↓ x = 6 此时，需要 swap(a[i],a[j]); 然后 i++; j--; 4 5 3 6 9 2 8 7 a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] i ↓ j ↓ 维持 i 左边的比 6 小，j 右边的比 6 大 L - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - R x = 6 4 5 3 6 9 2 8 7 a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] i ↓ j ↓ 继续 while(a[i]x) i++; while(a[j]x) j--; 4 5 3 6 9 2 8 7 a[1] a[2] a[