Javascript排序算法

发表于 | 更新于 | 分类于 | 评论数：



开篇

排序是我们日常开发中非常常用的一种操作。目前最经典的排序算法有十种，分别是：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序。下面我们介绍两种最常用的排序算法：冒泡排序和快速排序。

冒泡排序

冒泡排序实现思想比较简单，但是性能较差，适合作为培训教学使用。主要实现思想是：遍历数据中每一个节点，如果不合符我们预期的顺序则和下一个数据交换位置，依此类推。



实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//交换数组元素
function swap(arr,n,n1) {
	let temp = arr[n];
	arr[n] = arr[n1];
	arr[n1] = temp;
}
//冒泡排序
function bubbleSort(arr) {
    for(let i=arr.length-1;i>=0;i--) {
        for(let j=0;j<i;j++) {
            if(arr[j]>arr[i]) {
                swap(arr,j,i)
            }
        }
    }
    return arr;
}

快速排序

快速排序是已知排序算法中最快的之一，适合数据量较大的时候使用。其主要实现思想是：先取一个基数（一般取数据的中间位置），然后对基数两边的数据分别排序，比基数大的放右边，比基数小的放左边。之后，对左右两边的数据进行以上相同的操作，直到左右两边数据为空。



实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//快速排序
function quickSort(arr) {
	let piovtIndex = Math.floor(arr.length/2);
	if(arr.length<=1) return arr;
	let piovt = arr.splice(piovtIndex,1)[0];
	let _left = []
	let _right = []
	for (var i = 0; i < arr.length; i++) {
		let item = arr[i];
		if(item<piovt) {
			_left.push(item)
		} else {
			_right.push(item)
		}
	}
	return quickSort(_left).concat([piovt],quickSort(_right))
}

总结



不难看出：两种算法相对比之下，快速排序的所用的操作更少。下面我们用一个例子来验证下这个结论：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
var _arr = []
for(let i=0;i<100000;i++) {
	_arr.push(Math.ceil(Math.random()*100))
}

// console.log(_arr)
//快速排序
function quickSort(arr) {
	let piovtIndex = Math.floor(arr.length/2);
	if(arr.length<=1) return arr;
	let piovt = arr.splice(piovtIndex,1)[0];
	let _left = []
	let _right = []
	for (var i = 0; i < arr.length; i++) {
		let item = arr[i];
		if(item<piovt) {
			_left.push(item)
		} else {
			_right.push(item)
		}
	}
	return quickSort(_left).concat([piovt],quickSort(_right))
}

//交换数组元素
function swap(arr,n,n1) {
	let temp = arr[n];
	arr[n] = arr[n1];
	arr[n1] = temp;
}
//冒泡排序
function bubbleSort(arr) {
    for(let i=arr.length-1;i>=0;i--) {
        for(let j=0;j<i;j++) {
            if(arr[j]>arr[i]) {
                swap(arr,j,i)
            }
        }
    }
    return arr;
}

//测试
let time1 = Date.now()

var a = bubbleSort(_arr)

// console.log(a)
console.log('冒泡排序用时：',Date.now()-time1);


let time2 = Date.now()
quickSort(_arr)
console.log('快速排序用时：',Date.now()-time2);

// 冒泡排序用时： 5373
// 快速排序用时： 533

在数据量为10w时，结果输出为冒泡排序用时5373ms,快速排序用时533ms，两者性能相差10倍之多！