排序算法
# 排序算法
# 1.冒泡排序
# 基本思路
1.依次比较相邻的两个数，如果第一个比第二个小，不变。如果第一个比第二个大，调换顺序。一轮下来，最后一个是最大的数2.对除了最后一个之外的数重复第一步，直到只剩一个数
# 图示
# 时间复杂度
O(n*n)
# 算法实现
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
function bubbleSort(arr){
var len=arr.length;
var i,j;
for(i=0;i<len;i++){
for(j=0;j<len-i-1;j++){
if(arr[j]>arr[j+1]) //两两之间进行比较
swap(arr,j,j+1);
}
}
return arr;
}
function swap(arr,i,j){
var tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
var arr=[1,12,6,3,5];
bubbleSort(arr);
console.log(arr);
</script>
</body>
</html>
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
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
# 执行结果
# 2.选择排序
# 基本思路
1.找出最小的数，和第一个交换位置2.在剩下的数中，找出最二小的数，放在第二个3.依次类推，排出顺序
# 图示
# 时间复杂度
O(n*n)
# 算法实现
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
function selectionSort(arr){
var len=arr.length;
var i,j,xmin;
for(i=0;i<len;i++){
xmin=i; //将当前值设为最小值
for(j=i+1;j<len;j++){
if(arr[j]<arr[xmin])
xmin=j; //在后面找到更小的值
}
if(i!=xmin)
swap(arr,i,xmin) //将找到的更小值进行交换
}
return arr;
}
function swap(arr,i,j){
var tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
var arr=[1,12,6,3,5];
selectionSort(arr);
console.log(arr);
</script>
</body>
</html>
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
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
# 执行结果
# 3.插入排序
# 基本思路
1.把数组分为[已排序]和[未排序]两部分,第一个数为[已排序]，其余为[未排序]2.从[未排序]抽出第一个数，和[已排序]部分比较，插入到合适的位置
# 图示
# 时间复杂度
O(n*n)
# 算法实现
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
function insertSort(arr){
var len=arr.length;
var i,j,val;
for(i=0;i<len;i++){
val=arr[i];
for(j=i-1;j>=0;j--){
if(arr[j]<val) break; //找到可以放的位置即跳出
arr[j+1]=arr[j];
}
arr[j+1]=val;
}
return arr;
}
var arr=[1,12,6,3,5];
insertSort(arr);
console.log(arr);
</script>
</body>
</html>
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
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
# 执行结果
# 4.归并排序(分而治之)
# 基本思路
1.不断将数组对半分，直到每个数组只有一个2.将分出来的部分重新合并3.合并的时候按顺序排列
# 图示
# 算法实现
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Document</title>
</head>
<body>
<script>
function merge(left, right) {
var res = [],
i = 0,
j = 0;
//合并两个数组（按照从小到大的顺序）
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
res.push(left[i++]);
} else {
res.push(right[j++]);
}
}
//数组拼接
return res.concat(left.slice(i)).concat(right.slice(j));
}
function mergeSort(arr) {
var len = arr.length;
var i, j;
//不断拆分至只有一个数
if (len <= 1) return arr;
var mid = Math.floor(len / 2);
var left = arr.slice(0, mid),
right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
var arr = [1, 12, 6, 3, 5];
arr = mergeSort(arr);
console.log(arr);
</script>
</body>
</html>
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
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
# 执行结果
# 5.快速排序
# 基本思路
1.以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边2.再按此方法对这两部分数据分别进行快速排序（递归进行）3.不能再分后退出递归，并重新将数组合并
# 图示
# 时间复杂度
- 平均是
O(n * logN)，最坏是O(n * n)
# 算法实现
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
function partition(arr,p,q){
var i = p;
var x= arr[p];
var j;
for(j=p+1;j<=q;j++){
if(arr[j]<=x){
++i;
swap(arr,i,j);
}
}
swap(arr,i,p);
return i; //返回划分中间位置
}
function quickSort(arr,p,q){
if(p<q){
var k = partition(arr,p,q); //确定划分中间位置
quickSort(arr,p,k-1); //对左边部分进行递归
quickSort(arr,k+1,q); //对右边部分进行递归
}
}
//交换函数
function swap(arr,i,j){
var tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
var arr=[1,12,6,3,5];
quickSort(arr,0,arr.length-1);
console.log(arr);
</script>
</body>
</html>
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
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
# 执行结果
# 6.随机化快速排序
# 基本思路
随机化快速排序只是在快排基础上将主元通过随机函数选取一下了。
关于 js 中随机产生【n , m】随机数实例：
在本例中，我们将取得介于 1 到 10 之间的一个随机数：
Math.floor(Math.random() * 10 + 1);
1
输出结果：
5
# 算法实现
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
//随机选取主元
function randk(arr,p,q){
var k = Math.floor(Math.random()*q+p);
swap(arr,p,k);
return partition(arr,p,q);
}
function partition(arr,p,q){
var i = p;
var x= arr[p];
var j;
for(j=p+1;j<=q;j++){
if(arr[j]<=x){
++i;
swap(arr,i,j);
}
}
swap(arr,i,p);
return i; //返回划分中间位置
}
function quickSort(arr,p,q){
if(p<q){
var k = randk(arr,p,q); //确定划分中间位置
quickSort(arr,p,k-1); //对左边部分进行递归
quickSort(arr,k+1,q); //对右边部分进行递归
}
}
//交换函数
function swap(arr,i,j){
var tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
var arr=[1,12,6,3,5];
quickSort(arr,0,arr.length-1);
console.log(arr);
</script>
</body>
</html>
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
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
# 执行结果