快速排序是经典的排序算法，最理想的情况下，时间复杂度近乎二分法，平均时间复杂度为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
