文章目录
  1. 1. 冒泡排序
    1. 1.1. 1.基本排序
    2. 1.2. 2.次数优化
    3. 1.3. 3.轮次优化
  2. 2. 快速排序
    1. 2.0.1. 参考

冒泡排序

1.基本排序

对于数组内的每个元素,按照轮次和次数两两进行比较,最后得出有序的数组,其中比较次数和轮次都可以进行优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var arr = [3, 2, 1, 4, 5, 6, 7];
var m = 0; //控制 轮数
var n = 0; //控制
for (var i = 0; i < arr.length - 1; i++) {
//轮数
for (var j = 0; j < arr.length - 1; j++) {
// 次数
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
n++;
}
m++;
}
console.log(arr);
console.log("轮数 " + m); //6
console.log("轮数 " + n); //36

2.次数优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var arr = [3, 2, 1, 4, 5, 6, 7];
var m = 0; //控制 轮数
var n = 0; //控制
for (var i = 0; i < arr.length - 1; i++) {
//轮数
for (var j = 0; j < arr.length - 1 - i; j++) {
// 次数
//j的次数可以减少几次。 (每比较一轮,可以少比较一次)
//i: 第一轮为0;第二轮为1;第三轮为2;第四轮为3.....
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
n++;
}
m++;
}
console.log(arr);
console.log("轮数 " + m); //6
console.log("轮数 " + n); //21

3.轮次优化

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
var arr = [3, 2, 1, 4, 8, 6, 7];
var m = 0;
var n = 0;
var flag = true;

//轮数
for (var i = 0; i < arr.length - 1; i++) {
//次数
for (var j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
flag = false;
var tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
n++;
}
m++;
//判断:如果flag被修改了,说明没有排序完毕。如果一次都没有修改,就说明完成排序了。
if (flag) {
break;
}
}
console.log(arr);
console.log("轮数 " + m); // 轮数 6
console.log("次数 " + n); // 次数 21

快速排序

在数组中取一个数作为基准项,一般取中间的,没有正中间的这里向下取数,然后根据基准生成左右两边的数组,再分别对这两个数组进行排序,直到整个数组排列有序。

大致分三步:

1、找基准(一般是以中间项为基准)

2、遍历数组,小于基准的放在 left,大于基准的放在 right

3、递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function quickSort(arr) {
//如果数组<=1,则直接返回
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2); //向下
//找基准,并把基准从原数组删除
var pivot = arr.splice(pivotIndex, 1)[0];
//定义左右数组
var left = [];
var right = [];

//比基准小的放在left,比基准大的放在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));
}

参考

文章目录
  1. 1. 冒泡排序
    1. 1.1. 1.基本排序
    2. 1.2. 2.次数优化
    3. 1.3. 3.轮次优化
  2. 2. 快速排序
    1. 2.0.1. 参考