一天一个算法之快速排序

是什么？

快速排序是对冒泡排序的一种改进；

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都小于或者等于另外一部分的所有数据，然后再按照此方法对这两部分数据分别进行快速排序，整个排序的过程可以递归进行，以此达到整个数据变成有序序列。

复杂度？

平均时间：O(nlogn)

空间：O(1)

java demo

public class FastSort {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 6, 1, 2, 4, 7};
        for (int i : arr) {
            System.out.print(i + " ");//排序前数组
        }
        System.out.println();
        quicksort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");//排序后数组
        }
    }

    private static void quicksort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int base = arr[start];//定义基准值
        int left = start;//开始位置下标
        int right = end;//末尾位置下标
        while (left < right) {
            // 从右往左，找到比base小的值的index
            while (left < right && arr[right] >= base) {
                right--;
            }
            // 从左往右，找到比base大的值的index
            while (left < right && arr[left] <= base) {
                left++;
            }
            if (left < right) {//交换i和j的值
                int temp = arr[right];
                arr[right] = arr[left];
                arr[left] = temp;
            }
        }
        arr[start] = arr[left];
        arr[left] = base;
        quicksort(arr, start, left - 1);//递归调用
        quicksort(arr, left + 1, end);
    }
}