排序之一：快速排序

• 介绍
  快速排序又称分割交换排序法，是目前公认最佳的排序法。它的原理和冒泡排序法一样都是用交换的方式，不过它会现在数据中找到一个虚拟的中间值，把小于中间值的数据放在左边，而大于中间值的数据放在右边，再以同样的方式分别处理左右两边的数据，直到完成为止。
• 演示
  代码如下：

private static void quickSort(int arr[], int low, int high) {
    int l = low, h = high, povit = arr[low], tmp;
    while (l < h) {
        while (l < h && arr[h] >= povit) h--;
        if (l < h) {
            tmp = arr[h];
            arr[h] = arr[l];
            arr[l] = tmp;
            l++;
        }
        while (l < h && arr[l] <= povit) l++;
        if (l < h) {
            tmp = arr[h];
            arr[h] = arr[l];
            arr[l] = tmp;
            h--;
        }
    }
    if (l > low) quickSort(arr, low, l - 1);
    if (h < high) quickSort(arr, l + 1, high);
}

运行效果：

快速排序运行效果.png

• 分析

1. 在最快及平均情况下，时间复杂度为O(nlog底数为2 的n)。最坏情况就是每次挑中的中间值不是最大就是最小，起时间复杂度为O(n²)；
2. 不是稳定排序法；
3. 在最差的情况下，空间复杂度为O(n)，而最佳情况为O(log以2为底的n)；

---

其他排序：插入排序、选择排序、冒泡排序、希尔排序、基数排序