导师计划--数据结构和算法系列（下）

[reng99]

数据结构和算法系列的课程分为上下两篇文章，上篇文章主要是讲解数据结构，可以戳导师计划--数据结构和算法系列（上）进行了解。本篇文章主要讲解的是基本算法，辅助的语言依旧是JavaScript。POST的本篇文章主要是扩展下我们在开发中的方式，发散下思维～

排序算法

排序介绍：

• 一旦我们将数据放置在某个数据结构（比如数组）中存储起来后，就可以根据需求对数据进行不同方式的排序：
  • 比如对姓名按字母排序
  • 对商品按照价格排序
  • etc.

排序算法又分为简单排序和高级排序。其中简单排序包括冒泡排序、选择排序和插入排序。高级排序包括希尔排序、归并排序和快速排序。【⚠️这里仅介绍了六种排序算法】

下面我们逐个排序算法来讲解下：

冒泡排序

之所以叫冒泡排序，是因为使用这种排序算法时，数据值就会像气泡那样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列，较大的值会浮动在数组的右侧，而较小的值则会浮动到数组的左侧。产生这种冒泡的现象是因为算法会多次在数组中移动过，比较相邻的数据，当左侧值大于右侧值的时候将它们互换。

⚠️ 后面讲到的排序算法如无说明，则默认为升序

比如下面的简单列表的例子。

E A D B H

经过第一次的排序后，列表会变成：

A E D B H

前面两个元素进行了交互。接下来再次排序：

A D E B H

第二个元素和第三个元素进行了交互。继续进行排序：

A D B E H

第三个元素和第四个元素进行了交换。这一轮最后进行排序：

A D B E H

因为第四个元素比最后一个元素小，所以比较后保持所在位置。反复对第一个元素执行上面的操作（已经固定的值不参与排序，如第一轮固定的H不参与第二轮的比较了），得到如下的最终结果：

A B D E H

相关的动效图如下：

关键代码如下：

bubbleSort(){
    let numElements = this.arr.length;
    for(let outer = numElements-1; outer >= 2; --outer){
        for(let inner = 0; inner <= outer-1; ++inner){
            if(this.arr[inner] > this.arr[inner+1]){
                this.swap(inner, inner+1); // 交换数组两个元素
            }
        }
    }
}

选择排序

选择排序从数组的开头开始，将第一个元素和其它元素进行比较。检查完所有的元素之后，最小的元素会被放在数组的第一个位置，然后算法会从第二个位置继续。这个过程进行到数组的倒数第二个位置时，所有的数据便完成了排序。

原理：

选择排序用到双层嵌套循环。外循环从数组的第一个元素移动到倒数第二个元素；内循环从当前外循环所指元素的第二个元素开始移动到最后一个元素，查找比当前外循环所指元素小的元素。每次内循环迭代后，数组中最小的值都会被赋值到合适的位置。

下面是对五个元素的列表进行选择排序的简单例子。初始列表为：

E A D H B

第一次排序会找到最小值，并将它和列表的第一个元素进行交换：

A E D H B

接下查找第一个元素后面的最小值（第一个元素此时已经就位），并对它们进行交换：

A B D H E

D已经就位，因此下一步会对E H进行互换，列表已按顺序排列好如下：

A B D E H

通过gif图可能容易理解：

关键代码如下：

selectionSort(){
    let min,
        numElements = this.arr.length;
    for(let outer = 0; outer <= numElements-2; outer++){
        min = outer;
        for(let inner = outer+1; inner <= numElements-1; inner++){
            if(this.arr[inner] < this.arr[min]){
                min = inner;
            }
        }
        this.swap(outer, min);
    }
}

插入排序

插入排序类似我们按照数字或字母的顺序对数据进行降序或升序排序整理～

原理：

插入排序也用了双层的嵌套循环。外循环将数组挨个移动，而内循环则对外循环中选中的元素以及内循环数组后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素要小，那么内循环的数组元素会向右移动，腾出一个位置给外循环选定的元素。

