轴值选择 分割过程( Partition) ■尽可能使L,R长度相等 ■整个快速排序的关键,轴值位于 ■选择策略: 正确位置,分割后使得 选择最左边记录 nL中所有记录位于轴值左边 随机选择 ■R中记录位于轴值右边 选择平均值 举位▲张倍墙写 北大单张铭写 叔新有,命邮 2534453278122964 次分割过程 25344564781229B2 选择轴值并存储轴值 i J 最后一个元素放到轴值位置 初始化下标j,分别指向头尾 25344564781229 i递增直到遇到比轴值大的元素,将此元素援 道到遇到比轴值小的元素,将此元素覆 456478122934 复上一步直到==,将轴值放到的位 25294647812 34 北真大脆张写 版叔斯有就即究 6478124534 快速排序算法 template <class Record, class Compare> 2529126478 4534 Sorter<Record Public 值下标 252912l6478644534 int SelectPivot(int left, int right); /分割返回轴值位量 Partition(Record Array[], int left, int right); void Sort(Record Array[],int left, int right); 2529123278644534 聊张帖写 权新有,究11 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 61 轴值选择 „ 尽可能使L，R长度相等 „ 选择策略： „ 选择最左边记录 „ 随机选择 „ 选择平均值 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 62 分割过程（Partition） „ 整个快速排序的关键，轴值位于 正确位置，分割后使得 „ L中所有记录位于轴值左边 „ R中记录位于轴值右边 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 63 一次分割过程 „ 选择轴值并存储轴值 „ 最后一个元素放到轴值位置 „ 初始化下标i, j，分别指向头尾 „ i递增直到遇到比轴值大的元素，将此元素覆 盖到j的位置； j递减直到遇到比轴值小的元素，将此元素覆 盖到i的位置 „ 重复上一步直到i==j，将轴值放到i的位 置，完毕 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 64 25 34 45 32 78 12 29 64 25 34 45 64 78 12 29 32 i j 25 34 45 64 78 12 29 32 i j 25 34 45 64 78 12 29 34 i j 25 29 45 64 78 12 29 34 i j 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 65 25 29 45 64 78 12 45 34 i j 25 29 12 64 78 12 45 34 i j 25 29 12 64 78 64 45 34 ij 25 29 12 32 78 64 45 34 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 66 快速排序算法 template <class Record,class Compare> class QuickSorter:public Sorter<Record,Compare> { //快速排序类 private: //选择轴值，返回轴值下标 int SelectPivot(int left, int right); //分割,返回轴值位置 int Partition(Record Array[], int left, int right); public: void Sort(Record Array[],int left,int right); };