// 参考《算法导论》上的伪代码
public void quickSort(int[] num, int begin, int end) {
if(begin<end){
int center = partition(num, begin, end);
quickSort(num, begin, center-1);
quickSort(num, center+1, end);
}
}
pubic int partition(int[] num, int begin, int end) {
int index = num[end];
int i = begin - 1;
for(int j=begin; j<end; j++) {
if(num[j]<=index) {
i++;
exchange(num, i, j);
}
}
exchange(num, i+1, end);
return i+1;
}
- 最坏情况：
，当两个子集出现了包含
和
个元素的划分
- 最好情况：
，可能的最平衡划分中两个子问题的规模都不大于
- 如何改进？关键在于选取哪个元素作为枢纽（pivot）
