洛清寒前端进阶

# 排序算法和查找算法

# 一、基本概念

# 复杂度

O的概念，来描述算法的复杂度，简⽽⾔之，就是算法执⾏所需要的执⾏次数，和数据量的关系( 时间复杂度)， 占⽤额外空间和数据量的关系(空间复杂度)。

  • O(1) : 常数复杂度 (和数据量⽆关)
  • O(log n) :对数复杂度 (每次⼆分)
  • O(n) : 线性时间复杂度 （数组遍历⼀次）
  • O(n*log n) : 线性对数 （遍历+⼆分）
  • O(n^2) : 平⽅ 两层遍历
  • O(n^3) : ⽴⽅
  • O(2^n) : 指数
  • O(n!) : 阶乘

# 稳定性（针对排序算法而言）

数组中[ {name:'x', age:12}, {name:'y', age:12}]如果按照age排序，排序后，x和y的相对位置不变，我们成为稳定的算法，否则不稳定。

# 二、排序算法

# 1、冒泡排序

优点：稳定，比较次数已知；

缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。

# 原理

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

# 动态图

image

# 代码

比较n轮：

var arr = [23, 4, 5, 5, 7, 1, 3, 0, 6];
function bubbleSort(arr) {
	var n = arr.length;
	console.log(`初始:`, arr);
	// 比较n轮
	for (var i = 0; i < n - 1; i++) {
		// 内层循环是相邻元素两两比较，前面的元素如果大于后面的元素，就交换
		// j的值最大是n-2-i，即j <= n - 2 - i，也可以写成j < n - 1 - i
		for (var j = 0; j < n - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
			}
		}
		console.log(`第${i + 1}轮`, arr);
	}
	console.log(`排序结果:`, arr);
	return arr
}
bubleSort(arr);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

image

从上述的log打印中，可以看出来：在第7轮时就已经排好序了，所以从第8轮是无用操作。可以通过一个标记变量来判断是否已经排好序。








 



 


 
 
 







function bubbleSort(arr) {
	var n = arr.length;
	console.log(`初始:`, arr);
	// 比较n轮
	for (var i = 0; i < n - 1; i++) {
		// 内层循环是相邻元素两两比较，前面的元素如果大于后面的元素，就交换
		// j的值最大是n-2-i，即j <= n - 2 - i，也可以写成j < n - 1 - i
+		var success = true; // 假设这轮已排好序
		for (var j = 0; j < n - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
+				success = false; // 如果交换了则说明这轮没排好，还需要进行下一轮
			}
		}
+		if (success) {  // 如果success为true，则说明已经排好可以退出循环了
+			break;
+		}
		console.log(`第${i + 1}轮`, arr);
	}
	console.log(`排序结果:`, arr);
	return arr
}
bubleSort1(arr);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

image

# 复杂度

时间复杂度：两层循环，第1次遍历n次(n个元素)，第二次遍历n-1次，... 依次类推。因此，表达式如下：n + (n - 1) + (n - 2) + ... + 1 = n * (n + 1) / 2 = O(n^2)

空间复杂度：没有利用新的数组来帮助完成排序算法，我们认为其空间复杂度为O(1)

冒泡排序最好的情况下只需进行一趟排序，(n-1)次比较，此时的时间复杂度为O(n)，无需移动元素；最坏的情况下进行 n-1趟排序，时间复杂度为O(n^2)；冒泡排序是稳定的排序算法。

# 2、插入排序

# 原理

将初始序列中的第一个元素作为一个有序序列，然后将一个记录插入到已排好序的序列中，从而得到一个新的有序序列（将序列的第一个数据看成是一个有序的子序列，然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序）

重点：使用哨兵，用于临时存储和判断数组边界。

优点：稳定，快；

缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

# 动态图

image

# 代码

