§ 冒泡排序

冒泡排序(Bubble Sort)是最易懂的排序算法,但是效率较低,生产环境中很少使用。

基本思想
  • 依次比较相邻的两个数,如果不符合排序规则,则调换两个数的位置。这样一遍比较下来,能够保证最大(或最小)的数排在最后一位。
  • 再对最后一位以外的数组,重复前面的过程,直至全部排序完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function bubbleSort(arr) {
var len = arr.length;
var i;
var j;
var stop;
var temp;

for (i=0; i<len-1; i++) {
for (j=0; j<len-1-i; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
  • 最佳情况:T(n) = O(n)
  • 最差情况:T(n) = O(n2)
  • 平均情况:T(n) = O(n2)

§ 选择排序

选择排序与冒泡排序类似,也是依次对相邻的数进行两两比较。不同之处在于,它不是每比较一次就调换位置,而是一轮比较完毕,找到最大值(或最小值)之后,将其放在正确的位置,其他数的位置不变。

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
function selectionSort(arr) {
var len = arr.length;
var i;
var j;
var temp;
var min;

for (i=0; i<len; i++) {
// 将当前位置记录为最小值
min = i;
for (j=i+1; j<len; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}

// 如果当前位置不是最小值,将其换为最小值
if (i !== min) {
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
return arr;
}
  • 最佳情况:T(n) = O(n2)
  • 最差情况:T(n) = O(n2)
  • 平均情况:T(n) = O(n2)

§ 快速排序

快速排序(quick sort)是公认最快的排序算法之一,有着广泛的应用。

基本思想
  • 先确定一个“支点”(pivot),将所有小于“支点”的值都放在该点的左侧,大于“支点”的值都放在该点的右侧,
  • 然后对左右两侧不断重复这个过程,直到所有排序完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function quickSort(arr) {
if (arr.length < 2) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i=0; i<arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
}
  • 最佳情况:T(n) = O(nlogn)
  • 最差情况:T(n) = O(n2)
  • 平均情况:T(n) = O(nlogn)

§ 插入排序

它将数组分成“已排序”和“未排序”两部分,一开始的时候,“已排序”的部分只有一个元素,然后将它后面一个元素从“未排序”部分插入“已排序”部分,从而“已排序”部分增加一个元素,“未排序”部分减少一个元素。以此类推,完成全部排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function insertionSort(arr) {
var len = arr.length;
var i;
var index;
var current;

for (i=0; i<len; i++) {
current = arr[i]; // 储存当前位置的值
index = i-1; // 待比较元素的下标

/*
* 当已排序部分的当前元素大于current,
* 就将当前元素向后移一位,再将前一位与current比较
*/
while(index>=0 && arr[index]>current) {
arr[index+1] = arr[index];
index--;
}
arr[index+1] = current;
}
return arr;
}
  • 最佳情况:输入数组按升序排列。T(n) = O(n)
  • 最坏情况:输入数组按降序排列。T(n) = O(n2)
  • 平均情况:T(n) = O(n2)

§ 合并排序

它的基本思想是,将两个已经排序的数组合并,要比从头开始排序所有元素来得快。因此,可以将数组拆开,分成n个只有一个元素的数组,然后不断地两两合并,直到全部排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 合并两个子数组
function merge(left, right) {
var result = [];
while(left.length && right.length) {
// 注意:判断的条件是小于或等于,如果只是小于,那么排序将不稳定.
var item = left[0] <= right[0] ? left.shift() : right.shift();
result.push(item);
}
return result.concat(left.length ? left: right);
}

function mergeSort(arr) {
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2);
var left = arr.slice(0, middle);
var right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
  • 最佳情况:T(n) = O(n)
  • 最差情况:T(n) = O(nlogn)
  • 平均情况:T(n) = O(nlogn)