这是30天挑战的第一个系列的第一篇，从数据结构和算法开始。起因是我在b站上看到了有关30天挑战的视频，手痒的我也想挑战试试。至于选择数据结构和算法作为挑战对象，是因为我一直想学习基础知识，但是迟迟没有展开行动。
我还是不太擅于采用拍视频的方式来记录，还是先用博客的形式吧。
算法和数据结构可以学习的渠道很多，可以从书本、网站、视频中获取。我这次采用了知乎上关于如何学习数据结构的回答，选择了可视化数据结构和算法的学习网站visualgo.net。还有以前在Github上Fork的javascript-algorithms，visualgo.net上只有伪代码，必须要用一门编程语言去实现它。至于选什么编程语言并不重要，重要的是思想。
下面就切入正题，先从冒泡排序算法开始学起。
Bubble Sort
visualgo.net网站上给出的伪代码如下，仔细看伪代码其实并没有使用两层for循环，当然也不必太纠结
1
2
3
4
5
6
7
8
9
10
11
12
13
| do
swapped = false
for i = 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap(leftElement, rightElement)
swapped = true
while swapped
|
如果用javascript实现的话，参考BubbleSort.js将其转为ES5语法的话，代码如下
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
| function MyBubbleSort() {
this.sort = function(array) {
var swapped = false;
for (var i = 1; i < array.length; i++) {
swapped = false;
for (var j = 0; j < array.length - i; j++) {
if (array[j] > array[j+1]) {
var temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
swapped = true;
}
}
if(!swapped) {
return array;
}
}
return array;
}
}
var sorter = new MyBubbleSort();
var notSortedArr = [15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19];
var sortedArr = sorter.sort(notSortedArr);
console.log(sortedArr);
|
我从没写过Ruby，但是不妨碍我用Ruby实现一个冒泡排序算法。真的是除了写法不同，思想完全相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| def my_bubble_sort(array)
(array.size).times do |j|
j += 1
swapped = false
(array.size - j).times do |i|
if array[i] > array[i+1]
array[i], array[i+1] = array[i+1], array[i]
swapped = true
end
end
break if not swapped
end
array
end
list = [15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19]
my_bubble_sort(list)
print list, "\n"
|
最后是Java的版本
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
| import java.util.Arrays;
public class MyBubbleSort {
private static void sort(int[] arr) {
boolean swapped = false;
for (int i = 1; i < arr.length; i++) {
swapped = false;
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = true;
}
}
if (!swapped) {
return;
}
}
return;
}
public static void main(String[] args) {
int[] arr = {15, 8, 5, 12, 10, 1, 16, 9, 11, 7, 20, 3, 2, 6, 17, 18, 4, 13, 14, 19};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
|
为什么要用这么多语言实现一遍，也是想让自己加深对各种语言语法的印象。后面的挑战也会采用这样的形式，用javascript、ruby以及java各实现一个算法的版本。
最后是时间复杂度的计算。
外层循环执行N-1次。内层循环最多执行N次，最少执行1次，平均执行(N+1)/2次。
所以循环体内的比较交换约执行次数为（N-1)(N+1)/2 = (N^2 - 1)/2，按照计算平均时间复杂度的原则，去掉常数，去掉最高项系数，最后得出的结果是O(N^2)。
因为我的冒泡排序算法是经过优化过的，当执行第1次外层循环，内层循环执行N次后发现所有元素都无需交换，此时可以得出最优时间复杂度O(N)。
最差时间复杂度计算也很简单，外层循环执行N次，内层循环也执行N次，那也就是O(N^2)了。
空间复杂度始终是O(1)。所谓的空间复杂度，是指一个算法在运行过程中临时占用内存空间大小的度量。
举个冒泡排序在生活中的例子，大家一定有过在学校站队排高低的经历。这个时候就会采用冒泡排序算法，从高到低进行排列。
以上就是今天第一天的挑战，其实内容相当简单。最大的难度也就是临界条件的判断了。
