排序

时游大约 15 分钟

排序

排序犹如一把将混乱变为秩序的魔法钥匙，使我们能以更高效的方法理解与处理数据。

无论是简单的升序，还是复杂的分类排列，排序都向我们展示了数据的和谐美感。

排序算法

排序算法用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，应为有序数据通常能够被更高效的查找、分析和处理。

评价维度

  • 运行效率：期望排序算法的时间复杂度尽量低，且整体操作数量较少(常数项变少)。对于大数据量的情况下，运行效率尤为重要。
  • 就地性：顾名思义，原地排序通过在原数组上直接操作实现排序，无需借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。
  • 稳定性：稳定排序在完成排序后，想等元素在数组中的相对顺序不发生改变。
  • 自适应性：自适应性的时间复杂度会受输入数据的影响，即最佳时间复杂度、最差时间复杂度、平均时间复杂度并不完全相等。
  • 是否基于比较：基于比较的排序依赖运算符（< = >）来判断元素的相对顺序，从而排序整个数组，理论来说最优时间复杂度为O(nlogn{n log n})，而非比较排序不使用比较运算符，时间复杂度可达O(n)，但是其通用性较差。

选择排序

假设要升序排列一个无序数组，具体选择排序操作如下：

  1. 初始状态下，所有元素未排序，即未排序的索引空间为[0,n-1]
  2. 选取未排序索引空间中的最小元素，将其与索引0处的元素交换，此时未排序索引空间为[1,n-1]
  3. 重复这个操作，经过n-1轮操作后，数组的前n-1个元素都已经排序，仅剩的一个一定是最大的，无序排序，此时排序结束。
function selectSort(nums = []) {
	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;
}
let select = selectSort([1, 2, 4, 5, 7, 23, 24, 51, 12]);
console.log(select);

算法特性

  • 时间复杂度为O(n2{n^2})，非自适应排序，每轮循环分别包含n+n-1+n-2+……+3+2，求和为(n−1)(n+2)/2{(n-1)(n+2) / 2}
  • 空间复杂度为O(1)，原地排序：指针l与r均使用常数大小的空间
  • 非稳定性排序：元素nums[i]可能被交换至与其相等的元素的右侧
选择排序非稳定示例
选择排序非稳定示例

冒泡排序

冒泡排序会连续与相邻元素对比，假如左侧>右侧，则交换二者，遍历完成后，最大的会被移动到最左侧

/* 冒泡排序 */

function bubbleSort(nums = []) {
	let l = 0,
		r = nums.length;
	while (l <= r) {
		for (let i = 0; i < r - 1; i++) {
			console.log(nums[i + 1]);
			if (nums[i] > nums[i + 1]) {
				[nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
			}
		}
		r--;
	}

	return nums;
}

let bubble = bubbleSort([1, 2, 4, 5, 7, 23, 24, 51, 12]);
console.log(bubble);

效率优化

当在某轮循环中未发生任何交换操作，代表数组已经排序完成，无需再执行后续循环操作。因此可以增加一个tag标识，一旦出现这种情况，立马跳出循环。

/* 优化：添加tag位置 */
function bubbleTagSort(nums = []) {
	let l = 0,
		r = nums.length;
	let index = 0;
	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--;
		index++;

		if (tag) break;
	}
	console.log("执行了：", index);
	return nums;
}

let tagBubble = bubbleTagSort([1, 2, 3, 4, 5]);
console.log(tagBubble);

算法特性

  • 时间复杂度为O(n2{n^2})、自适应排序：各轮冒泡遍历的数组长度为n-1、n-2……、2、1，总和为(n-1)n/2，在引入tag标记后，最佳时间复杂度可达O(n)。
  • 空间复杂度为O(1)，原地排序：指针l、r使用常数大小的内存空间。
  • 稳定排序：在冒泡时遇到相等元素不交换。

插入排序

在未排序区间选择一个基准元素，将其与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置，重复这个操作直到结束。

/* 插入排序 */
function insertSort(nums = []) {
	for (let l = 0; l < nums.length; l++) {
		let current = nums[l];

		let j = l - 1;
		while (j >= 0 && nums[j] > current) {
			nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位
			j--;
		}
		nums[j + 1] = current; // 将 base 赋值到正确位置
	}

	return nums;
}

let insert = insertSort([4, 1, 3, 1, 5, 2]);
console.log(insert);

算法特性

  • 时间复杂度为O(n2{n^2})，自适应排序：在最差情况下，每次插入操作需要分别循环n-1、n-2、……、2、1次，因此时间复杂度为O(n2{n^2})。而在遇到完全有序数据时，插入排序达到最优时间复杂度O(n)。
  • 空间复杂度为O(1)、原地排序：指针l、j使用常数大小的额外空间。
  • 稳定排序：在插入操作中，会将元素插入到相等元素的右侧，不会改变其顺序。

