【排序】快排-1

// 参考《算法导论》上的伪代码
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）