template <class Record, class Compare> void QuickSorter<Record, Compare> Sort(Record Array[, int left, int right) 排序数组,i分别为数组两端 轴值选择函数 0成1个记录,就不需排序 ( right<=left) return;//只有o或1个记录 template <class Record, class Compare> nt pivot= SelectPivot( left, right);//选择轴值 int QuickSorter<Record, Compare> //分割前先将轴值放到数组末端 SelectPivot(int left, int right) //参数 left, right分别表示序列的左右端下标 //对剩余的记录进行分割 /选择中间纪录作为轴值 rtition(Array, left, right) return(left+right)/2; /对轴值左边的子序列进行递归快速排序 t(Array, left, pivot-1) /对轴值右边的子序列进行递归快速排序 ▲啦张铭写 北大单张铭写 叔新有,命邮 分割函数 template <class record, class Compare> int QuickSorter <Record, Compare> while(!= j /i右移,直到找到一个大于等于轴值的记录 Partition( Record Array], int left, int right) //分割函数,分割后轴值已到达正确位置 while(Compare:lt(Array[], TempRecord) &&>) Record TempRecord;//存放轴值 inti=left//i为左指针,j为右指针 //若订未相遇就将逆序元素换到右边空闲位置 intj= right if (i<j) //将轴值存放在临时变量中 Array u]= arrays] TempRecord Array ll: //j指针向左移动 //开始分割,i不断向中间移动,直到相遇 北真大脆张写 真大影张帖写 叔新有,量究 //左移,直到找到一个小于等于轴值的记录 while(Compare: : gt(Array, TempRecord) > 时间代价 如未相遇就将逆序元素换到左边空闲位置 长度为n的序列,时间为Tn) if (i<jt Array[] array l]; T(0)=T(1)=1 i++;/f指针向右移动一步 ■选择轴值时间为常数 分割时间为cn /把轴值回填到分界位置让上 分割后长度分别为i和n-i-1 Array[]= TempRecor 对子序列进行快速排序所需时间分别 return i /返回分界位置i 为T()和T(n-1-i) 北真大学张铭编写 聊张帖写 权新有,究 1212 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 67 template <class Record,class Compare> void QuickSorter<Record,Compare>:: Sort(Record Array[], int left,int right) { //Array[]为待排序数组，i,j分别为数组两端 // 如果子序列中只有0或1个记录，就不需排序 if (right <= left) return; // 只有0或1个记录， int pivot = SelectPivot(left, right); //选择轴值 //分割前先将轴值放到数组末端 swap(Array, pivot, right); // 对剩余的记录进行分割 pivot = Partition(Array, left, right); //对轴值左边的子序列进行递归快速排序 Sort(Array, left, pivot-1); //对轴值右边的子序列进行递归快速排序 Sort(Array, pivot +1, right); } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 68 轴值选择函数 template <class Record,class Compare> int QuickSorter<Record,Compare>:: SelectPivot(int left,int right) { //参数left,right分别表示序列的左右端下标 //选择中间纪录作为轴值 return (left+right)/2; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 69 分割函数 template <class Record,class Compare> int QuickSorter<Record,Compare>:: Partition(Record Array[], int left,int right) { //分割函数，分割后轴值已到达正确位置 Record TempRecord; //存放轴值 int i = left; // i为左指针，j为右指针 int j = right; //将轴值存放在临时变量中 TempRecord = Array[j]; //开始分割，i,j不断向中间移动，直到相遇 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 70 while (i != j) { //i右移，直到找到一个大于等于轴值的记录 while (Compare::lt(Array[i], TempRecord) && (j>i)) i++; // 若i,j未相遇就将逆序元素换到右边空闲位置 if (i<j) { Array[j] = Array[i]; j--; //j指针向左移动一步 } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 71 //j左移，直到找到一个小于等于轴值的记录 while (Compare::gt(Array[j], TempRecord) && (j > i)) j--; //如果i,j未相遇就将逆序元素换到左边空闲位置 if (i<j) { Array[i] = Array[j]; i++; //i指针向右移动一步 } } //把轴值回填到分界位置i上 Array[i] = TempRecord; return i; //返回分界位置i } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 72 时间代价 „ 长度为n的序列，时间为T(n) „ T(0) = T(1) =1 „ 选择轴值时间为常数 „ 分割时间为cn „ 分割后长度分别为 i 和 n-i-1 „ 对子序列进行快速排序所需时间分别 为T(i)和T(n-1-i)