上面表达的晦涩难懂。简单来说，插入排序就是未排序的元素对已经排序好的序列数据进行合适位置的插入。如果还是不懂，结合下面的排序示例来理解下：

下面对五个元素进行插入排序。初始列表如下：

E B A H D

第一次插入排序，第二个元素挪动到第一位：

B E A H D

第二次插入排序是对A进行操作：

B A E H D

A B E H D

第三次是对H进行操作，因为它比之前的元素都大，所以保持位置。最后一次是对D元素进行插入排序了，过程和最后结果如下：

A B E D H

A B D E H

相关的gif图了解一下：

相关代码如下：

insertionSort(){
    let temp,
        inner,
        numElements = this.arr.length;
    for(let outer = 1; outer <= numElements-1; outer++){
        temp = this.arr[outer];
        inner = outer;
        while(inner > 0 && this.arr[inner-1] >= temp){
            this.arr[inner] = this.arr[inner-1];
            inner--;
        }
        this.arr[inner] = temp;
    }
}

希尔排序

希尔排序是插入排序的优化版，但是，其核心理念与插入排序不同，希尔排序会首先比较距离较远的元素，而非相邻的元素。

原理：

希尔排序通过定义一个间隔序列来表示数据在排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列，不过对于大部分的实际应用场景，算法用到的间隔序列可以提前定义好。

如下演示希尔排序中，间隔序列是如何运行的：

通过下面的gif图你也许会更好理解：

实现的代码：

shellSort(){
    let temp,
        j,
        numElements = this.arr.length;
    for(let g = 0; g < this.gaps.length; ++g){
        for(let i = this.gaps[g]; i < numElements; ++i){
            temp = this.arr[i];
            for(j = i; j >= this.gaps[g] && this.arr[j - this.gaps[g]] > temp; j -= this.gaps[g]){ // 之前的已经拍好序的了
                this.arr[j] = this.arr[j - this.gaps[g]];
            }
            this.arr[j] = temp; // 这里和上面的for循环是互换两个数据位置
        }
    }
}

🤔思考：[6, 0, 2, 9, 3, 5, 8, 0, 5, 4] 间隔为3的排序结果是什么呢？

归并排序

原理:

把一系列的排好序的子序列合并成一个大的有序序列。从理论上讲，这个算法很容易实现。我们需要两个排好序的子数组，然后通过比较数据的大小，先从最小的数据开始插入，最后合并得到第三个数组。然而，实际上操作的相当大的数据的时候，使用归并排序是很耗内存的，这里我们了解一下就行。

实现归并排序一般有两种方法，一种是自顶向下和自底向上的方法。

上面的gif图是自顶向下的方法，那么何为自顶向下呢？

自顶向下的归并排序算法就是把数组元素不断的二分，直到子数组的元素个数为一个，因为这个时候子数组必定是有序的，然后再将两个有序的序列合并成一个新的有序序列，连个有序序列又可以合并成另一个新的有序序列，以此类推，直到合并一个有序的数组。如下图：

自底向上的归并排序算法的思想是将数组先一个一个归并成两两有序的序列，两两有序的序列归并成四个四个有序的序列，以此类推，直到归并的长度大于整个数组的长度，此时整个数组有序。

⚠️注意：数组按照归并长度划分，最后一个子数组可能不满足长度要求，这种情况就要特殊处理了。

快速排序

快速排序是处理大数据集最快的排序算法之一，时间复杂度 最好的情况也也是和归并排序一样，为O(nlogn)。

原理：

快速排序是一种**分而治之（分治）**的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列，然后不断重复这个步骤，直到所有的数据都是有序的。

可以更清晰的表达快速排序算法步骤如下：

1. 选择一个基准元素（pivot，枢纽），将列表分隔成两个子序列；
2. 对列表重新排序，将所有小于基准值的元素放在基准值的前面，将所有大于基准值的元素放在基准值的后面；
3. 分别对较小元素的子序列和较大元素的子序列重复步骤1 和 2。

