排序

冒泡排序

最基本的排序算法,双重遍历数组。数组中的每个值会依次与数组所有的值进行比较,从而进行位置的交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
let bubling = arr => {
arrl = arr.length

for (let i = 0; i < arrl; i ++) {
for (let j = 0; j < arrl; j ++) {
if (arr[i] < arr[j]) {
let temp = arr[j]
arr[j] = arr[i]
arr[i] = temp
}
}
}
return arr
}

// 第一次的外层loop结束,这个数组的最大值max会根据条件被推(冒泡)到数组的第一位置或末尾。

// 第二次外层loop,会以index为1的位置的元素与所有的数组元素进行比较。最后,会以max冒泡到 index 1的位置结束本次loop。

// 第三次外层loop,会以index为2的位置的元素与所有的数组元素进行比较。最后,会以max冒泡到 index 2的位置结束本次loop。
// 之后的每一次,都以此类推直至外层loop结束。

可以看出,冒泡排序的本质便是不断的将max根据条件的不同向前或是向后冒泡,在每一次max冒泡到当前外层loop的index的过程中,会对它两边的元素进行排序。

优点稳定,易懂。但效率不高,耗费性能,频繁的交换值。

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
let qsort = arr => {

if (arr.length <= 1) { return arr }

let left = [],
right = [],
pivot = arr.splice(Math.floor(arr.length / 2), 1)[0] // 取中间值

// 以中间值为准,小于push进left反之right数组。
for (item of arr) {
if (item < pivot) {
left.push(item)
} else {
right.push(item)
}
}

// 递归qsort,直至arr.length <= 1
return [].concat(qsort(left), pivot, qsort(right))
}


快排采取的是分而治之思想。
将一个大问题分解成有着相同问题的小问题,大问题的解便是所有小问题的解的合集。

每次取数组的一个值(不是中间值也可)为准,小于准值的归为left数组,大于的话归为right。
之后递归作用与left与right,直至将每个无序数组分化为若干个由单个元素数组组成的有序数组时
concat合并成最后的一个有序数组。

优点快速便捷,但由于递归的使用,不稳定,较为脆弱。

快速排序–三路划分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const qsort = (arr) => {
if (arr.length <= 1) { return arr }
let left = [],
mid = [],
right = [],
zero = arr[0]

for(item of arr){
if (item < zero) {
left.push(item)
} else if (item == zero){
mid.push(item)
} else {
right.push(item)
}
}
return [].concat(qsort(left), mid, qsort(right))
}
// 这里的准值每次都是取最左边的元素,也叫做原地排序。快排的关键点在于基准的选择,选取不同的基准,会有不同的性能。

// 三路划分是在快排的基础上进行优化,与准值相等的值放入一个数组mid,且不再参与遍历。通过减少遍历次数以优化。
// 即使这样,快排仍然有很大的优化空间,例如如何均匀地取准值也是一个需要优化的空间。

三行代码–三路划分

1
2
3
4
5
6
// 对上面的三路划分的重写

let qsort = arr => arr.length <= 1 ? arr :
qsort(arr.filter(x => x < arr[0]))
.concat(arr.filter(x => x === arr[0]))
.concat(qsort(arr.filter(x => x > arr[0])))

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
let insertSort = arr => {
for(let i = 1; i < arr.length; i ++){
let el = arr[i]
// 故意将 j 提升为全局变量
for(var j = i - 1; j >= 0; j --) {
let tmp = arr[j]
let order = tmp - el
if(order > 0) {
arr[j+1] = tmp
}else{
break;
}
}

arr[j+1] = el
}
return arr
}

// 直接插入排序适用于数组长度小于10,且快要成型的有序数组中。

Array.prototype.sort

JS内置了一个高阶的排序函数sort

1
2
3
4
5
let a = [3,1,43,5,123,6,231,0,456,500,123, 1, 2, 88, 99];

a.sort((x, y) => x - y) // 将会把数组以升序的方式排序,若要降序,y - x 即可。

不仅方便快捷,且性能胜于上述所有。

MDN-Array.prototype.sort

我们也可以看看Google的V8中的快排实现。

在第760行。

Google Chrome–V8

对于算法的优劣,我们有一个时间复杂度的判断标准。感兴趣可以翻阅有关于算法的书籍。如《算法》4th

这里只是对于一些常用算法的概览,以及作者笔记用途。

文章作者: Luo Jun
文章链接: /2018/06/05/quickSort/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Aning