912.排序数组

/*
 * @lc app=leetcode.cn id=912 lang=typescript
 *
 * [912] 排序数组
 */

// @lc code=start

/* 选择排序：会超时 */
// function sortArray(nums: number[]): number[] {
// 	let l = 0,
// 		r = nums.length - 1;
// 	while (l <= r) {
// 		// 选取第一个座位最小数
// 		let min = l;

// 		for (let j = l; j < nums.length; j++) {
// 			if (nums[j] < nums[l]) {
// 				min = j;
// 			}
// 		}
// 		// 交换
// 		[nums[l], nums[min]] = [nums[min], nums[l]];
// 		l++;
// 	}
// 	return nums;
// }

/* 冒泡排序：会超时 */
// function sortArray(nums: number[]): number[] {
// 	let r = nums.length - 1;
// 	for (let i = 0; i < nums.length; i++) {
// 		for (let j = 0; j < r; j++) {
// 			if (nums[j] > nums[j + 1]) {
// 				[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
// 			}
// 		}
// 	}
// 	return nums;
// }

/* 冒泡排序2：超时 */
// function sortArray(nums: number[]): number[] {
// 	let l = 0,
// 		r = nums.length;
// 	while (l <= r) {
// 		let tag = true;
// 		for (let i = 0; i < r - 1; i++) {
// 			if (nums[i] > nums[i + 1]) {
// 				[nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
// 				tag = false;
// 			}
// 		}
// 		r--;
// 		if (tag) break;
// 	}
// 	return nums;
// }

/* 插入排序：超时 */
// function sortArray(nums: number[]): number[] {
// 	for (let i = 1; i < nums.length; i++) {
// 		let current = nums[i];
// 		let j = i - 1;

// 		// 将大于current的元素向右移动一位
// 		while (j >= 0 && nums[j] > current) {
// 			nums[j + 1] = nums[j];
// 			j--;
// 		}

// 		// 将current插入到正确的位置
// 		nums[j + 1] = current;
// 	}
// 	return nums;
// }

/* 快速排序：会超时 */
// function sortArray(nums: number[]): number[] {
// 	if (nums.length > 1) {
// 		// 基准元素
// 		let base = nums[0];
// 		let left: number[] = [],
// 			right: number[] = [];
// 		for (let i = 1; i < nums.length; i++) {
// 			if (nums[i] > base) {
// 				right.push(nums[i]);
// 			} else {
// 				left.push(nums[i]);
// 			}
// 		}
// 		return sortArray(left).concat(base, sortArray(right));

// 	} else {
// 		return nums;
// 	}
// }

/* 快速排序2(基准优化)：超出内存限制 */
// function sortArray(nums: number[]): number[] {
// 	// 如果数组长度小于等于1，直接返回数组
// 	if (nums.length <= 1) {
// 		return nums;
// 	}
// 	// 基准元素
// 	let baseIndex = medianThree(nums);
// 	let base = nums[baseIndex];
// 	let left: number[] = [],
// 		right: number[] = [];
// 	for (let i = 0; i < nums.length; i++) {
// 		if (i != baseIndex) {
// 			if (nums[i] > base) {
// 				right.push(nums[i]);
// 			} else {
// 				left.push(nums[i]);
// 			}
// 		}
// 	}
// 	return sortArray(left).concat(base, sortArray(right));
// }

// function medianThree(nums: number[]): number {
// 	let l = nums[0],
// 		m = nums[Math.floor((nums.length - 1) / 2)],
// 		r = nums[nums.length - 1];
// 	// m 在 l 和 r 之间
// 	if ((l <= m && m <= r) || (r <= m && m <= l))
// 		return Math.floor((nums.length - 1) / 2);
// 	// l 在 m 和 r 之间
// 	if ((m <= l && l <= r) || (r <= l && l <= m)) return 0;
// 	return nums.length - 1;
// }

/* 归并排序：通过 */
function sortArray(nums: number[]): number[] {
	if (nums.length <= 1) return nums;
	const m = Math.floor(nums.length / 2);
	const l = nums.slice(0, m);
	const r = nums.slice(m);
	return merge(sortArray(l), sortArray(r));
}

function merge(left: number[], right: number[]) {
	let result: number[] = [];
	let leftIndex = 0;
	let rightIndex = 0;

	while (leftIndex < left.length && rightIndex < right.length) {
		if (left[leftIndex] < right[rightIndex]) {
			result.push(left[leftIndex]);
			leftIndex++;
		} else {
			result.push(right[rightIndex]);
			rightIndex++;
		}
	}
	return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

import arr from "./data/arr";
console.log(sortArray(arr));

// console.log(sortArray([5, 2, 3, 1]));

// @lc code=end