10.3交换排序—快速排序 2基本思想:是通过一趟排序将一个记录 结 (其关键字叫做控制关键字)置于排序序 构列的最终位置上,从而将文件分成两部分 使关键字值比控制关键字小的都在前面部 分,大的均在其后。然后再对这两部分重 复上述过程进行排序,直至每一部分中只 部 剩下一个记录为止。 序 一般,选择待排序列中最左端的关键 字作为控制关键字 29 Witkey 65 76 13 27 49 ↑high 据 65 97 76 13 4949 构 个L 个 27 38 49 76 13 65 49 ↑high←↑high 7649 65 49 个Low→↑Lov ↑high 新[2738134769765 49 序 high个↑Low←↑hgh 趙 4976 二趙13 49 97 排序 13 49 6576 9715 数 据 结 构 之 内 部 排 序 29 10. 3 交换排序——快速排序 ¾ 基本思想：是通过一趟排序将一个记录 （其关键字叫做控制关键字）置于排序序 列的最终位置上，从而将文件分成两部分， 使关键字值比控制关键字小的都在前面部 分，大的均在其后。然后再对这两部分重 复上述过程进行排序，直至每一部分中只 剩下一个记录为止。 一般，选择待排序列中最左端的关键 字作为控制关键字。 数 据 结 构 之 内 部 排 序 30 27 38 13 49 76 97 65 49 27 38 13 49 76 97 65 49 27 38 13 97 76 49 65 49 27 38 49 97 76 13 65 49 13 27 38 49 49 65 76 97 49 65 13 27 38 49 49 65 76 97 high ↑ ↑ Low ← ↑ high ↑ Low → ↑ Low ↑ high ↑ Low ↑ high ← ↑ high Pivtkey 27 38 65 97 76 13 49 49 ↑ Low → ↑ Low ↑ high ↑Low ← ↑ high 49 38 65 97 76 13 27 49 一趟 结果 二趟 排序