Java编程中快速排序算法的实现及相关算法优化

时间复杂度

平均情况：O(nlgn)
最坏情况：O(n*n)，发生在当数据已经是排序状态时
快排算法的基本原理

1、从数据中选取一个值a[i]作为参考
2、以a[i] 为参考，将数据分成2部分：P1、P2，P1中的数据全部≤a[i]，P2中的数据全部＞a[i]，数据变为｛｛P1｝｛a[i]｝｛P2｝｝
3、将P1、P2重复上述步骤，直到各部分中只剩1个数据
4、数据完成升序排列

基本示例：

原始数据：

  ｛3，9，8，5，2，1，6｝

第1步：选取第1个数据：3
第2步：将数据分成2部分，左边≤3，右边大于>3：

  ｛2，1｝ ｛3｝ ｛9，8，5，6｝

第3步：将各部分重复以上步骤，直到每部分只剩1个数据：

  ｛2，1｝ => ｛1｝ ｛2｝
  ｛9，8，5，6｝ => ｛8，5，6｝ ｛9｝=> ｛5，6｝ ｛8｝ ｛9｝=> ｛5｝ ｛6｝ ｛8｝ ｛9｝

第4步：数据完成升序排列：

  ｛1｝ ｛2｝ ｛3｝ ｛5｝ ｛6｝ ｛8｝ ｛9｝

程序中数据通常保存在数组中，以int类型的数组为例，可以将上面的步骤写成一个quickSort函数原型：

quickSort(int begin, int end) {
//begin为数组的第一个数据的索引值，end为数组的最后一个数据的索引值+1
  //如果只有1个数据或0个数据，则程序返回
  if( begin == end || begin == (end-1) ) return;
  int p = in[begin];//p为选择的参考数据，选择第一个数据
  int a = begin +1; //a作为2部分数据分界线的索引值
  int b = a;//b为待比较的数据的索引值
  for( ; b < end; b++) {//将数组中的各个数据依次与参考数据进行比较
    if( in[b] < p) { //如果该数据<参考数据则将其移动到左边
      if(a == b){a++; continue;} //如果该数据已经在左边则不动
      int temp = in[a];//将数据移动到左边
      in[a] = in[b];
      in[b] = temp;
      a++;//将分界线右移
    }
  }
  in[begin] = in[a-1];//讲参考值移动到2组数据中间
  in[a-1] = p;
  if( a-1 > begin){ // 如果左边有数据则将其重复上述步骤
    quickSort(begin, a);
  }
  if( end-1 > a ) {// 如果右边有数据则将其重复上述步骤
    quickSort(a, end);
  }
  return; // 如果无数据返回
}

算法优化
上面这个快速排序算法可以说是最基本的快速排序，因为它并没有考虑任何输入数据。但是，我们很容易发现这个算法的缺陷：这就是在我们输入数据基本有序甚至完全有序的时候，这算法退化为冒泡排序，不再是O(n㏒n)，而是O(n^2)了。
究其根源，在于我们的代码实现中，每次只从数组第一个开始取。如果我们采用“三者取中”，即arr[low],arr[high],arr[（low+high）/2]三者的中值作为枢轴记录，则可以大大提高快速排序在最坏情况下的性能。但是，我们仍然无法将它在数组有序情形下的性能提高到O(n)。还有一些方法可以不同程度地提高快速排序在最坏情况下的时间性能。

此外，快速排序需要一个递归栈，通常情况下这个栈不会很深，为log(n)级别。但是，如果每次划分的两个数组长度严重失衡，则为最坏情况，栈的深度将增加到O(n)。此时，由栈空间带来的空间复杂度不可忽略。如果加上额外变量的开销，这里甚至可能达到恐怖的O(n^2)空间复杂度。所以，快速排序的最差空间复杂度不是一个定值，甚至可能不在一个级别。
为了解决这个问题，我们可以在每次划分后比较两端的长度，并先对短的序列进行排序（目的是先结束这些栈以释放空间），可以将最大深度降回到O(㏒n)级别。

这里提出对快速排序的3点优化思路：
对于小数组，可以采用插入排序，避免递归调用。例如，当if(hi <= lo + M)时，就可以转到插入排序。
采用子数组的一部分元素的中位数来切分数组。这样做得到的切分更好，但代价是需要计算中位数。
如果数组中含有大量的重复元素，可以采用三向切分。将数组切分为三部分，分别对应于小于、等于和大于切分元素的数组元素。代码实现如下：

  private static void sort1(int[] a, int lo, int hi) {
  if (hi <= lo)
    return;
  int lt = lo, i = lo + 1, gt = hi;
  int v = a[lo];
  while (i <= gt) {
    if (a[i] < v) {
      swap(a, lt++, i++);
    } else if (a[i] > v) {
      swap(a, i, gt--);
    } else {
      i++;
    }
    sort(a, lo, lt - 1);
    sort(a, gt + 1, hi);
  }
}