排序算法--基本排序算法

发表于 | 更新于

最近公司里没有安排什么事情，翻了翻数据结构与算法这本书，补足一下自己在算法方面的知识。

数组类和方法

es6的出现已经有很长一段时间了，之前看过一些关于es6的教程不过一直没有实践过，这次正好用es6来练练手。

在讲解每一个排序算法前我们先定义一个叫cArray的类和一些方法来辅助我们。

先上代码：

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
58
59
60
class cArray {
    constructor(numOfElement) {
        this.dataStore = [];                // 储存数组
        this.numOfElement = numOfElement;   // 数组的长度
            
		// 默认每个值自增
		for (let i = 0; i < numOfElement; i++) {
			this.dataStore[i] = i;
		}
	}
	
	/**
	 * 随机生成数组成员
	 */
	randomSetArr() {
		for (let i = 0; i < this.numOfElement; i++) {
			this.dataStore[i] = Math.floor(Math.random() * this.numOfElement + 1);
		}
	}
	
	/**
	 * 数组深拷贝
	 * @returns {*}
	 */
	copyArr(){
		let length = this.dataStore.length,
			newArr = new cArray(length);
		for(let i = 0; i < length; i++){
			newArr.dataStore[i] = this.dataStore[i];
		}
		return newArr;
	}
	
	/**
	 * 输出数组
	 * @returns {string}
	 */
	toString() {
		let str = '';
		for (let i = 0; i < this.dataStore.length; i++) {
			str += this.dataStore[i] + ' ';
			if (i > 0 && i % 10 === 0) {
				str += '\n'; // 每输出10个换行
			}
		}
		return str;
	}
	
	/**
	 * 交换数组成员
	 * @param arr
	 * @param index1
	 * @param index2
	 */
	swap(arr, index1, index2) {
		let temp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = temp;
	}
}

我们来挨个解释一下。

0. constructor

在constructor里要求传入一个参数表示数组的长度，然后对数组依次赋上默认值。

1. randomSetArr

默认递增的数组显然不是我们想要的，所以这里需要一个方法，把数组每个成员定为随机值。

2. copyArr

如果想要准确比较不同排序算法的速度差异，单一变量原则很重要，所以我们需要把随机设定的值深拷贝出来，获得多个内容相同又不互相影响的数组。

3. toString

这个就不用解释什么了，把数组成员10个一行地依次输出出来。

4. swap

既然是排序嘛，肯定会有数据成员间互相交换位置的时候

基本排序算法

前戏差不多就这样了，我们来开始正题吧。

数据结构与算法中说：基本排序算法其核心思想是指对一组数据按照一定的顺序重新排列。重新排列时用到的技术是一组嵌套的for循环。其中，外循环会遍历数组的每一项，内循环则用于比较元素。

冒泡排序

冒泡排序，是最慢的排序之一，也是一种最容易实现的排序算法。

以按升序排列为例，较大的值会浮动到数组的右侧，较小的值会浮动到数组的左侧。

其实就是很简单的数组中两两成员依次比较，如果左大于右，就交换位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 注意：此函数为cArray类的方法，下同
 */
bubbleSort() {
	let numOfElements = this.dataStore.length;
	for (let outer = numOfElements; outer >= 2; outer--) {
		for (let inner = 0; inner <= outer; inner++) {
			if (this.dataStore[inner] > this.dataStore[inner + 1]) {
          		this.swap(this.dataStore, inner, inner + 1);
          	}
   		}
	}
}

我们来试一下这个排序算法的效果，和处理时间：

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
var numOfElements = 100,
    myArray = new cArray(numOfElements);
myArray.randomSetArr();
console.log(myArray.toString());

var arr1 = myArray.copyArr();

console.time('bubbleSort');
arr1.bubbleSort();
console.timeEnd('bubbleSort');
console.log(arr1.toString());

