算法篇-排序

快排

算法思想：每次找一个基数，然后对数组左右遍历，将小于基数的数据放到左边，大于基数的数放到右边，然后将基数左边，右边进行迭代再排序。

public static void quickSort(int[] nums, int left, int right) {if (left >= right) {return;}// 基准数字int base = nums[left];// 左右游标int low = left;int high = right;while (low < high) {while (low < high && nums[high] > base) {high--;}nums[low] = nums[high];while (low < high && nums[low] <= base) {low++;}nums[high] = nums[low];}nums[low] = base;quickSort(nums, left, low - 1);quickSort(nums, low + 1, right);}

归并排序

归并切实也就听着比较难，其实算法思想还是比较简单的。
算法思想：归并其实就是分治，最终将两个单数进行排序，然后再对有序的数组进行合并即可。两个有序的数组合并，需要开辟额外的空间，双指针遍历两个有序的数组，每次将其中最大的数，放入结果中。

代码：

public static void main(String[] args) {int[] nums = new int[]{8, 4, 5, 7, 1, 3, 6, 2};sort(nums, 0, nums.length - 1);System.out.println(Arrays.toString(nums));}public static void sort(int[] nums, int left, int right) {if (left >= right) {return;}// 分治int mid = (right + left) / 2;sort(nums, left, mid);sort(nums, mid + 1, right);// 合并merge(nums, left, mid, right);}public static void merge(int[] nums, int left, int mid, int right) {// 需要临时开辟空间int[] tmps = Arrays.copyOfRange(nums, left, right + 1);int i = left;int j = mid + 1;for (int k = left; k <= right; k++) {if (i > mid) {nums[k] = tmps[j - left];j++;} else if (j > right) {nums[k] = tmps[i - left];i++;} else if (tmps[i - left] < tmps[j - left]) {nums[k] = tmps[i - left];i++;} else {nums[k] = tmps[j - left];j++;}}}

双指针排序思想

笔试题中有很多有序的数组，然后根据有序的特性去做一些事情，比如下面这个题：
一个非递减数组[-4,-3,-2,-1,0,1,2,3,4,5]，对每个元素进行平方，然后重新排序得到新的非递减数组。我们可以观察平方后的数组是什么？
解题思路：

1. 平方运算后的数组[16,9,4,1,0,1,4,9,16,25]
2. 我们观察这个数组有什么特点，两边大中间小
3. 采用爽指针从左右遍历， 每次取最大的元素

代码：

public static void main(String[] args) {int[] nums = new int[]{-4,-3,-2,-1,0,1,2,3,4,5};System.out.println(Arrays.toString(nums));int l = 0;int r = nums.length - 1;int[] result = new int[nums.length];int i = r;while (i >= 0) {int left = nums[l] * nums[l];int right = nums[r] * nums[r];if (left < right) {result[i] = right;r--;} else {result[i] = left;l++;}i--;}System.out.println(Arrays.toString(result));}