插入排序的优势

插入排序的时间复杂度为O(n2{n^2}),而快速排序的时间复杂度为O(nlogn{nlogn})，尽管插入排序的时间复杂度更高,在小数据量情况下，插入排序通常更快，因为快速排序包含了更多的计算单元。

在大多数编程语言中内置的插入排序，大致思路为：对于大数组，采用基于分治策略的排序算法，例如快速排序；对于短数组，直接使用插入排序。

虽然冒泡排序、选择排序和插入排序的时间复杂度都为O(${n^2})，但是在实际情况中，插入排序的使用频率显著高于冒泡排序与选择排序，主要原因如下：

  • 冒泡排序基于元素交换实现，需要借助一个临时变量，设计三个单元操作；插入排序基于元素赋值实现，仅需一个单元操作。
  • 选择排序在任何情况下的时间复杂度都为O(n2{n^2})，若给一组有序的数据，插入排序通常比选择排序效率高。
  • 选择排序不稳定，无法应用于多级排序。

快速排序

快速排序是一种基于分治策略的排序算法，运行高效，应用广泛。

快速排序的核心是“哨兵划分”，其目标是：选择数组中某个元素当作“基准数”，将所有小于基准数的元素移动到左侧，将所有大于基准数的元素移动到右侧，循环这个步骤直到排序完成。

/* 快速排序 */
function quikSort(nums = []) {
	if (nums.length > 1) {
		// 选取第一个作为基准元素
		let base = nums[0];
		let left = [],
			right = [];

		for (let i = 1; i < nums.length; i++) {
			if (nums[i] <= base) {
				left.push(nums[i]);
			} else {
				right.push(nums[i]);
			}
		}
		return quikSort(left).concat(base, quikSort(right));
	} else {
		return nums;
	}
}

let quik = quikSort([1, 2, 3, 6, 4, 1, 2, 4]);

console.log(quik); // 1 1 2 2 3 4 4 6

算法特性

  • 时间复杂度为O(nlogn{nlogn})，自适应排序
  • 空间复杂度为O(n)、原地排序
  • 非稳定排序

基准优化

快速排序在某些极端特殊情况下的时间效率可能会降低，例如输入数据是完全倒序的，由于选择了最左端元素所谓基准数，那么始终有一侧的子数组长度为0，退化为“冒泡排序”。

基准优化是选取三个候选元素（通常为首、尾、中点），取其中位数作为基准数，进一步提升算法的稳健性。

/* 基准数优化 */
/* 选取三个候选元素的中位数 */
function medianThree(nums) {
	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 smartQuikSort(nums = []) {
	let baseIndex = medianThree(nums);
	let base = nums[baseIndex];

	let left = [],
		right = [];

	for (let i = 0; i < nums.length; i++) {
		if (i != baseIndex) {
			if (nums[i] <= base) {
				left.push(nums[i]);
			} else {
				right.push(nums[i]);
			}
		}
	}
	return quikSort(left).concat(base, quikSort(right));
}

let smart = smartQuikSort([1, 2, 3, 6, 4, 1, 2, 4, 10, 9]);
console.log(smart);

归并排序

归并排序是一种基于分治策略的排序算法，包含以下操作：

  1. 划分阶段：通过递归不断地将数组从中点分开，将长数组变换成短数组。
  2. 合并阶段：当子数组长度为1时，开始合并，持续地将左右两个较短的有序数组合并成一个较长的有序数组，直到结束。
归并排序的划分与合并阶段
归并排序的划分与合并阶段
/* 归并排序 */

function merge(left, right) {
	let result = [];
	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));
}

function mergeSort(arr) {
	if (arr.length <= 1) return arr;

	const middle = Math.floor(arr.length / 2);
	const left = arr.slice(0, middle);
	const right = arr.slice(middle);

	return merge(mergeSort(left), mergeSort(right));
}

const arr = [5, 3, 7, 1, 9, 2, 6];
const sortedArr = mergeSort(arr);
console.log(sortedArr);

算法特性

  • 时间复杂度为O(nlogn{nlogn})、非自适应排序：划分产生高度为log n的递归树，每层合并的总操作数量为n。
  • 空间复杂度为O(n)、非原地排序：递归深度为log n，使用O(logn{log n})大小的栈帧空间。
  • 稳定排序：在合并过程中，相等元素的次序保持不变。

堆排序

堆排序步骤：

  1. 首先根据数据构建一个大顶堆，此时最大元素位于堆顶。
  2. 将堆顶元素与堆底元素对换，交换后堆底元素(本身为堆顶元素)出堆。
  3. 从顶至底进行堆化操作，重新生成一个大顶堆。
  4. 重复执行。