// 排序前：
// 36 4 81 58 82 6 88 79 37 57 33 
// 96 60 21 71 67 14 1 10 70 86 
// 6 92 84 96 34 72 81 31 96 1 
// 66 21 71 47 94 55 81 23 38 80 
// 40 21 23 69 94 85 51 16 40 53 
// 89 85 32 28 96 9 9 68 80 37 
// 55 98 64 80 79 59 79 28 3 30 
// 74 57 55 59 88 38 50 8 17 72 
// 16 25 70 72 58 85 52 57 71 43 
// 24 90 77 71 73 79 59 57 75 
// 排序后：
// 1 1 3 4 6 6 8 9 9 10 14 
// 16 16 17 21 21 21 23 23 24 25 
// 28 28 30 31 32 33 34 36 37 37 
// 38 38 40 40 43 47 50 51 52 53 
// 55 55 55 57 57 57 57 58 58 59 
// 59 59 60 64 66 67 68 69 70 70 
// 71 71 71 71 72 72 72 73 74 75 
// 77 79 79 79 79 80 80 80 81 81 
// 81 82 84 85 85 85 86 88 88 89 
// 90 92 94 94 96 96 96 96 98 
// bubbleSort: 1.033ms

选择排序

选择排序，从数组的开头开始,将第一个元素和其他元素进行比较。检测完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从第二个位置继续。这个过程一直进行,当进行到数组的倒数第二个位置时,所有的数据便完成了排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
selectionSort() {
	let min;
	for (let outer = 0; outer <= this.dataStore.length - 2; outer++) {
		min = outer;

		// 在内循环中总会获得一个最小的值
		for (let inner = outer + 1; inner <= this.dataStore.length - 1; inner++) {
			if (this.dataStore[inner] < this.dataStore[min]) {
				min = inner;  // 得到最小数的索引
			}
		}
		this.swap(this.dataStore, outer, min);
	}
}

接下来是测试时间：

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
var arr2 = myArray.copyArr();

console.time('selectionSort');
arr2.selectionSort();
console.timeEnd('selectionSort');
console.log(arr2.toString());

// 排序前：
// 36 4 81 58 82 6 88 79 37 57 33 
// 96 60 21 71 67 14 1 10 70 86 
// 6 92 84 96 34 72 81 31 96 1 
// 66 21 71 47 94 55 81 23 38 80 
// 40 21 23 69 94 85 51 16 40 53 
// 89 85 32 28 96 9 9 68 80 37 
// 55 98 64 80 79 59 79 28 3 30 
// 74 57 55 59 88 38 50 8 17 72 
// 16 25 70 72 58 85 52 57 71 43 
// 24 90 77 71 73 79 59 57 75 
// 排序后：
// 1 1 3 4 6 6 8 9 9 10 14 
// 16 16 17 21 21 21 23 23 24 25 
// 28 28 30 31 32 33 34 36 37 37 
// 38 38 40 40 43 47 50 51 52 53 
// 55 55 55 57 57 57 57 58 58 59 
// 59 59 60 64 66 67 68 69 70 70 
// 71 71 71 71 72 72 72 73 74 75 
// 77 79 79 79 79 80 80 80 81 81 
// 81 82 84 85 85 85 86 88 88 89 
// 90 92 94 94 96 96 96 96 98 
// selectionSort: 1.397ms

插入排序

插入排序有两个循环。外循环将数组挨个移动,内循环对外循环中选中的元素以及它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小,那么数组元素会向右移动。插入排序的运行并非通过数据交换,而是通过将较大的数组元素移动到右侧,为数组左侧的较小元素腾出位置。

没有理解到吗？没关系，书上举了一个非常通俗易懂的🌰。

我让班里的每个学生上交一张写有他的名字、学生证号以及个人简介的索引卡片。学生交上来的时候是没有顺序的，但是我想让这些卡片按字母顺序拍好，这样就很容易地与班级花名册进行对照了。

