这里用JavaScript实现冒泡排序、选择排序、插入排序、归并排序以及快速排序这些基本的排序算法
首先我们给本文约定一个实现的框架：定义一个ArrayList类里面包含排序数组声明、数组元素添加、排序算法实现以及数组输出的方法。
代码框架：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| function ArrayList(){
var array=[];
this.inputArraymember=function(){
var ins=0;
for(var i=0;i<10;i++){
ins=Math.floor(Math.random()*15+1);
array.push(ins);
}
};
this.相应的排序算法=function(){...算法的具体实现代码...};
this.toString=function(separator){
return array.join(separator);
};
}
var a = new ArrayList();
a.inputArraymember();
console.log("随机生成的原始数组为："+a.toString('-'));
a.bubbleSort();
console.log("排序后数组为："+a.toString('-'));
|
冒泡排序
用两层循环，第一层用来记录剩余的还未排序的数的个数，第二层用来在剩下的未排序的数中找到最大的数并将其放到未排序数的最后面（冒泡）。
代码实现：
1
2
3
4
5
6
7
8
9
10
| this.bubbleSort=function(){
var length=array.length;
for(var i=0;i<length;i++){
for(var j=0;j<length-1-i;j++){
if(array[j]>array[j+1]){
var t=array[j]; array[j]=array[j+1];array[j+1]=t;
}
}
}
};
|
冒泡排序的时间复杂度是O(n²)。将以上代码替换文章开始约定的代码框架中的“代码块替换部分”即可用于在调试工具中运行查看代码运行结果。
选择排序
思路很简单，每次都找出未排序的数当中最小的数并放在开头，直到所有数的位置确定下来。说清楚点就是从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| this.selectsort=function(){
var length=array.length,currentMin;
for(var i=0;i<length-1;i++){
currentMin=i;
for(var j=i;j<length;j++){
if(array[currentMin]>array[j]){
currentMin=j;
}
}
if(i!==currentMin){
var t=array[currentMin];
array[currentMin]=array[i];
array[i]=t;
}
}
};
|
可看出，选择排序也用了两个嵌套着的循环，所以时间复杂度也是O(n²)，是一种原址排序。
插入排序
从第二个数开始（因为第一个数只有一个，前面没得比。），与前面的数挨个比较，直到找到前一个数比当前值小，后一个数比当前值大的位置，让后将当前值置于此处，以此类推。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
| this.insertsort=function(){
var length=array.length, j,temp;
for(var i=1;i<length;i++){
j=i;
temp=array[i];
while(j>0&&array[j-1]>temp){
array[j]=array[j-1];
j--
}
array[j]=temp;
}
};
|
归并排序
时间复杂度为O(nlogn)。归并用的是分治的思想，将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着讲小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。
代码实现：
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
| this.mergeSort=function() {
array = mergeSortRec(array);
};
var mergeSortRec = function(array){
var length = array.length;
if (length === 1) {
return array;
}
var mid = Math.floor(length / 2),
left = array.slice(0, mid),
right = array.slice(mid, length);
return merge(mergeSortRec(left), mergeSortRec(right));
};
var merge = function(left, right) {
var result = [],
il = 0,
ir = 0;
while(il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
while (il < left.length) {
result.push(left[il++]);
}
while (ir < right.length) {
result.push(right[ir++]);
}
return result;
};
|
快速排序
时间复杂度为O(logn)。用的是分治的思想。
代码实现：
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
| this.quickSort = function(){
quick(array, 0, array.length - 1);
};
var partition = function(array, left, right) {
var pivot = array[Math.floor((right + left) / 2)],
i = left,
j = right;
console.log('pivot is ' + pivot + '; left is ' + left + '; right is ' + right);
while (i <= j) {
while (array[i] < pivot) {
i++;
console.log('i = ' + i);
}
while (array[j] > pivot) {
j--;
console.log('j = ' + j);
}
if (i <= j) {
console.log('swap ' + array[i] + ' with ' + array[j]);
swapQuickStort(array, i, j);
i++;
j--;
}
}
return i;
};
var swapQuickStort = function(array, index1, index2){
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
};
var quick = function(array, left, right){
var index;
if (array.length > 1) {
index = partition(array, left, right);
if (left < index - 1) {
quick(array, left, index - 1);
}
if (index < right) {
quick(array, index, right);
}
}
return array;
};
|