/* 堆排序 */

class MaxHeap {
	heap;
	constructor(heap) {
		this.heap = heap || []; // 初始化堆
	}

	// 获取父索引
	getParentIndex = (i) => Math.floor((i - 1) / 2);

	// 获取左子节点索引
	getLeftIndex = (i) => 2 * i + 1;

	// 获取右子节点索引
	getRightIndex = (i) => 2 * i + 2;

	// 获取堆顶元素
	peek = () => this.heap[0];

	// 获取大小
	size = () => this.heap.length;

	// 堆化：从底至顶堆化
	shiftUp = (i) => {
		while (true) {
			// 与其父节点对比
			let p = this.getParentIndex(i);
			if (this.heap[i] > this.heap[p]) {
				this.swap(i, p);
				// 向上继续堆化
				i = p;
			} else {
				break;
			}
		}
	};

	// 堆化：从顶至底堆化
	shiftDown = (i) => {
		while (true) {
			// 元素本身、左子节点、右子节点对比
			const l = this.getLeftIndex(i),
				r = this.getRightIndex(i);

			let ma = i; // 设置ma为三个中最大值
			if (l < this.size() && this.heap[l] > this.heap[i]) ma = l;
			if (r < this.size() && this.heap[r] > this.heap[ma]) ma = r;

			// 无需堆化，直接跳出
			if (ma === i) break;

			// 交换当前节点与子节点最大
			this.swap(i, ma);

			// 继续向下堆化
			i = ma;
		}
	};
	// 入堆
	push = (val) => {
		this.heap.push(val);
		// 堆化：从低至顶堆化
		this.shiftUp(this.size() - 1);
	};

	// 交换元素
	swap = (i, p) => {
		[this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]];
	};

	// 堆顶出堆
	pop = () => {
		if (this.heap.length == 0) return "堆为空";
		// 交换堆顶与堆底元素
		this.swap(0, this.size() - 1);

		// 删除堆底元素
		let val = this.heap.pop();

		// 从顶至第堆化
		this.shiftDown(0);

		return val;
	};
}

// 生成大顶堆
let heap = new MaxHeap([]);
let arr = [1, 7, 5, 6, 8, 3, 6, 9];
arr.map((el) => heap.push(el));

// 依次出堆
let final = [];
arr.map((el) => {
	final.push(heap.pop())
});
console.log(final);

算法特性

  • 时间复杂度为O(nlogn{n log n})、非自适应排序：建堆操作使用O(n)时间，从堆中提取最大元素的时间复杂度为O(logn{log n})，共n-1轮。
  • 空间复杂度为O(1)、原地排序：几个指针变量占用O(1)的时间，元素交换和堆化操作都是在原数组上进行的。
  • 非稳定排序：在交换堆顶元素和堆底元素时，相等元素的位置可能会发生变化。

桶排序

桶排序是分治策略的一个典型应用，它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中，然后对每个桶进行排序，最终按照桶的顺序将所有数据组合起来。

/* 桶排序 */

function bucketSort(nums = []) {
	// 初始化k个桶
	let k = nums.length / 2;
	let buckets = [];
	for (let i = 0; i < k; i++) {
		buckets.push([]); // 向上取整生成桶数量
	}

	// 将元素归入各个桶中
	nums.map((num) => {
		// 因为输入数据是[0,1)，所以num * k 映射到索引范围 [0, k-1]
		const i = Math.floor(num * k);
		// 将 num 添加进桶 i
		buckets[i].push(num);
	});

	// 将各个桶中数据进行排序
	buckets.map((bucket) => {
		bucket.sort((a, b) => a - b);
	});

	// 汇总
	let res = [];
	buckets.map((bucket) => {
		res.push(...bucket);
	});

	console.log(res);
	return res;
}

bucketSort([
	0.14, 0.19, 0.69, 0.46, 0.33, 0.25, 0.75, 0.98, 0.68, 0.36, 0.99, 0.36,
	0.21, 0.16,
]);

算法特性

桶排序适用于处理数据量很大的数据，例如输入100万个元素，由于空间限制，系统内存无法一次性加载所有数据，因此可以将数据分成1000个桶，然后分别对每个桶进行排序，最后将结果合并。

  • 时间复杂度为O(n+k)：假设元素在各个桶内平均分布，那么每个桶内元素数量为nk\dfrac{n}{k}。假设排序单个桶内元素使用O(nklognk)O(\dfrac{n}{k}log\dfrac{n}{k})时间，则排序所有桶使用O(nlognk)O(nlog\dfrac{n}{k})，当k较大时，时间复杂度趋向于O(n){O(n)}。合并过程中花费O(n+k){O(n+k)}的时间。
  • 自适应排序：在最差情况下，所有数据被分配到一个桶中，且排序该桶使用O(n2){O(n^2)}时间。
  • 空间复杂度为O(n+k){O(n+k)}、非原地排序：需要借助k个桶和n个元素的空间。
  • 桶排序是否稳定取决于排序桶内元素的算法是否稳定。