我将卡片带回办公室，清理好书桌，然后拿起第一张卡片，卡片上的姓氏是 Smith 。我把它放到桌子的左上角，然后再拿起第二张卡片，这张卡片上的姓氏是 Brown 。我把 Smith 移右，把 Brown 放到 Smith 的前面。 下一张卡片是 Williams ，可以把它放到桌面的最右边，而不用移动其他任何卡片。 接下来是 Acklin 。这张卡片必须放在这些卡片的最前面，因此其他所有卡片必须向右移动一个位置来为 Acklin 这张卡片腾出位置。这就是插入排序的排序原理。

来看代码和运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
insertSort() {
	let temp, inner;
	for (let outer = 1; outer <= this.dataStore.length - 1; outer++) {
		temp = this.dataStore[outer];   // 将需要比较的数据暂存
		inner = outer;

		// 将数组右移
		while (inner > 0 && (this.dataStore[inner - 1] >= temp)) {
			this.dataStore[inner] = this.dataStore[inner - 1];
			--inner;
		}
		this.dataStore[inner] = temp;   // 将当前for循环中最小值放到左边
	}
}
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
var arr3 = myArray.copyArr();

console.time('insertSort');
arr3.insertSort();
console.timeEnd('insertSort');
console.log(arr3.toString());

// 排序前：
// 36 4 81 58 82 6 88 79 37 57 33 
// 96 60 21 71 67 14 1 10 70 86 
// 6 92 84 96 34 72 81 31 96 1 
// 66 21 71 47 94 55 81 23 38 80 
// 40 21 23 69 94 85 51 16 40 53 
// 89 85 32 28 96 9 9 68 80 37 
// 55 98 64 80 79 59 79 28 3 30 
// 74 57 55 59 88 38 50 8 17 72 
// 16 25 70 72 58 85 52 57 71 43 
// 24 90 77 71 73 79 59 57 75 
// 排序后：
// 1 1 3 4 6 6 8 9 9 10 14 
// 16 16 17 21 21 21 23 23 24 25 
// 28 28 30 31 32 33 34 36 37 37 
// 38 38 40 40 43 47 50 51 52 53 
// 55 55 55 57 57 57 57 58 58 59 
// 59 59 60 64 66 67 68 69 70 70 
// 71 71 71 71 72 72 72 73 74 75 
// 77 79 79 79 79 80 80 80 81 81 
// 81 82 84 85 85 85 86 88 88 89 
// 90 92 94 94 96 96 96 96 98 
// insertSort: 1.630ms

基本排序算法的计时比较

在上面的运行过程中，我们其实已经在数组长度为100的情况下进行了比较，可以看到这三种算法的执行事件差异并不大。接着我们来分别测试对1k个和10k个数据排序所花时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 长度为1000的情况
var numOfElements = 1000,
	myArray = new cArray(numOfElements);
myArray.randomSetArr();
var arr1 = myArray.copyArr(),
    arr2 = myArray.copyArr(),
    arr3 = myArray.copyArr();

console.time('bubbleSort');
arr1.bubbleSort();
console.timeEnd('bubbleSort');

console.time('selectionSort');
arr2.selectionSort();
console.timeEnd('selectionSort');

console.time('insertSort');
arr3.insertSort();
console.timeEnd('insertSort');

// bubbleSort: 14.968ms
// selectionSort: 2.077ms
// insertSort: 1.425ms

其实已经渐渐地有些差异了，不过还不大，我们接着增加长度

1
2
3
4
5
var numOfElements = 10000;

// bubbleSort: 843.945ms
// selectionSort: 67.561ms
// insertSort: 38.479ms

小结

10000个数字和1000个数字的测试结果一致，我们可以初步得出：选择排序和插入排序要比冒泡排序快，插入排序是这三种算法中最快的。不过这个结果是基于数据量比较大的时候，较小的数据量并不能比较出这三种排序算法的快慢。

下一次有时间再看看高级排序算法。

以上。