算法思想

通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

算法步骤如下:

  • 从数列中挑出一个元素,称为 “基准”(pivot );
  • 步骤2:重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  • 步骤3:递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码思路

public static void quickSort(int[] array, int start, int end) {
  if (start < end) {
    //默认用第一个数做基准
    int i = start;
    int j = end;
    int pivot = array[start];
    while (i < j) {
      // 从右向左找第一个小于基准的数
      while (i < j && array[j] >= pivot) {
        j--;
      }
      if (i < j) {
        array[i++] = array[j];
      }
      // 从左向右找第一个大于等于基准的数
      while (i < j && array[i] < pivot) {
        i++;
      }
      if (i < j) {
        array[j--] = array[i];
      }
    }
    array[i] = pivot;
    quickSort(array, start, i - 1);
    quickSort(array, i + 1, end);
  }

}

复杂度分析

  • 最佳情况:T(n) = O(nlogn)
  • 最差情况:T(n) = O(n2)
  • 平均情况:T(n) = O(nlogn)
最后修改:2020 年 10 月 13 日 12 : 00 PM