快速排序

快速排序

时间复杂度：平均时间复杂度为O(NlogN)。

思路： 每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。

快速排序.gif

代码实现

public class 快速排序 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int array[] = {9,1,5,3,7,8,2,6,4};
        kuaiSu(array,0,array.length-1);
    }
    
    
    public static void kuaiSu(int []array,int left,int right){
        if(left < right) {
            int i=left,j=right;
            int pivot = array[left];//选择最左边的元素作为中间值

        /**
         * 分治
         */
        while(i < j) {
            while(i < j && array[j] >= pivot) {
                j--;
            }
            if(i < j) {
                array[i] = array[j];
                i++;
            }
            while(i < j&& array[i] < pivot){
                i++;
            }
            if(i < j) {
                array [j] =array [i];
                j--;
            }
        }
        array [i]=pivot;
        //递归
        kuaiSu(array,left,i-1);
        kuaiSu(array,i+1,right);
        }
    }

}