Page 133 - 高中 信息技术 选择性必修1 数据与数据结构
P. 133
5.3 排序
例6：假设待排序列为39，26，54，83，91，47，18，32，用快速排序算法对该序列
进行升序排序，第一趟快速排序的过程如图5-8所示，快速排序的全部过程如图5-9所示。
序号 1 2 3 4 5 6 7 8
初始 39 26 54 83 91 47 18 32
↑i ↑j往左扫描（32<39，交换32和39）
第一次交换后 32 26 54 83 91 47 18 39
↑i往右扫描 ↑j
广东教育出版社
32 26 54 83 91 47 18 39
↑i ↑j （54>39，交换54和39）
第二次交换后 32 26 39 83 91 47 18 54
↑i ↑j往左扫描
32 26 39 83 91 47 18 54
↑i ↑j （18<39，交换18和39）
第三次交换后 32 26 18 83 91 47 39 54
↑i往右扫描 ↑j
32 26 18 83 91 47 39 54
↑i ↑j （83>39，交换83和39）
第四次交换后 32 26 18 39 91 47 83 54
↑i ↑j往左扫描
32 26 18 39 91 47 83 54
i j （i=j，本趟结束）
图5-8 一趟快速排序的过程
序号 1 2 3 4 5 6 7 8
初始状态 39 26 54 83 91 47 18 32
第一趟排序结果｛32 26 18｝39｛91 47 83 54｝
第二趟排序结果｛18 26｝32 39｛54 47 83｝91
第三趟排序结果 18｛26｝32 39｛47｝54｛83｝91
快速排序最终排序结果 18 26 32 39 47 54 83 91
图5-9 快速排序的全部过程
125125
21X2204.indd 125 2019/9/26 13:53:44
