手写常见排序
# 手写常见排序
# 冒泡排序
冒泡排序的原理如下,从第一个元素开始,把当前元素和下一个索引元素进行比较。如果当前元素大,那么就交换位置,重复操作直到比较到最后一个元素,那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作,但是此时最后一个元素已经是最大数了,所以不需要再比较最后一个元素,只需要比较到 length - 1 的位置。
function bubbleSort(list) {
var n = list.length;
if (!n) return [];
for (var i = 0; i < n; i++) {
// 注意这里需要 n - i - 1
for (var j = 0; j < n - i - 1; j++) {
if (list[j] > list[j + 1]) {
var temp = list[j + 1];
list[j + 1] = list[j];
list[j] = temp;
}
}
}
return list;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 快速排序
快排的原理如下。随机选取一个数组中的值作为基准值,从左至右取值与基准值对比大小。比基准值小的放数组左边,大的放右边,对比完成后将基准值和第一个比基准值大的值交换位置。然后将数组以基准值的位置分为两部分,继续递归以上操作
function quickSort(list) {
var n = list.length;
if (n <= 1) return list;
var midIndex = Math.floor(n / 2);
var midVal = list[midIndex]; // 取中间的数
var left = [];
var right = [];
for (var i = 0; i < n; i++) {
if (i === midIndex) continue;
if (list[i] < midVal) {
left.push(list[i]);
} else {
right.push(list[i]);
}
}
// 递归
return quickSort(left).concat(quickSort(right));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21