八大排序之快速排序

动画演示：

 思路：

        1、从数组中选一个数做为基准值，一般选第一个数，或者最后一个数。
        2、采用双指针(头尾两端)遍历，从左往右找到比基准值大的第一个数，从右往左找到比基准值小的第一个数，交换两数位置，直到头尾指针相等或头指针大于尾指针，把基准值与头指针的数交换。这样一轮之后，左边的数就比基准值小，右边的数就比基准值大。
        3、对左边的数列递归操作，对右边数列递归操作
        4、数列递归结束后，排序完成。

代码演示：

public class QuickSort {
    public static void main(String[] args) {
        int[]arr = new int[]{2,6,3,4,9,8};
        sort(arr,0,arr.length-1);
        print(arr);
    }

    private static void sort(int[] arr,int left,int right)
    {
        if(arr == null || arr.length < 2) return;
        quickSort(arr,left,right);

    }

    private static void quickSort(int[] arr, int left, int right) {
        //递归终止条件
        if (left > right) {
            return;
        }
        int i = left;
        int j = right;
        //找一个基准值（选择左边了）
        int point = arr[left];
        //双指针遍历
        while (i < j) {
            while (i < j && arr[j] > point) {
                j--;
            }
            while (i < j && arr[i] <= point) {
                i++;
            }
            if (i < j) {
                swap(arr,i,j);
            }
        }
        //一遍过后，i=j，且该索引位置左边都是小于等于point,右边都是大于point，将point和该索引交换元素
        swap(arr,left,i);
        //递归左边
        quickSort(arr, left, i - 1);
        //递归右边
        quickSort(arr, i + 1, right);

    }
    
    private static void swap(int []arr,int left,int right)
    {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    private static void print(int[] arr) {
        for(int i=0;i<arr.length;i++)
        {
            System.out.print(arr[i]+" ");
        }
    }
}

算法复杂度：O(nlogn)
算法空间复杂度：O(1)
算法稳定性：不稳定