快速排序

快速排序，顾名思义，它的效率是比较高的。快速排序采用的思想是分治法，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序涉及到3个步骤：

1. 从待排序数中选取一个数作为基准数；
2. 排序过程中，将比基准数小的数放到左边，比基准数大的数放到右边；
3. 重复过程2，直到各区间只有一个数。

假设有数列 a = [5, 6, 2, 0, 5]。

根据快速排序思想，可以有多种实现方式，这里列举两种实现方式：

• 一次交换一个数的排序
  选取数列的第一个数作为基准数（这里用 b 表示），用 i 表示从左往右扫描，用 j 表示从右往左扫描。因为基准数选取的是左边第一个数，所以必须先用 j 从右往左扫描。j 在扫描的过程中如果发现 a[j] 小于基准数，则将 a[j] 处的值复制到 a[i] ，并且 i 往右移动一位；同理，i 在扫描的过程中如果发现 a[i] 大于基准数，则将 a[i] 处的值复制到 a[j] ，并且 j 往左移动一位。直到 i = j，再将基准数的值复制到 a[j] 即可。在这个过程中，因为基准数的值在开始前已经拷贝出来了，所以不用担心基准数的值会丢失。
  详细步骤如下：

步骤 \ 索引	0	1	2	3	4
初始，基准数 b=a[i]=a[0]=5	5	6	2	0	5
i=0，j=4，先用 a[j] 跟基准数 b 比较,因为 a[j] 不小于 b，所以 j 继续移动，j--	5	6	2	0	5
i=0，j=3，因为 a[j] < b，所以 a[i] = a[j]，a[i] 原来的值已经在 b 处不会丢失，i++	0	6	2	0	5
i=1，j=3，因为 a[i] > b，所以 a[j] = a[i]，a[j] 原来的值已经在 a[0] 处不会丢失，j--	0	6	2	6	5
i=1，j=2，因为 a[j] < b，所以 a[i] = a[j]，a[i] 原来的值已经在 a[3] 处不会丢失，i++	0	2	2	6	5
i=2，j=2，因为 i = j，所以把 b 放入 a[j] 处，a[j] 原来的值已经在 a[1] 处不会丢失	0	2	5	6	5

此时，基准数a[0]已经归位，可以看到此时a[2]左边的数都不大于a[2]，a[2]右边的数都不小于a[2]。然后再对a[0~1] 和 a[3~4] 分别重复上述过程，即可完成所有排序。其实每一次的递归排序就是各个基准数归为的过程，直到所有的基准算归位，则排序结束。

• 一次交换两个数的排序
  这个实现方式跟前一个实现方式大体类似，不同点在于，一次交换一个数的排序是每当发现一个数（不管是 i 扫描的还是 j 扫描的）比基准数大或者小时，就马上进行值的交换；而一次交换两个数的排序是要先找到右边的数（j 扫描的）小于基准数，并且再等左边的数（i 扫描的）大于基准数时，才会进行值的交换，这时候直接交换 a[i] 和 a[j] 的值即可。由于过程跟前一个实现方式类似，就不进行赘述了，直接看下方的代码。

代码实现如下：

• 快速排序

public class QuickSort {
    public static void main(String[] args) {
        int[] data = new int[] {5, 6, 2, 0, 5};
        sortBySwapOneAtATime(data, 0, 4);
        for (int i = 0, size = data.length; i < size; i++) {
            System.out.println(data[i]);
        }
    }

    /**
     * 一次交换一个数的排序
     */
    public static void sortBySwapOneAtATime(int[] data, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = left, j = right, baseNumber = data[left];
        while (i != j) {
            while (data[j] >= baseNumber && i < j) {
                j--;
            }
            if (i < j) {
                data[i] = data[j];
                i++;
            }
            while (data[i] <= baseNumber && i < j) {
                i++;
            }
            if (i < j) {
                data[j] = data[i];
                j--;
            }
        }
        data[i] = baseNumber;
        sortBySwapOneAtATime(data, left, i - 1);
        sortBySwapOneAtATime(data, i + 1, right);
    }

    /**
     * 一次交换两个数的排序
     */
    public static void sortBySwapTwoAtATime(int[] data, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = left, j = right, temp;
        while (i != j) {
            while (data[j] >= data[left] && i < j) {
                j--;
            }
            while (data[i] <= data[left] && i < j) {
                i++;
            }
            if (i < j) {
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
        temp = data[left];
        data[left] = data[i];
        data[i] = temp;

        sortBySwapTwoAtATime(data, left, i - 1);
        sortBySwapTwoAtATime(data, i + 1, right);
    }
}

运行结果：
0
2
5
5
6

当然，选取最左边的第一个数作为基准数不是必须的，也可以选取其他位置的数作为基准数，选取其他位置的数作为基准数就需要调整一下算法实现了。

快速排序的最差的时间复杂度为 O(N^2)，平均时间复杂度为 O(N*logN)。