JavaScript数组排序算法

直播预告-鸿蒙创想开发实例详解：从需求到上线的全流程解决方案

大多数语言都有一个内置方法，用于尝试对一堆数据进行排序。大多数开发人员的共同倾向可能是选择这条道路并避免编写自己的实现。但是，这最终可能会对性能产生不可预见的影响。因此，最好采用最适合您当前要求的排序技术。

JavaScript 中的内置排序方法是 Array.prototype.sort()，“就地”对数组的元素进行排序，并返回对相同数组的引用。默认排序是将元素转换为字符串，然后按照它们的 UTF-16 码元值升序排序。

在计算机科学中，一个原地算法（in-place algorithm，也称“就地算法”）是基本上不需要借助额外的数据结构就能对输入的数据进行变换的算法。不过，分配少量空间给部分辅助变量是被允许的。算法执行过程中，输入的数据往往会被输出结果覆盖。原地算法只能通过替换或交换元素的方式来修改原始的输入。不满足“原地”原则的算法也被称为非原地（not-in-place）算法或异地（out-of-place）算法。

由于它取决于具体实现，因此无法保证排序的时间和空间复杂度。

计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。

先来准备一个无序的数组：

function random(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min
}

function create(len, min, max) {
	const nums = []

	for (let i = 0; i < len; i++) {
		nums.push(random(min, max))
	}

	return nums
}

const nums = create(10, -100, 100)

冒泡排序

冒泡排序是最简单的排序算法之一，该算法的空间复杂度为 O(1)，平均时间复杂度为 O(n²)。

• 开始迭代数组，一次比较 2 个元素。
• 根据需要交换它们。
• 在第一遍结束时，最大的数字已冒泡到数组的最后一个索引，因此忽略下一遍中的最后一个索引。
• 继续这些传递，直到数组排序完毕。

function bubbleSort(arr) {
	// 通过减少所需的传递次数，稍微优化的解决方案
	let noSwaps

	for (let i = 0; i < arr.length; i++) {
		noSwaps = true

		for (let j = 0; j < arr.length - 1 - i; j++) {
			// // 根据需要交换元素
			if (arr[j] > arr[j + 1]) {
				[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
				noSwaps = false
			}
		}

		// 如果在一个完整的过程中没有进行交换，则结束迭代
		if (noSwaps) break
	}

	return arr
}

console.log(bubbleSort(nums))

插入排序

插入排序算法的空间复杂度也为 O(1)，时间复杂度为 O(n²)。

• 首先将第二个元素与第一个元素进行比较，必要时交换。
• 迭代数组的其余部分。然后，对于每个元素，迭代数组的排序部分，并通过比较将该元素插入到需要的位置。
• 继续这样做，直到所有元素都插入到正确的位置。

function insertionSort(arr) {
	for (let i = 1; i < arr.length; i++) {
		// 开始比较当前元素与它之前的每个元素
		for (let j = i - 1; j > -1; j--) {
			// 根据需要交换元素
			if (arr[j + 1] < arr[j]) {
				[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
			}
		}
	}

	return arr
}

console.log(insertionSort(nums))

选择排序

选择排序的时间复杂度为 O(n²)，空间复杂度为 O(1)。

• 假设第一个元素是最小的（或者最大，如果按降序排序）。
• 从数组中找到最小值并将其与数组的第一个元素交换。这就完成了一次传递，其中数组的最小元素现在位于第 0 个索引处。
• 对数组的其余元素重复此过程，但对于下一遍，不要比较我们刚刚放置在第 0 个索引处的元素。

function selectionSort(arr) {
	let min

	for (let i = 0; i < arr.length; i++) {
		// 假设一个最小值
		min = i

		for (let j = i + 1; j < arr.length; j++) {
			if (arr[j] < arr[min]) {
				min = j
			}
		}

		// 如果找到新的最小值，则交换
		if (min !== i) {
			[arr[i], arr[min]] = [arr[min], arr[i]]
		}
	}

	return arr
}

console.log(selectionSort(nums))

前三种算法很难获得高性能的排序算法。因此，为了有一个在时间复杂度上优于 O(n²) 的算法，我们必须使用递归。

归并排序

归并排序的空间复杂度是 O(n)，时间复杂度为 O(n * logn)。

• 递归地将数组分成更小的数组，直到每个数组只有一个元素。
• 一旦数组被分解成单个元素，我们就可以将它们合并在一起，从左到右或从右到左。
• 合并两个数组 arr1 和 arr2。
• 重复此过程，直到数组只有一个元素。

// 合并两个已排序的子数组
function merge(arr1, arr2) {
	// 创建一个新数组，并使用两个指针来跟踪 arr1 和 arr2 中的元素
	let res = [], i = 0, j = 0

	// 循环，直到 arr1 或 arr2 变为空
	while (i < arr1.length && j < arr2.length) {
		// 如果 arr1 的当前元素小于 arr2 的元素，则推入 arr1[i] 并增加 i
		if (arr1[i] < arr2[j]) {
			res.push(arr1[i])
			i++
		} else {
			res.push(arr2[j])
			j++
		}
	}

	// 将剩下的子数组添加到新数组中
	while (i < arr1.length) {
		res.push(arr1[i])
		i++
	}

	while (j < arr2.length) {
		res.push(arr2[j]);
		j++
	}

	return res
}

// 递归归并排序
function mergeSort(arr) {
	if (arr.length <= 1) return arr

	// 从中间分割数组为两部分
	let mid = Math.floor(arr.length / 2)
	let left = mergeSort(arr.slice(0, mid))
	let right = mergeSort(arr.slice(mid))

	// 合并两个已排序的两部分
	return merge(left, right)
}

console.log(mergeSort(nums))

快速排序

快速排序的空间复杂度是 O(log n)，时间复杂度为 O(n * log n)。

• 选择一个元素作为基准（pivot）。
• 所有小于基准的元素都移到基准的左边，所有大于基准的元素都移到基准的右边。
• 对基准左边的子数组和右边的子数组进行排序。

function partition(arr, start = 0, end = arr.length - 1) {
	// 选择 arr[start] 作为基准值
	let pivot = arr[start]
	let swapIdx = start

	for (let i = start + 1; i <= end; i++) {
		if (arr[i] < pivot) {
			swapIdx++
			// 将当前元素与基准索引处的元素交换
			[arr[i], arr[swapIdx]] = [arr[swapIdx], arr[i]]
		}
	}

	// 交换基准索引和基准元素处的元素
	[arr[swapIdx], arr[start]] = [arr[start], arr[swapIdx]]

	// 返回交换后枢轴元素的索引
	return swapIdx
}

function quickSort(arr, left = 0, right = arr.length - 1) {
	// left 和 left 不重叠，之后我们将得到一个只有一个元素的数组
	if (left < right) {
		let pivotIndex = partition(arr, left, right)

		// 对于 left 数组，也就是在主元素左边的所有元素
		quickSort(arr, left, pivotIndex - 1)

		// 对于 right 数组，也就是主元素右边的所有元素
		quickSort(arr, pivotIndex + 1, right)
	}

	// 当数组长度为1时返回数组，即 left === right
	return arr
}

console.log(quickSort(nums))