快速排序（1）

快速排序是经典的排序算法，最理想的情况下，时间复杂度近乎二分法，平均时间复杂度为O（nlogn）
关于快速排序的图解网上有很多，也很容易理解，直接上代码吧

/**
  快速排序 经典版本
  排序过程只需要三步
 （1）在数据集之中，选择一个元素作为"基准"（pivot）。
 （2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
 （3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
 * */
public class QuickSortBasic {

    public void sort(int[] array){
        sort(array, 0, array.length-1);
    }

    private void sort(int[] array, int low, int high){
        //退出条件
        if(low >= high){
            return;
        }
        //枢轴，默认取数组第一个元素
        int pivot = array[low];
        //i 为左下标，从左递增寻找大于枢轴的数字
        //j 为右下标，从右递减寻找小于枢轴的数字
        int i = low;
        int j = high;

        while (i<j){
            while (i<j && array[j] >= pivot){
                j--;
            }
            while (i<j && array[i] <= pivot){
                i++;
            }
            if(i<j){
                SortUtils.swap(array, i, j);
            }
        }
        //j位置，左侧都小于等于枢轴，右侧都大于等于枢轴
        SortUtils.swap(array, low, j);

        sort(array, low, j-1);
        sort(array, j+1, high);
    }
}

    public static void main(String[] args){
        //49, 38, 65, 97, 76, 13, 27
        //6,3,4,2,1,4,5,6
        //3,1,3,2,3,7,3,3,2,5
        int[] datas = {3,1,3,2,3,7,3,3,2,5};

        QuickSortBasic sortBasic = new QuickSortBasic();
        sortBasic.sort(datas);
        System.out.println(SortUtils.intArrayToString(datas));
    }

输出结果为

1,2,2,3,3,3,3,3,5,7