概述
常见排序算法:
- 稳定指:如果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]));
复制运行
5.1. 分割原理
首先,设定一个参考数,我们这里用第一个参数做参考数,然后用两个变量 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
5.2. 阮一峰版
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]);
复制运行
正在加载评论