排序算法总结之JavaScript版
本文由 小茗同学 发表于 2018-06-13 浏览(2956)
最后修改 2024-07-05 标签：javascript sort

概述

常见排序算法：

  • 稳定指：如果a=b,a在b的前面，排序后a仍然在b的前面
  • 不稳定指：如果a=b，a在b的前面，排序后可能会交换位置

傻瓜排序（选择排序）

这个傻瓜排序是我自己给起的名字，就是按照人的常规思维进行排序，不考虑任何时间复杂度和空间复杂度。话说如果给你一个数组让你手工排序，你的思路会是什么样的呢？我想你肯定是这样的：

整体用肉眼扫描一遍，找到最小的，插入结果里面，然后再扫描剩下的数字，找到最小的，再次插入结果里面，直至原始数组变空，是的，没错，这里说的傻瓜排序就是这个思路。

后来发现就这么笨的排序方法竟然还专门有一个名字，就叫“选择排序”。

/**
 * 选择排序（傻瓜排序），时间复杂度O(n^2)，空间复杂度O(1)
 */
function selectionSort(arr) {
	var result = [];
	while(arr.length) {
		var min = arr[0], minIdx = 0; // 先假设第一个数是最小的
		// 遍历找到最小的数字
		for(var i = 1; i< arr.length; i++) {
			if(arr[i] < min) {
				min = arr[i];
				minIdx = idx;
			}
		}
		result.push(min); // 将当前最小数放入结果数组中
		arr.splice(idx, 1); // 从原始数组删除这个数
	}
	return result;
}

冒泡排序（Bubble Sort）

这是最笨也是最容易想到的排序方法：

/**
 * 冒泡排序，最坏时间复杂度O(n^2)，空间O(1)
 * @param arr 要排序的数组
 */
function bubbleSort(arr) {
	for (let i = 0, n = arr.length; i < n - 1; i++) {
		for (let j = 0; j < n - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
			}
		}
	}
	return arr;
}

如何记忆呢？这样记忆：n个数，需要n-1次循环，每次循环从0到n-1-i处为止，最大或最小的数永远在最后面。

插入排序

插入排序其实和冒泡排序非常类似，只不过处理方式不同，插入排序类似打扑克洗牌的过程，逐个将未排序的元素插入到已排序的部分中。时间和空间复杂度和冒泡一样。

/**
 * 插入排序，最坏时间复杂度O(n^2)，空间O(1)
 * @param arr 要排序的数组
 */
function insertSort(arr) {
		for (var i = 1, n = arr.length; i < n; i++) {
			for (var j = i; j > 0; j--) {
				if (arr[j] < arr[j - 1]) {
					// 调换两者的位置
					[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
				}
			}
		}
		return arr;
}

快速排序

快速排序采用了“分治”的思想，它在冒泡排序基础上实现的递归分治法。优点就是快，大多数情况下表现较好，但缺点是不稳定，最坏运行情况是O(n²)。

/**
 * 快速排序时间最好O(n*log n)，最坏O(n^2)，空间O(log n)
 * @param arr 要排序的数组
 */
function quickSort(arr, left = 0, right = arr.length - 1) {
	function split(arr, left, right) {
		var i = left + 1, j = right, base = left; // base为基准
		while (i <= j) {
			while (i <= right && arr[i] < arr[base]) i++;
			while (j >= left && arr[j] > arr[base]) j--;
			if (i <= j) {
				//交换并且自增
				[arr[i++], arr[j--]] = [arr[j], arr[i]];
			}
		}
		[arr[base], arr[j]] = [arr[j], arr[base]];
		return j;
	}
	if (left < right) {
		var splitIndex = split(arr, left, right);
		quickSort(arr, left, splitIndex - 1);
		quickSort(arr, splitIndex + 1, right);
	}
	return arr;
}
console.log(quickSort([1,5,3,4,8,0,9,4,2,12,6,8,3,2,6,7,8,9,4,32,7,9]));

分割原理

首先，设定一个参考数，我们这里用第一个参数做参考数，然后用两个变量 i 和 j 从数组两边开始向中间扫描，i 向右走，j 往左走：

i往右走，直到遇见比中轴元素大的（或等于）元素停止移动，j 向左走，直到遇到比中轴元素小的（或等于）的元素停止移动：

此时，如果 i < j 则交换 i、j 所指向的元素：

然后继续向右向左走，直到 i >= j 整个扫描停止：

此时 i 对应元素的左边（不包含arr[i]）必定小于或等于5,j 对应元素的右边（不包含arr[j]）必定大于或等于5

至此，分隔完成。

本段主要参考这里（图片也是来自这里）：https://www.itcodemonkey.com/article/3287.html

阮一峰版

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [], right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) left.push(arr[i]);
		else right.push(arr[i]);
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

从代码长度以及理解难易程度上阮一峰版是最佳的，因为即便是从未了解过快速排序的人基本上一看就能懂，但是有2个大问题：

  • 每次都创建新数组，无形中大大增加了空间复杂度；
  • 使用splice不合理。

希尔排序

希尔排序是插入排序的一种改进版本，通过比较和交换相隔一定距离的元素来实现更高效的排序。

/**
 * 希尔排序，时间O(n * log n * log n)，最坏O(n^2)，空间O(1)
 * @param arr 要排序的数组
 */
function shellSort(arr) {
	const n = arr.length;
	for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
		for (let i = gap; i < n; i++) {
			for (let j = i; (j - gap) >= 0; j -= gap) {
				if (arr[j] < arr[j - gap]) {
					[arr[j], arr[j - gap]] = [arr[j - gap], arr[j]];
				}
			}
		}
	}
	return arr;
}
shellSort([4,6,1,8,2,7]);