Day60.算法训练

912. 排序数组

• 归并排序

class Solution {public int[] sortArray(int[] nums) {int lo = 0;int hi = nums.length - 1;int[] assist = new int[nums.length];sortArray(nums, assist, lo, hi);return nums;}private void sortArray(int[] nums, int[] assist, int lo, int hi) {if (lo >= hi) {return;}int mid = lo + (hi - lo) / 2;sortArray(nums, assist, lo, mid);sortArray(nums, assist, mid + 1, hi);merge(nums, assist, lo, mid, hi);}private void merge(int[] nums, int[] assist, int lo, int mid, int hi) {int p1 = lo;int p2 = mid + 1;int i = lo;while (p1 <= mid && p2 <= hi) {if (lessCmp(nums[p1], nums[p2])) {assist[i++] = nums[p1++];} else {assist[i++] = nums[p2++];}}while (p1 <= mid) {assist[i++] = nums[p1++];}while (p2 <= hi) {assist[i++] = nums[p2++];}for (int index = lo; index <= hi; index++) {nums[index] = assist[index];}}private boolean lessCmp(Comparable a, Comparable b) {return a.compareTo(b) < 0;}
}

• 快速排序

class Solution {public int[] sortArray(int[] nums) {int lo = 0;int hi = nums.length - 1;sortArray(nums, lo, hi);return nums;}private void sortArray(int[] nums, int lo, int hi) {if (lo >= hi) {return;}int partion = partion(nums, lo, hi);sortArray(nums, lo, partion - 1);sortArray(nums, partion + 1, hi);}private int partion(int[] nums, int lo, int hi) {int k = nums[lo];int left = lo;int right = hi + 1;while (true) {while (right > 0 && gtCmp(nums[--right], k)) {if (right == lo) {break;}}while (left < hi && leCmp(nums[++left], k)) {if (left == hi) {break;}}if (left == right) {break;}exch(nums, left, right);}exch(nums, lo, right);return right;}private void exch(int[] nums, int left, int right) {int a = nums[left];nums[left] = nums[right];nums[right] = a;}private boolean leCmp(Comparable a, Comparable b) {return a.compareTo(b) < 0;}private boolean gtCmp(Comparable a, Comparable b) {return a.compareTo(b) > 0;}}