交换排序之-快速排序

算法概述/思路

快速排序一般基于递归实现。其思路是这样的：

1. 选定一个合适的值（理想情况中值最好，但实现中一般使用数组第一个值）,称为“枢轴”(pivot)。
2. 基于这个值，将数组分为两部分，较小的分在左边，较大的分在右边。
3. 可以肯定，如此一轮下来，这个枢轴的位置一定在最终位置上。
4. 对两个子数组分别重复上述过程，直到每个数组只有一个元素。
5. 排序完成。

下面是快速排序的示意图（图片来自维基百科）：

Sorting_quicksort_anim.gif

算法详解 解说部分转自《坐在马桶上看算法》

快排.png

JAVA代码

public class QuickSort {
  public static void main(String[] args) {
    int[] arr = {9, 10, 3, 5, 4, 6, 2, 8, 1, 7};
    qsort(arr, 0, arr.length - 1);
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
  }

  private static void qsort(int[] arr, int low, int high) {
    if (low < high) {
      int pivot = partition(arr, low, high);        //将数组分为两部分
      qsort(arr, low, pivot - 1);                   //递归排序左子数组
      qsort(arr, pivot + 1, high);                  //递归排序右子数组
    }
  }

  private static int partition(int[] arr, int low, int high) {
    int pivot = arr[low];     //枢轴记录
    while (low < high) {
      while (low < high && arr[high] >= pivot) {
        --high;
      }
      arr[low] = arr[high];             //交换比枢轴小的记录到左端
      while (low < high && arr[low] <= pivot) {
        ++low;
      }
      arr[high] = arr[low];           //交换比枢轴小的记录到右端
    }
    //扫描完成，枢轴到位
    arr[low] = pivot;
    //返回的是枢轴的位置
    return low;
  }
}

算法性能/复杂度

可以看出，每一次调用partition()方法都需要扫描一遍数组长度（注意，在递归的时候这个长度并不是原数组的长度n，而是被分隔出来的小数组，即n*2^(-i)，其中i为调用深度。而在这一层同样长度的数组有2⁽ⁱ⁾个。那么，每层排序大约需要O(n)复杂度。而一个长度为n的数组，调用深度最多为log(n)层。二者相乘，得到快速排序的平均复杂度为O(n㏒n)。

通常，快速排序被认为是在所有同数量级的排序方法中，平均性能最好。

从代码中可以很容易地看出，快速排序单个栈的空间复杂度不高，每次调用partition方法时，其额外开销只有O(1)。所以，最好情形下快速排序空间复杂度大约为O(㏒n)。