分治法
递归解决问题的方法
分治的过程
1，找出基线条件，这种条件必须尽可能简单
2，不断将问题分解（或者缩小规模），知道符合基线条件
快速排序
分区
- 一个由所有小于基准值的数字组成的子数组
- 基准值
- 一个由所有大于基准值的数据组成的子数组
public static void sort(int[] arr, int left, int right) {
if (left > right) {
return;
}
int i, j,temp;
temp = arr[left];//存储基准值
i = left;
j = right;
while (i != j) {
//从右边开始找,找到比基准值大的就j--
while (i < j && arr[j] >= temp) {
j--;
}
//从左边开始找，找到比基准值小的就i++
while (i < j && arr[i] <= temp) {
i++;
}
//交换i ,j位置
if (i < j) {
Utils.exchange(arr, i, j);
}
}
//将基数归位
arr[left] = arr[i];
arr[i] = temp;
//递归调用
sort(arr, left, i - 1);
sort(arr, i + 1, right);
}
时间复杂度 O(NlogN) 最糟糕情况下O(N²)