我们来用代码实现下：

// 快速排序
    quickSort(){
        this.arr = this.quickAux(this.arr);
    }

// aux函数 - 快排的辅助函数
quickAux(arr){
    let numElements = arr.length;
    if(numElements == 0){
        return [];
    }
    let left = [],
        right = [],
        pivot = arr[0]; // 取数组的第一个元素作为基准值
    for(let i = 1; i < numElements; i++){
        if(arr[i] < pivot){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
    return this.quickAux(left).concat(pivot, this.quickAux(right));
}

以上介绍了六种排序的算法，当然还有很多其它的排序算法，你可以到视频 | 手撕九大经典排序算法，看我就够了！文章中查看。

搜索算法

在列表中查找数据又两种方式：顺序查找和二分查找。顺序查找适用于元素随机排列的列表；而二分查找适用于元素已排序的列表。二分查找效率更高，但是我们必须在进行查找之前花费额外的时间将列表中的元素进行排序。

顺序查找

对于查找数据来说，最简单的就是从列表中的第一个元素开始对列表元素逐个进行判断，直到找到了想要的元素，或者直到列表结尾也没有找到。这种方法称为顺序查找或者线性查找。

这种查找的代码实现方式很简单，如下：

/*
* @param { Array } arr 目标数组
* @param { Number } data 要查找的数组
* @return { Boolean } 是否查找成功
**/
function seqSearch(arr, data){
	for(let i = 0; i < arr.length; i++){
		if(arr[i] === data){
			return true;
		}
	}
	return false;
}

当然，看到上面的代码，你也许会简化成下面的这样的代码：

function seqSearch(arr, data){
	return arr.indexOf(data) >= 0 ? true : false;
}

实现的方式有多种，但是原理都是一样的，要从第一个元素开始遍历，有可能会遍历到最后一个元素都找不到要查找的元素。所以，这是一种暴力查找技巧的一种。

那么，有什么更加高效的查找方法嘛？这就是我们接下来要讲的了。

二分查找算法

在开始之前，我们来玩一个猜数字游戏：

• 规则：在数字1-100之间，你朋友选择要猜的数字之后，由你来猜数字。你每猜一个数字，你的朋友将会作出下面三种回应之一：
  • 猜对了
  • 猜大了
  • 猜小了

这个游戏很简单，如果我们使用二分查找的策略进行的话，我们只需要经过短短的几次就确定我们要查找的数据了。

那么二分查找的原理是什么呢？

二分查找又称为折半查找，对有序的列表每次进行对半查找。就是这么简单@～@！

代码实现走一波：

/*
* @param { Array } arr 有序的数组 ⚠️注意：是有序的有序的有序的
* @param { Number } data 要查找的数据
* @return { Number } 返回查找到的位置，未查找到放回-1值
**/
function binSearch(arr, data){
	let upperBound = arr.length -1,
		 lowerBound = 0;
	while(lowerBound <= upperBound){
		let mid = Math.floor((upperBound + lowerBound) / 2);
		if(arr[mid] < data){
			lowerBound = mid + 1;
		}else if(arr[mid] > data){
			upperBound = mid + 1;
		}else{
			return mid;
		}
	}
	return -1; // 你朋友选要猜的数据在1-100范围之外
}

至此，导师计划--数据结构和算法已经完结。后期的话会在另一篇文章中补充一下各个算法的时间复杂度的比较（不作为课程讲解，要动笔算算的，而且也就是总结一个表而已～），当然你可以查看文章算法的时间复杂度并结合实际编写的代码来自行理解，并去总结。

后话

文章中的一些案例来自coderwhy的数据结构和算法系列文章，感谢其授权

绘图软件 Numbers，本篇文章用到的图片绘图稿感兴趣可以下载。

课程代码可以戳相关算法来获取

部分图片来自网络，侵删

参考

• 旧金山大学的David Galles教授实现的html5实现的排序动画

• coderwhy的数据结构和算法系列文章

• 《数据结构与算法JavaScript描述》