原理

  • 通过分治的方式进行排序

  • 步骤

    • 将数列划分为两部分（保证相对大小关系）
    • 递归到两个子序列中分别进行快速排序
    • 不用合并，数列已经完全有序

      性质

  • 稳定性：不稳定

  • 时间复杂度
    • 最优和平均：快速排序 - 图1
    • 最坏：快速排序 - 图2

      代码

      1. public void quick_sort(int[] a, int left, int right) {
      2. if (left > right) {
      3.    return;
      4. }
      5. int midValue = a[left];
      6. int low = left;
      7. int high = right;
      8. while (low < high) {
      9.    while (low < high && a[high] >= midValue) {
      10.        high--;
      11.    }
      12.    a[low] = a[high];
      13.    while (low < high && a[low] < midValue) {
      14.        low++;
      15.    }
      16.    a[high] = a[low];
      17. }
      18. a[low] = midValue;
      19. quick_sort(a, left, low - 1);
      20. quick_sort(a, low + 1, right);
      21. }