本质来说，快速排序的过程就是不断地将无序元素集递归分割，一直到所有的分区只包含一个元素为止。主要就是将数组以一个数组内随机的基准数进行分隔，比基准数小的在左边比基准数大的在右边，即从两侧向内遍历。
排序过程：
- 当遍历右侧有数据小于基准数，停止遍历，来到左侧遍历至有数据大于基准数将。将这两者数据互换。
- 一直到两者 遍历至同一个下标，停止，将基准数与该下标对应的数据互换。
- 现在的状态是基准数左边的都小于基准数，基准数右边的都大于基准数。
- 这时候，我们再以基准数为分割，以同样的方式对基准数左侧及右侧分别排序。
- 以这样递归的方式，一直到基准数左右各只有一个元素停止，这时候排序结束。
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[] { 1, 4, 2, 5, 2, 3, 6, 45, 234, 234, 5435,
546546, 1, 2, 3, 4, 5 };
int[] dividerSort = quickSort(arr);
System.out.print("最终结果："+Arrays.toString(dividerSort));
}
public static int[] quickSort(int[] arr) {
return dividerSort(arr, 0, arr.length-1);;
}
public static int[] dividerSort(int[] arr, int left, int right) {
if(left>right)
return null;
int i=left;
int j = right;
int current = arr[left];
while (i != j) {
while (arr[j] >= current && i < j) {
j--;
}
while (arr[i] <= current && i < j) {
i++;
}
if (i < j) {
toChange(arr, i, j);
}
}
arr[left]=arr[i];
arr[i]=current;
dividerSort(arr, left, i-1);
dividerSort(arr, i+1, right);
return arr;
}
public static int[] toChange(int[] arr, int i, int j) {
int c = arr[j];
arr[j] = arr[i];
arr[i] = c;
return arr;
}
}
时间复杂度：nlog(n)
