快速排序

平均时间复杂度:O(N logN)

package com.bj.zl.learn.sort;

/**
 * 快速排序
 *
 * 思路
 * 取任一一个元素为目标元素,然后用目标元素与其他元素进行比较
 * 比目标元素大的放在右边,小的放在左边.
 * 然后对左子树和右子树做以上递归调用,直到左子树和右子树只剩下一个元素为止
 *
 */
public class QuickSort {


    public static void main(String[] args) {

        int[] arr = {50,88,79,52,548,1,2,7,5,69};
        quickSort(arr,0,arr.length-1);
        for (int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }

    }

    private static void quickSort(int[] arr,int left,int right){
        int r =right;
        int l =left;
        int base = arr[left];
        while (left < right){
            while (left<right && arr[right] >= base){
                right--;
            }
            arr[left] =arr[right];

            while (left<right && arr[left] <=base){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] =base;

        if (left < r){
            quickSort(arr,right+1,r);
        }
        if (right > l){
            quickSort(arr,l,left-1);
        }
    }
}