引言
说到常见的算法>排序算法，那肯定少不了快速排序和归并排序，因为这两个都是时间复杂度为Ologn的算法>排序算法，下面来说说这两种算法的思路以及注意事项
快速排序
思路
- 任意选取一个数记为pivot
- 对数组进行划分，根据选取的pivot将数组划分成小于pivot的部分和大于pivot的部分
- 递归求解小于pivot和大于pivot的部分
思考：2个数有序的定义是不是就是 左边的数小于右边的数，或者3个数有序的定义是不是就是，中间的那个数大于左边，小于右边，
所以可以猜到，快速排序核心其实就是递归到最小序列使其有序，使每一段序列都满足划分规则，到最后那就是整个序列有序
代码
class Solution {public int[] sortArray(int[] nums) {quickSort(nums,0,nums.length-1);return nums;}private void quickSort(int[] nums,int l,int r) {if (l >= r) return;int i = l,j = r;int pivot = nums[ThreadLocalRandom.current().nextInt(r - l + 1) + l];while(i<=j) {while(nums[i] < pivot) {i++;}while(nums[j] > pivot) {j--;}if(i <= j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;i++;j--;}}quickSort(nums, l, j); quickSort(nums, i, r); }}
归并排序
思路
分解（递归）阶段
- 将待排序数组不断二分，直到无法再分（每个子数组只有一个元素）
- 单个元素的数组天然是有序的，这是递归的"基本情况"
合并阶段
- 将两个已排序的子数组合并成一个有序数组
- 从最小的子数组开始，逐层向上合并
- 合并过程中保持元素的有序性
static void mergeSort(int[] nums, int l, int r) {if (l >= r) return;int mid = l + r >> 1;mergeSort(nums, l, mid);mergeSort(nums, mid + 1, r);int[] tmp = new int[r - l + 1];int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r) {if (nums[i] <= nums[j]) {tmp[k++] = nums[i++];} else {tmp[k++] = nums[j++];}}while (i <= mid) {tmp[k++] = nums[i++];}while (j <= r) {tmp[k++] = nums[j++];}for (int ii = l, jj = 0; ii <= r; ii++, jj++) {nums[ii] = tmp[jj];}}