var arr = [23, 4, 5, 5, 7, 1, 3, 0, 6];
console.log(`初始:`, arr);
function insertSort(arr) {
    var n = arr.length;
    // 外层是要插入的元素，从arr[1]到arr[n-1],n轮
    for (var i = 1; i < n; i++) {
        // 内层是这个元素和已排序的元素进行一一比较，找到插入位置，j-1最小是0，j最大是i
        for (var j = i; j > 0; j--) {
            if (arr[j - 1] > arr[j]) {
                [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
            } else {
                break;  // 如果当前元素比前一个大，就直接退出本次内层循环
            }
        }
        console.log(`第${i}轮`, arr);
    }
    console.log(`排序结果:`, arr);
}
insertSort(arr);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

怎样找插入位置？就是判断前一个元素是否比当前元素大，如果是，则交换位置，然后继续判断前一个元素是否比当前元素大。

image

# 复杂度

其他说明：插入排序在最好的情况下时间复杂度为O(n)，比较次数为(n-1)次，移动元素次数是2(n-1)；最坏的情况下时间复杂度为O(n^2)； 插入排序是稳定的排序算法。

# 3、选择排序

# 原理

将初始序列(A[0] ~ A[n-1])作为待排序序列，第一趟在待排序序列(A[0] ~ A[n-1])中找到最小值元素，将其与第一个元素A[0]交换，这样子序列(A[0])已经有序，下一趟在排序在待排序子序列(A[1] ~ A[n-1])中进行。第i趟排序在待排序子序列(A[i-1] ~ A[n-1])中找到最小值元素，与该子序列中第一个元素A[i-1]交换。经过 n-1 趟排序后使得初始序列有序。

优点：比较次数与冒泡排序一样，数据移动次数比冒泡排序少；

缺点：相对之下还是慢。

# 动态图

image

# 代码

var arr = [23, 4, 5, 5, 7, 1, 3, 0, 6];
console.log(`初始:`, arr);
function selectSort(arr) {
    var n = arr.length;
    // 外层遍历,最多进行n-1趟
    for (var i = 0; i < n - 1; i++) {
        var m = i;  // m保存值最小的元素的下标
        for (var j = m + 1; j < n; j++) {  //j要取到最后一个元素,即arr[n-1]
            if (arr[j] < arr[m]) {
                m = j;  // 一直取到最小的m
            }
        }
        if (i != m) [arr[i], arr[m]] = [arr[m], arr[i]];  // 如果不等，则交换
        console.log(`第${i}轮`, arr);
    }
    console.log(`排序结果:`, arr);
}
selectSort(arr);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

image

# 复杂度

选择排序的最好、最坏和平均情况的时间复杂度都为O(n^2)，而且它还需交换元素(n-1)次和移动元素3(n-1)次；它是不稳定的排序算法。

# 4、快速排序

# 原理

快速排序是找出一个元素（理论上可以随便找一个）作为基准,然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

快排参考

优点：极快，数据移动少；

缺点：不稳定。

# 动态图

image

# 代码

var arr = [23, 4, 5, 5, 7, 1, 3, 0, 6];
console.log(`初始:`, arr);
function quickSort(arr, left, right) {
    if (left < right) {
        var pivot = arr[left],  // 基准元素，保存起来，相当于一个坑
            low = left,  // 初始arr[left]是一个坑
            high = right;
        while (low < high) {
            // 从右向左找小于pivot的数来填arr[low]
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high];  // 这时，arr[high]变成了新的坑
            // 从左向右找大于pivot的数来填arr[high]
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low];
        }
        // 当上面while循环结束了，low就等于hight
        arr[low] = pivot; // 这时，arr[low]变成了新的坑
        console.log(`内排`, arr);
        quickSort(arr, low + 1, right); // 递归右边的区间
        quickSort(arr, left, low - 1); // 递归左边的区间
    }
}
quickSort(arr, 0, arr.length - 1);
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

image

# 复杂度

在最好情况下，每次划分所取的基准都是当前无序区的”中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlogn)。 在最坏的情况下，即已经逆序排列的数组，复杂度为O(n^2)；

尽管快速排序的最坏时间为O(n^2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlogn)。快速排序是不稳定的排序算法。

image

# 三、递归

快排我们了解到，递归就是⾃⼰调⽤⾃⼰，形成⼀个调⽤栈，逐渐缩⼩⽬标，到达截⽌条件返回执⾏的逻辑。

# 1、数组打平 （扁平化）

Array.prototype.flat = function() {
    var arr = [];
    this.forEach((item,idx) => {
        if(Array.isArray(item)) {
            arr = arr.concat(item.flat()); //递归去处理数组元素
        } else {
            arr.push(item)   //非数组直接push进去
        }
    })
    return arr;   //递归出口
}
arr = [1,2,3,[4,5,[6,7,[8,9]]],[10,11]]
console.log(arr.flat())
1
2
3
4
5
6
7
8
9
10
11
12
13

# 2、爬楼

有⼀楼梯共10级，刚开始时你在第⼀级，若每次只能跨上⼀级或⼆级，要⾛上第10级，共有多少种⾛法？

其实就是个斐波那契数列，只有两种⽅式从第9层上⼀级，或者从第8级上⼆级， 9和8⼜各⾃⼜两种情况。最后推到3级楼梯，3级楼的两种⽅式1和2是固定的次数。

function stairs(n) {
    if(n === 0) {
        return 1;
    } else if (n < 0) {
        return 0
    }
    else {
        return stairs(n-1) + stairs(n-2)
    }
}
console.log(stairs(10))
1
2
3
4
5
6
7
8
9
10
11

# 四、查找算法

查找⽐较简单，我们先来看⼀个经典的⼆分查找有点类似幸运52的猜价格，⽐如让你在1和1000之间猜个数字，挨个猜是很蠢的，要先猜500，如果⼤了，那就是0~500 ，每次问题减半，很快就能查到。

// 循环版本
function binarySearch(arr, target) {
    var low = 0,
        high = arr.length - 1,
        mid;
    while (low <= high) {
        mid = Math.floor((low + high) / 2);
        if (target === arr[mid]) {
            return `找到了${target},在第${mid + 1}个`
        }
        if (target > arr[mid]) {
            low = mid + 1;
        } else if (target < arr[mid]) {
            high = mid - 1;
        }
    }
    return -1
}

// 递归版本
function binarySearch1(arr, target, low = 0, high = arr.length - 1) {
    const n = Math.floor((low + high) / 2);
    const cur = arr[n];
    if (cur === target) {
        return `找到了${target},在第${n + 1}个`;
    } else if (cur > target) {
        return binarySearch1(arr, target, low, n - 1);
    } else if (cur < target) {
        return binarySearch1(arr, target, n + 1, high);
    }
    return -1;
}

console.log(binarySearch([1, 2, 3, 4, 5, 7, 9, 11, 14, 16, 17, 22, 33, 55, 65], 4))
console.log(binarySearch1([1, 2, 3, 4, 5, 7, 9, 11, 14, 16, 17, 22, 33, 55, 65], 4))
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
Last Updated: 3/29/2020, 2:48:05 PM

← 动态规划 →