如何实现平均分配

桶排序在理论上是可以达到O(n){O(n)}的，关键在于如何将元素均匀分配到各个桶中。为了实现平均分配，我们可以先设定一条大致的分界线，将数据大致分为3个桶中，然后将数量较多的那个桶继续划分为3个桶，直到所有桶内的元素数量大致相等。

计数排序

技术排序通过统计元素数量来实现排序，通常用于整数数组。

实现步骤：

  1. 找出其中最大数字，记为m，创建长度为m+1的数组counter。
  2. 遍历数据nums，将counter[num]++，num记录的即为数据出现次数。
  3. 由于索引天然有序，所以只需要遍历counters，然后将数据组合起来即可。
/* 计数排序 */

function countSort(nums = []) {
	// 找到最大值
	let max = Math.max(...nums);

	// 创建max+1长度的数组并赋值0
	let counter = new Array(max + 1).fill(0);

	// 遍历nums，对应位置值+1
	nums.map((num) => {
		counter[num]++;
	});

	// 组合数据返回
	let result = [];
	counter.map((count, index) => {
		result.push(...new Array(count).fill(index));
	});

	return result;
}

countSort([0, 1, 2, 3, 5, 5, 2, 4, 0, 3]);

算法特性

  • 时间复杂度为O(n+m){O(n+m)}：设计遍历nums和遍历counter，一般情况下n>>m，时间复杂度趋向于O(n){O(n)}。
  • 空间复杂度为O(n+m){O(n+m)}、非原地排序：借助长度为n和m的数组result和counter。
  • 稳定排序

局限性

计数排序只能适用于非负整数。

基数排序

基数排序原则是从低位数开始排序起，直到最高位排序完成

/* 基数排序 */

/* 获取元素 num 的第 k 位，其中 exp = 10^(k-1) */
function digit(num, exp) {
	// 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
	return Math.floor(num / exp) % 10;
}

/* 计数排序（根据 nums 第 k 位排序） */
function countingSortDigit(nums, exp) {
	// 十进制的位范围为 0~9 ，因此需要长度为 10 的桶数组
	const counter = new Array(10).fill(0);
	const n = nums.length;
	// 统计 0~9 各数字的出现次数
	for (let i = 0; i < n; i++) {
		const d = digit(nums[i], exp); // 获取 nums[i] 第 k 位，记为 d
		counter[d]++; // 统计数字 d 的出现次数
	}
	// 求前缀和，将“出现个数”转换为“数组索引”
	for (let i = 1; i < 10; i++) {
		counter[i] += counter[i - 1];
	}
	// 倒序遍历，根据桶内统计结果，将各元素填入 res
	const res = new Array(n).fill(0);
	for (let i = n - 1; i >= 0; i--) {
		const d = digit(nums[i], exp);
		const j = counter[d] - 1; // 获取 d 在数组中的索引 j
		res[j] = nums[i]; // 将当前元素填入索引 j
		counter[d]--; // 将 d 的数量减 1
	}
	// 使用结果覆盖原数组 nums
	for (let i = 0; i < n; i++) {
		nums[i] = res[i];
	}
}

/* 基数排序 */
function radixSort(nums) {
	// 获取数组的最大元素，用于判断最大位数
	let m = Math.max(...nums);
	// 按照从低位到高位的顺序遍历
	for (let exp = 1; exp <= m; exp *= 10) {
		// 对数组元素的第 k 位执行计数排序
		// k = 1 -> exp = 1
		// k = 2 -> exp = 10
		// 即 exp = 10^(k-1)
		countingSortDigit(nums, exp);
	}
	return nums;
}

let res = radixSort([25, 15, 71, 34, 91, 394]);

console.log(res);

算法特性

  • 时间复杂度位O(nk){O(nk)}：设数据量为n、数据位为d进制、最大位数为k，则对某一位进行计数排序使用O(n+d){O(n+d)}的时间，排序所有k位使用O((n+d)k){O((n+d)k)}的时间，通常情况下d和k都相对较小，时间复杂度趋向于O(n){O(n)}。
  • 空间复杂度为O(n+d){O(n+d)}、非原地排序：与计数排序相同。
  • 稳定排序
上次编辑于:
贡献者: Sunshine,minmengwei
Loading...
时游的个人技术博客
Copyright © 2026 时游