LeetCode 912. 排序数组

题目

给你一个整数数组 nums，将该数组升序排列。

示例 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 <= nums.length <= 50000

• -50000 <= nums[i] <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

这道题没有什么好说的，快排就完事了；
引申：Arrays中的sort（DualPivotQuicksort 即双轴快排）源码值得一看，sort是一个综合了快排，归并，直接选择，插入排序等的多因素排序方法，
源码的设计者应该是根据大量数据计算出的几个数据量边界，以此来决定使用最优的排序算法；
sort源码的部分片段：

/** * This class implements the Dual-Pivot Quicksort algorithm by * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm * offers O(n log(n)) performance on many data sets that cause other * quicksorts to degrade to quadratic performance, and is typically * faster than traditional (one-pivot) Quicksort implementations. * 该排序算法是一个双轴快速排序，是三位大神(Vladimir Yaroslavskiy，Jon Bentley， and JoshuaBloch)实现的， * 在大量数据集中，其他快排算法的排序性能最坏时为O(n²)，但该算法将一直提供稳定的O(nlogn)排序性能，其效率要优于传统单轴快速排序 * * All exposed methods are package-private, designed to be invoked * from public methods (in class Arrays) after performing any * necessary array bounds checks and expanding parameters into the * required forms. * 所有的方法都是包私有的，以便于在完成必要的边界检查和参数扩展及格式化后供Arrays调用 * * @author Vladimir Yaroslavskiy * @author Jon Bentley * @author Josh Bloch * * @version 2011.02.11 m765.827.12i:5\7pm * @since 1.7 */final class DualPivotQuicksort {...}

几个边界量：

/** * The maximum number of runs in merge sort. * 合并子列最大数量：待合并的序列的最大数量 */private static final int MAX_RUN_COUNT = 67;/** * The maximum length of run in merge sort. * 合并子列最大长度：待合并的序列的最大长度 */private static final int MAX_RUN_LENGTH = 33;/** * If the length of an array to be sorted is less than this * constant, Quicksort is used in preference to merge sort. * 快速排序阈值：若待排序数组的长度小于该值，则优先使用快速排序而不是归并排序 */private static final int QUICKSORT_THRESHOLD = 286;/** * If the length of an array to be sorted is less than this * constant, insertion sort is used in preference to Quicksort. * 插入排序阈值：若待排序数组的长度小于该值，则优先考虑插入排序而不是快速排序 */private static final int INSERTION_SORT_THRESHOLD = 47;/** * If the length of a byte array to be sorted is greater than this * constant, counting sort is used in preference to insertion sort. * byte数组计数排序阈值：若待排序的byte数组长度大于该值，则优先使用计数排序而不是插入排序 */private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;/** * If the length of a short or char array to be sorted is greater * than this constant, counting sort is used in preference to Quicksort. * short&char数组计数排序阈值：若待排序的数组是short或char类型的且数组长度大于该值，将优先使用计数排序而不是插入排序 */private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;

思路1-快排；

步骤：

1. 寻找一个中间值（一般为第一个数），将小于该值的放左边，大于的放右边；

2. 以上一次的终止位置（不包括该位置）为分界线分两块递归进行1的操作；

3. 终结条件为左右索引相遇；

算法源码示例

package leetcode;/** * @author ZhouJie * @date 2020年3月31日 上午12:02:03  * @Description: 912. 排序数组 * */public class LeetCode_0912 {}class Solution_0912 {	/**	 * @author: ZhouJie	 * @date: 2020年3月31日 上午12:50:01 	 * @param: @param nums	 * @param: @return	 * @return: int[]	 * @Description: 快速排序	 *	 */	public int[] sortArray(int[] nums) {		quickSort(nums, 0, nums.length - 1);		return nums;	}	/**	 * @author: ZhouJie	 * @date: 2020年3月31日 上午12:50:04 	 * @param: @param nums	 * @param: @param start	 * @param: @param end	 * @return: void	 * @Description: 快排核心	 *	 */	private void quickSort(int[] nums, int start, int end) {		if (start >= end) {			return;		}		int midVal = nums[start];		int left = start, right = end;		while (left < right) {			while (left < right && nums[right] >= midVal) {				right--;			}			nums[left] = nums[right];			while (left < right && nums[left] <= midVal) {				left++;			}			nums[right] = nums[left];		}		nums[left] = midVal;		quickSort(nums, start, left - 1);		quickSort(nums, left + 1, end);	}}