快速排序

过程

我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

动图展示

代码实现

/**
 * 快速排序
 */

public class QuickSort {

    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //选取中轴元素
            int pivot = arr[left];
            int i = left + 1;
            int j = right;
            while (true) {
                //从右边找到第一个小于等于 pivot 的元素位置
                while (i <= j && arr[j] >= pivot) j--;
                //从左边找到第一个大于等于 pivot 的元素位置
                while (i <= j && arr[i] <= pivot) i++;
                if (i >= j) {
                    break;
                }
                //交换两个元素的位置，使得左边的元素不大于pivot,右边的不小于pivot
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            arr[left] = arr[j];
            //使中轴元素处于有序的位置
            arr[j] = pivot;
            //递归排序左子数组
            quickSort(arr, left, j - 1);
            //递归排序右子数组
            quickSort(arr, j + 1, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 3, 1, 4, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

}

性质：

1. 时间复杂度：O(nlogn)
2. 空间复杂度：O(logn)
3. 非稳定排序
4. 原地排序

参考

• 冒泡排序
• 十大经典排序算法动画与解析