快速排序_912. 排序数组（10中排序算法）

给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

1 快速排序（重点）

报错代码

class Solution {public int[] sortArray(int[] nums) {int temp = 0;int pivot = nums[0];int left = 0,right = nums.length-1;sortArray_nums(nums,left,right);}public int[] sortArray_nums(int[] nums,left,right) {while(left < right){while(nums[left]<=pivot){left++;}while(pivot<=nums[right]){right--;}temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}nums[left] = pivot;sortArray_nums(nums,0,left-1);sortArray_nums(nums,right+1,nums.length-1);return nums;}
}  我的快速排序是不是有问题

超时代码

class Solution {public int[] sortArray(int[] nums) {sortArray_nums(nums,0,nums.length-1);return nums;}public void sortArray_nums(int[] nums,int left,int right) {if(left>=right){return;}int l = left,r = right;int pivot = nums[left];int temp = 0;l++;while(l <= r){while(l <= r && nums[l]<=pivot){l++;}while(l <= r && pivot<=nums[r]){r--;}if(l <= r){temp = nums[l];nums[l] = nums[r];nums[r] = temp;l++;r--;}}nums[left] = nums[r];nums[r] = pivot;sortArray_nums(nums,left,r-1);sortArray_nums(nums,r+1,right);}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

修改

class Solution {public int[] sortArray(int[] nums) {sortArray_nums(nums,0,nums.length-1);return nums;}public void sortArray_nums(int[] nums,int left,int right) {if(left>=right){return;}int randomIndex = (left + right)/2;swap(nums, left, randomIndex);int l = left,r = right;int pivot = nums[left];l++;while(l <= r){while(l <= r && nums[l]<=pivot){l++;}while(l <= r && pivot<=nums[r]){r--;}if(l <= r){swap(nums, l, r);l++;r--;}}nums[left] = nums[r];nums[r] = pivot;sortArray_nums(nums,left,r-1);sortArray_nums(nums,r+1,right);}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

官方题解

class Solution {public int[] sortArray(int[] nums) {randomizedQuicksort(nums, 0, nums.length - 1);return nums;}public void randomizedQuicksort(int[] nums, int l, int r) {if (l < r) {int pos = randomizedPartition(nums, l, r);randomizedQuicksort(nums, l, pos - 1);randomizedQuicksort(nums, pos + 1, r);}}public int randomizedPartition(int[] nums, int l, int r) {int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元swap(nums, r, i);return partition(nums, l, r);}public int partition(int[] nums, int l, int r) {int pivot = nums[r];int i = l - 1;for (int j = l; j <= r - 1; ++j) {if (nums[j] <= pivot) {i = i + 1;swap(nums, i, j);}}swap(nums, i + 1, r);return i + 1;}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

快速排序 1：基本快速排序

import java.util.Random;public class Solution {// 快速排序 1：基本快速排序/*** 列表大小等于或小于该大小，将优先于 quickSort 使用插入排序*/private static final int INSERTION_SORT_THRESHOLD = 7;private static final Random RANDOM = new Random();public int[] sortArray(int[] nums) {int len = nums.length;quickSort(nums, 0, len - 1);return nums;}private void quickSort(int[] nums, int left, int right) {// 小区间使用插入排序if (right - left <= INSERTION_SORT_THRESHOLD) {insertionSort(nums, left, right);return;}int pIndex = partition(nums, left, right);quickSort(nums, left, pIndex - 1);quickSort(nums, pIndex + 1, right);}/*** 对数组 nums 的子区间 [left, right] 使用插入排序** @param nums  给定数组* @param left  左边界，能取到* @param right 右边界，能取到*/private void insertionSort(int[] nums, int left, int right) {for (int i = left + 1; i <= right; i++) {int temp = nums[i];int j = i;while (j > left && nums[j - 1] > temp) {nums[j] = nums[j - 1];j--;}nums[j] = temp;}}private int partition(int[] nums, int left, int right) {int randomIndex = RANDOM.nextInt(right - left + 1) + left;swap(nums, left, randomIndex);// 基准值int pivot = nums[left];int lt = left;// 循环不变量：// all in [left + 1, lt] < pivot// all in [lt + 1, i) >= pivotfor (int i = left + 1; i <= right; i++) {if (nums[i] < pivot) {lt++;swap(nums, i, lt);}}swap(nums, left, lt);return lt;}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

快速排序 2：双指针（指针对撞）快速排序

import java.util.Random;public class Solution {// 快速排序 2：双指针（指针对撞）快速排序/*** 列表大小等于或小于该大小，将优先于 quickSort 使用插入排序*/private static final int INSERTION_SORT_THRESHOLD = 7;private static final Random RANDOM = new Random();public int[] sortArray(int[] nums) {int len = nums.length;quickSort(nums, 0, len - 1);return nums;}private void quickSort(int[] nums, int left, int right) {// 小区间使用插入排序if (right - left <= INSERTION_SORT_THRESHOLD) {insertionSort(nums, left, right);return;}int pIndex = partition(nums, left, right);quickSort(nums, left, pIndex - 1);quickSort(nums, pIndex + 1, right);}/*** 对数组 nums 的子区间 [left, right] 使用插入排序** @param nums  给定数组* @param left  左边界，能取到* @param right 右边界，能取到*/private void insertionSort(int[] nums, int left, int right) {for (int i = left + 1; i <= right; i++) {int temp = nums[i];int j = i;while (j > left && nums[j - 1] > temp) {nums[j] = nums[j - 1];j--;}nums[j] = temp;}}private int partition(int[] nums, int left, int right) {int randomIndex = left + RANDOM.nextInt(right - left + 1);swap(nums, randomIndex, left);int pivot = nums[left];int lt = left + 1;int gt = right;// 循环不变量：// all in [left + 1, lt) <= pivot// all in (gt, right] >= pivotwhile (true) {while (lt <= right && nums[lt] < pivot) {lt++;}while (gt > left && nums[gt] > pivot) {gt--;}if (lt >= gt) {break;}// 细节：相等的元素通过交换，等概率分到数组的两边swap(nums, lt, gt);lt++;gt--;}swap(nums, left, gt);return gt;}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

快速排序 3：三指针快速排序

import java.util.Random;public class Solution {// 快速排序 3：三指针快速排序/*** 列表大小等于或小于该大小，将优先于 quickSort 使用插入排序*/private static final int INSERTION_SORT_THRESHOLD = 7;private static final Random RANDOM = new Random();public int[] sortArray(int[] nums) {int len = nums.length;quickSort(nums, 0, len - 1);return nums;}private void quickSort(int[] nums, int left, int right) {// 小区间使用插入排序if (right - left <= INSERTION_SORT_THRESHOLD) {insertionSort(nums, left, right);return;}int randomIndex = left + RANDOM.nextInt(right - left + 1);swap(nums, randomIndex, left);// 循环不变量：// all in [left + 1, lt] < pivot// all in [lt + 1, i) = pivot// all in [gt, right] > pivotint pivot = nums[left];int lt = left;int gt = right + 1;int i = left + 1;while (i < gt) {if (nums[i] < pivot) {lt++;swap(nums, i, lt);i++;} else if (nums[i] == pivot) {i++;} else {gt--;swap(nums, i, gt);}}swap(nums, left, lt);// 注意这里，大大减少了两侧分治的区间quickSort(nums, left, lt - 1);quickSort(nums, gt, right);}/*** 对数组 nums 的子区间 [left, right] 使用插入排序** @param nums  给定数组* @param left  左边界，能取到* @param right 右边界，能取到*/private void insertionSort(int[] nums, int left, int right) {for (int i = left + 1; i <= right; i++) {int temp = nums[i];int j = i;while (j > left && nums[j - 1] > temp) {nums[j] = nums[j - 1];j--;}nums[j] = temp;}}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

2 归并排序（重点）

public class Solution {// 归并排序/*** 列表大小等于或小于该大小，将优先于 mergeSort 使用插入排序*/private static final int INSERTION_SORT_THRESHOLD = 7;public int[] sortArray(int[] nums) {int len = nums.length;int[] temp = new int[len];mergeSort(nums, 0, len - 1, temp);return nums;}/*** 对数组 nums 的子区间 [left, right] 进行归并排序** @param nums* @param left* @param right* @param temp  用于合并两个有序数组的辅助数组，全局使用一份，避免多次创建和销毁*/private void mergeSort(int[] nums, int left, int right, int[] temp) {// 小区间使用插入排序if (right - left <= INSERTION_SORT_THRESHOLD) {insertionSort(nums, left, right);return;}int mid = left + (right - left) / 2;// Java 里有更优的写法，在 left 和 right 都是大整数时，即使溢出，结论依然正确// int mid = (left + right) >>> 1;mergeSort(nums, left, mid, temp);mergeSort(nums, mid + 1, right, temp);// 如果数组的这个子区间本身有序，无需合并if (nums[mid] <= nums[mid + 1]) {return;}mergeOfTwoSortedArray(nums, left, mid, right, temp);}/*** 对数组 arr 的子区间 [left, right] 使用插入排序** @param arr   给定数组* @param left  左边界，能取到* @param right 右边界，能取到*/private void insertionSort(int[] arr, int left, int right) {for (int i = left + 1; i <= right; i++) {int temp = arr[i];int j = i;while (j > left && arr[j - 1] > temp) {arr[j] = arr[j - 1];j--;}arr[j] = temp;}}/*** 合并两个有序数组：先把值复制到临时数组，再合并回去** @param nums* @param left* @param mid   [left, mid] 有序，[mid + 1, right] 有序* @param right* @param temp  全局使用的临时数组*/private void mergeOfTwoSortedArray(int[] nums, int left, int mid, int right, int[] temp) {System.arraycopy(nums, left, temp, left, right + 1 - left);int i = left;int j = mid + 1;for (int k = left; k <= right; k++) {if (i == mid + 1) {nums[k] = temp[j];j++;} else if (j == right + 1) {nums[k] = temp[i];i++;} else if (temp[i] <= temp[j]) {// 注意写成 < 就丢失了稳定性（相同元素原来靠前的排序以后依然靠前）nums[k] = temp[i];i++;} else {// temp[i] > temp[j]nums[k] = temp[j];j++;}}}
}

3 堆排序（堆很重要，堆排序根据个人情况掌握）

public class Solution {public int[] sortArray(int[] nums) {int len = nums.length;// 将数组整理成堆heapify(nums);// 循环不变量：区间 [0, i] 堆有序for (int i = len - 1; i >= 1; ) {// 把堆顶元素（当前最大）交换到数组末尾swap(nums, 0, i);// 逐步减少堆有序的部分i--;// 下标 0 位置下沉操作，使得区间 [0, i] 堆有序siftDown(nums, 0, i);}return nums;}/*** 将数组整理成堆（堆有序）** @param nums*/private void heapify(int[] nums) {int len = nums.length;// 只需要从 i = (len - 1) / 2 这个位置开始逐层下移for (int i = (len - 1) / 2; i >= 0; i--) {siftDown(nums, i, len - 1);}}/*** @param nums* @param k    当前下沉元素的下标* @param end  [0, end] 是 nums 的有效部分*/private void siftDown(int[] nums, int k, int end) {while (2 * k + 1 <= end) {int j = 2 * k + 1;if (j + 1 <= end && nums[j + 1] > nums[j]) {j++;}if (nums[j] > nums[k]) {swap(nums, j, k);} else {break;}k = j;}}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

4 插入排序（熟悉）

public class Solution {// 插入排序：稳定排序，在接近有序的情况下，表现优异public int[] sortArray(int[] nums) {int len = nums.length;// 循环不变量：将 nums[i] 插入到区间 [0, i) 使之成为有序数组for (int i = 1; i < len; i++) {// 先暂存这个元素，然后之前元素逐个后移，留出空位int temp = nums[i];int j = i;// 注意边界 j > 0while (j > 0 && nums[j - 1] > temp) {nums[j] = nums[j - 1];j--;}nums[j] = temp;}return nums;}
}

5 选择排序（了解）

import java.util.Arrays;public class Solution {// 选择排序：每一轮选择最小元素交换到未排定部分的开头public int[] sortArray(int[] nums) {int len = nums.length;// 循环不变量：[0, i) 有序，且该区间里所有元素就是最终排定的样子for (int i = 0; i < len - 1; i++) {// 选择区间 [i, len - 1] 里最小的元素的索引，交换到下标 iint minIndex = i;for (int j = i + 1; j < len; j++) {if (nums[j] < nums[minIndex]) {minIndex = j;}}swap(nums, i, minIndex);}return nums;}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}public static void main(String[] args) {int[] nums = {5, 2, 3, 1};Solution solution = new Solution();int[] res = solution.sortArray(nums);System.out.println(Arrays.toString(res));}
}

6 冒泡排序（了解）

public class Solution {// 冒泡排序：超时public int[] sortArray(int[] nums) {int len = nums.length;for (int i = len - 1; i >= 0; i--) {// 先默认数组是有序的，只要发生一次交换，就必须进行下一轮比较，// 如果在内层循环中，都没有执行一次交换操作，说明此时数组已经是升序数组boolean sorted = true;for (int j = 0; j < i; j++) {if (nums[j] > nums[j + 1]) {swap(nums, j, j + 1);sorted = false;}}if (sorted) {break;}}return nums;}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

7 计数排序（了解）

public class Solution {// 计数排序private static final int OFFSET = 50000;public int[] sortArray(int[] nums) {int len = nums.length;// 由于 -50000 <= A[i] <= 50000// 因此"桶" 的大小为 50000 - (-50000) = 10_0000// 并且设置偏移 OFFSET = 50000，目的是让每一个数都能够大于等于 0// 这样就可以作为 count 数组的下标，查询这个数的计数int size = 10_0000;// 计数数组int[] count = new int[size];// 计算计数数组for (int num : nums) {count[num + OFFSET]++;}// 把 count 数组变成前缀和数组for (int i = 1; i < size; i++) {count[i] += count[i - 1];}// 先把原始数组赋值到一个临时数组里，然后回写数据int[] temp = new int[len];System.arraycopy(nums, 0, temp, 0, len);// 为了保证稳定性，从后向前赋值for (int i = len - 1; i >= 0; i--) {int index = count[temp[i] + OFFSET] - 1;nums[index] = temp[i];count[temp[i] + OFFSET]--;}return nums;}
}

8 基数排序（了解）

public class Solution {// 基数排序：低位优先private static final int OFFSET = 50000;public int[] sortArray(int[] nums) {int len = nums.length;// 预处理，让所有的数都大于等于 0，这样才可以使用基数排序for (int i = 0; i < len; i++) {nums[i] += OFFSET;}// 第 1 步：找出最大的数字int max = nums[0];for (int num : nums) {if (num > max) {max = num;}}// 第 2 步：计算出最大的数字有几位，这个数值决定了我们要将整个数组看几遍int maxLen = getMaxLen(max);// 计数排序需要使用的计数数组和临时数组int[] count = new int[10];int[] temp = new int[len];// 表征关键字的量：除数// 1 表示按照个位关键字排序// 10 表示按照十位关键字排序// 100 表示按照百位关键字排序// 1000 表示按照千位关键字排序int divisor = 1;// 有几位数，外层循环就得执行几次for (int i = 0; i < maxLen; i++) {// 每一步都使用计数排序，保证排序结果是稳定的// 这一步需要额外空间保存结果集，因此把结果保存在 temp 中countingSort(nums, temp, divisor, len, count);// 交换 nums 和 temp 的引用，下一轮还是按照 nums 做计数排序int[] t = nums;nums = temp;temp = t;// divisor 自增，表示采用低位优先的基数排序divisor *= 10;}int[] res = new int[len];for (int i = 0; i < len; i++) {res[i] = nums[i] - OFFSET;}return res;}private void countingSort(int[] nums, int[] res, int divisor, int len, int[] count) {// 1、计算计数数组for (int i = 0; i < len; i++) {// 计算数位上的数是几，先取个位，再十位、百位int remainder = (nums[i] / divisor) % 10;count[remainder]++;}// 2、变成前缀和数组for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 3、从后向前赋值for (int i = len - 1; i >= 0; i--) {int remainder = (nums[i] / divisor) % 10;int index = count[remainder] - 1;res[index] = nums[i];count[remainder]--;}// 4、count 数组需要设置为 0 ，以免干扰下一次排序使用for (int i = 0; i < 10; i++) {count[i] = 0;}}/*** 获取一个整数的最大位数** @param num* @return*/private int getMaxLen(int num) {int maxLen = 0;while (num > 0) {num /= 10;maxLen++;}return maxLen;}
}

9 桶排序（了解）

public class Solution {// 桶排序// 1 <= A.length <= 10000// -50000 <= A[i] <= 50000// 10_0000private static final int OFFSET = 50000;public int[] sortArray(int[] nums) {int len = nums.length;// 第 1 步：将数据转换为 [0, 10_0000] 区间里的数for (int i = 0; i < len; i++) {nums[i] += OFFSET;}// 第 2 步：观察数据，设置桶的个数// 步长：步长如果设置成 10 会超出内存限制int step = 1000;// 桶的个数int bucketLen = 10_0000 / step;int[][] temp = new int[bucketLen + 1][len];int[] next = new int[bucketLen + 1];// 第 3 步：分桶for (int num : nums) {int bucketIndex = num / step;temp[bucketIndex][next[bucketIndex]] = num;next[bucketIndex]++;}// 第 4 步：对于每个桶执行插入排序for (int i = 0; i < bucketLen + 1; i++) {insertionSort(temp[i], next[i] - 1);}// 第 5 步：从桶里依次取出来int[] res = new int[len];int index = 0;for (int i = 0; i < bucketLen + 1; i++) {int curLen = next[i];for (int j = 0; j < curLen; j++) {res[index] = temp[i][j] - OFFSET;index++;}}return res;}private void insertionSort(int[] arr, int endIndex) {for (int i = 1; i <= endIndex; i++) {int temp = arr[i];int j = i;while (j > 0 && arr[j - 1] > temp) {arr[j] = arr[j - 1];j--;}arr[j] = temp;}}
}

10 希尔排序（不建议多花时间了解）

public class Solution {// 希尔排序public int[] sortArray(int[] nums) {int len = nums.length;int h = 1;// 使用 Knuth 增量序列// 找增量的最大值while (3 * h + 1 < len) {h = 3 * h + 1;}while (h >= 1) {// insertion sortfor (int i = h; i < len; i++) {insertionForDelta(nums, h, i);}h = h / 3;}return nums;}/*** 将 nums[i] 插入到对应分组的正确位置上，其实就是将原来 1 的部分改成 gap** @param nums* @param gap* @param i*/private void insertionForDelta(int[] nums, int gap, int i) {int temp = nums[i];int j = i;// 注意：这里 j >= deta 的原因while (j >= gap && nums[j - gap] > temp) {nums[j] = nums[j - gap];j -= gap;}nums[j] = temp;}
}