Fighting with LeetCode -- 刷题记录一点思考

AlfxjxAlfxjx
2022-03-16

关于快速排序

今天学习了快速排序,读了阮一峰老师的博客,但是这个预设了数组是不重复的; 对于这个题目来说,有点不够用。后面又看了文章评论下面的讨论,对递归的快速排序改造了一下:

function sortArr(arr) {
	if (arr.length <= 1) return arr;
	let mid = Math.floor(arr.length / 2);
	// 这里没有使用splice方法去改变原数组,原因是 mid 是存在重复的情况。
	let left = [];
	let right = [];
	let mids = [];
	for (let i = 0; i < arr.length; i++) {
		if (arr[i] < arr[mid]) {
			left.push(arr[i]);
		} else if (arr[i] > arr[mid]) {
			right.push(arr[i]);
		} else {
			// 对于有重复的情况,需要把重复的放到一起
			mids.push(arr[i]);
		}
	}
	// 其他和原文是一样的
	return [...sortArr(left), ...mids, ...sortArr(right)];
}