开放原子开发者工作坊

我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]：https://github.com/izhoujie/Algorithmcii

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);
	}

}