前言

本篇将会继续基于线性结构介绍几种常见的查找和排序算法。话不多说，我们开始吧。

查找算法

这里介绍两个查找算法，分别为：

• 顺序查找
• 二分查找

顺序查找

顺序查找，顾名思义，是按照顺序来访问和查找数据项。从列表的第一个数据开始，逐个比对数据项，如果找到了对应的数据项则查找成功，如果直到最后一个都没有发现要查找的项，那么查找失败。下面我们用JavaScript代码来实现一下这个算法

function seqSearch(item, array) {
	let flag = false,
		i = 0;
	while (i < array.length && !flag) {
		if (array[i] === item) {
			flag = true;
		}
		i++;
	}
	return flag;
}
console.log(seqSarch(7, [2, 6, 5, 7, 4, 9, 3])); // true

算法分析： 在查找算法中，主要的计算步骤就是数据项的比对，因此比对次数决定了算法的复杂度，当需要查找的数据项就在第一个时，只需比对一次，算法复杂度就为O(1),如果需要查找的数据项不在列表中，那么就需要比较n次，算法复杂度就变成了O(n)。所以顺序查找的算法复杂度是O(n).

二分查找

二分查找是基于有序表的算法。其基本原理是从列表的中间开始查找，如果列表中间项与查找项匹配成功则查找结束，如果不匹配，那就比对一下查找项和中间项的大小，如果查找项大于中间项，则其查找的结果只可能出现在后半部分（当然，是以顺序排列的列表为基础），那么我们就继续从后半部分的中间项开始查找，反之，如果查找项小于中间项，则其查找结果只可能出现在前半部分，那么我们就继续从前半部分的中间项开始查找。以此类推，每次都会将比对范围缩小一半，直至查找到或最终都未找到退出。下面我们用JavaScript代码来实现一下

function binarySearch(item, array) {
	let first = 0,
		last = array.length - 1,
		flag = false;
	while (first <= last && !flag) {
		let mid = Math.floor((first + last) / 2);
		if (array[mid] === item) {
			flag = true;
		} else if (array[mid] < item) {
			first = mid + 1;
		} else if (array[mid] > item) {
			last = mid - 1;
		}
	}
	return flag;
}
console.log(binarySearch(6, [1, 2, 3, 4, 5, 6, 7, 8, 9])); // true

算法分析：由于二分查找的每次比对都将下一步的比对范围缩小一半，当比对足够多的次数后，比对范围内就会仅剩余1个数据项，所以n/2^i = 1，所以二分查找的算法复杂度是O(log n)。

虽然二分查找的算法复杂度优于顺序查找，但是它是基于有序表的，也就是说也要考虑排序的开销，所以在选择算法时还是需要根据实际应用来考虑.

排序算法

下面我们将介绍六个常用的排序算法，它们分别是：

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 归并排序
• 快速排序

冒泡排序

冒泡排序是通过多趟两两相邻的比较和交换实现整表排序的，即每一趟将两两相邻的数据项都进行比较，如果后面的数据项小于前面的数据项，则这两个数据项交换位置，反之则不做操作。经过这一趟，最大的一项会被放到列表的最后，进行n-1趟后，整个列表排序完成，这样每趟的最大项一步一步移到最后，就像气泡一个一个从水底浮到水面上一样，所以叫冒泡排序，下面我们用JavaScript代码实现一下

function bubbleSort(array) {
	for (let i = 0; i < array.length - 1; i++) {
		for (let j = 0; j < array.length - 1 - i; j++) {
			if (array[j] > array[j + 1]) {
				let temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}
	return array;
}
console.log(bubbleSort([8, 9, 4, 1, 3, 2, 7, 5])); // [1, 2, 3, 4, 5, 7, 8, 9]

算法分析：冒泡排序不管开始列表的顺序是什么样的，总会比对n-1趟，随着趟数的增加，比对次数会从n-1减到1，比对次数是1~n-1的累加，即(n²-n)/2,所以比对的时间复杂度为O(n²)。交换的时候每次包含三次赋值语句，最好的情况下交换次数为0，最差的情况下每次都进行交换，所以交换次数的时间复杂度也是O(n²)。所以冒泡排序的时间复杂度为O(n²)。

冒泡排序是一个效率较差的排序算法，但是它有一点优势，即无需任何额外的存储空间开销。

选择排序

选择排序在冒泡排序的基础上进行了改进，它依旧比对多趟，但是在交换上做了优化，即记录本趟最小项的位置，到本趟最后再与本趟的第一项进行交换，这样每趟只需进行一次交换，JavaScript的代码实现如下

function selectSort(array) {
	for (let i = 0; i < array.length - 1; i++) {
		let min = i;
		for (let j = i + 1; j < array.length; j++) {
			if (array[j] < array[min]) {
				min = j;
			}
		}
		let temp = array[min];
		array[min] = array[i];
		array[i] = temp;
	}
	return array;
}
console.log(selectSort([9, 8, 7, 6, 5, 4, 3, 2, 1])); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

算法分析：选择排序和冒泡排序再比对的时候是一样的，即总会比对n-1趟，所以选择排序的对比次数的时间复杂度也是O(n²)，但是它的交换次数变为每趟一次，多以交换次数的时间复杂度减为O(n)。所以选择排序的时间复杂度还是O(n²)。

插入排序

插入排序维持一个始终在列表前部的子列表，然后逐步扩大，直到整个列表排序完成。也就是从第二个数据项开始，使这个数据项与其前面的数据项逐个比对，并插入到小于其值得后面。这样一直到最后一个数据被插入到对应得位置，排序完毕。下面我们用JavaScript的代码实现一下

function insertSort(array) {
	for (let i = 1; i < array.length; i++) {
		let item = array[i],
			index = i;
		while (index > 0 && array[index - 1] > item) {
			array[index] = array[index - 1];
			index--;
		}
		array[index] = item;
	}
	return array;
}
console.log(insertSort([8, 9, 4, 1, 3, 2, 7, 5])); // [1, 2, 3, 4, 5, 7, 8, 9]

算法分析：插入排序会经过n-1项的对比和插入，最差情况每次都和子列表中的所有项进行比对，总的比对次数与冒泡排序相同，时间复杂度也是O(n²)。最好情况排序前就是已经排序好的列表，每趟只需要比对1次，时间复杂度为O(n)，所以插入排序的时间复杂度为O(n²)。

希尔排序

希尔排序以插入排序作为基础，将列表以一定的间隔分为几个子列表，并给子列表分别执行插入排序。这样，随着子列表逐渐接近有序，插入排序的比对次数就会越少。比如一共9个数，间隔为3，那么第一个第四个第七个是一个子列表，第二个第五个第八个是一个子列表，第三个第六个第九个是一个子列表，他们分别进行插入排序，之后改变间隔为为2，这样子列表数会减小，最后随着间隔数减为1，就剩一个子列表即整个列表，这时对它进行插入排序，因为子列表都接近有序，所以只需要换几个值就可以排好序。它的JavaScript代码实现如下

function shellSort(array) {
	let interval = Math.floor(array.length / 2);
	while (interval > 0) {
		for (let start = 0; start < interval; start++) {
			gapInsertSort(array, start, interval);
			start = Math.floor(start / 2);
		}
	}
}
function gapInsertSort(array, start, gap) {
	for (let i = start + gap; i < array.length; i += gap) {
		let item = array[i],
			index = i;
		while (index > 0 && array[index - gap] > item) {
			array[index] = array[index - gap];
			index -= gap;
		}
		array[index] = item;
	}
}
console.log(shellSort([9, 8, 7, 6, 5, 4, 3, 2, 1])); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

算法分析：希尔排序虽然以插入排序为基础，但是由于每趟都使列表接近有序，这样会减少很多原先需要进行的无效的对比，所以是较好于插入排序的。对希尔排序的详尽分析较复杂，如果有兴趣可以自行百度探索了解。它的时间复杂度是介于O(n)和O(n²)之间。

归并排序

归并排序是递归算法，其思路是将数据表持续分为两半，对两半分别进行归并排序。咱们用上一章的递归知识来分析一下它：首先，基本结束条件是当数据表仅一个元素的时候，这时候它肯定是排好序的，直接返回；通过将数据表分为两半缩小规模，然后两半分别调用自身，排好后再进行归并。下面我们用JavaScript代码来实现一下

function mergeSort(array) {
	if (array.length <= 1) {
		return array
	}
	let mid = Math.floor(array.length / 2),
	        left = mergeSort(array.slice(0, mid)),
		right = mergeSort(array.slice(mid, array.length)),
		sortArry = [];
	while (left.length !== 0 && right.length !== 0) {
		if (left[0] < right[0]) {
			sortArry.push(left.shift());
		} else {
			sortArry.push(right.shift());
		}
	}
	if (left.length !== 0) {
		sortArry = sortArry.concat(left);
	} else if (right.length !== 0) {
		sortArry = sortArry.concat(right);
	}
	return sortArry;
}
console.log(mergeSort([8, 9, 4, 1, 3, 2, 7, 5])); // [1, 2, 3, 4, 5, 7, 8, 9]

算法分析：归并排序分为分裂和归并两个过程，我们通过二分查找的类比可以知道分裂过程的时间复杂度为O(log n)，归并的过程中所有数据都会被比较和放入数组一次，所以其时间复杂度为O(n)，综合起来看，每个分裂的部分都进行一次时间复杂度为O(n)的归并，所以归并排序总的时间复杂度为O(nlog n)。

快速排序

快速排序也是一个递归算法，它的思路是随机选择一个数据项的值我们将其作为中值，根据它将数据表分为两半，即小于中值的一半和大于中值的一半，然后每个部分分别再进行快速排序。我们再用上一章的知识来分析一下这个算法：首先，基本结束条件依然是当数据表中只有1个数据项的时候，这时肯定时排好序的，然后根据中值将数据表分为两部分缩小规模，最后将两部分别调用自身进行排序（和归并排序的思想差不多哈）。

快速排序分裂数据表时的操作是比较复杂的，在这里详细说一下。通俗的说就是左右各有一个标，就像两个箭头一样，左标向右移，右标向左移。那什么时候停止呢？

左标：

• 1.碰到比中值大的值
• 2.移动到右标的右侧

右标：

• 1.碰到比中值小的值
• 2.移动到左标的左侧

当两标都达到了各自的第一个条件，那么把两个标所指的值互换，然后继续移动；有一个标达到了第二个条件（即此位置为中值位置），则将此时这个标指的值与中值互换。

好了，逻辑捋清楚了，我们用JavaScript代码实现一下

let arr = [9, 8, 7, 6, 5, 4, 3, 2, 1]
function quickSort(array) {
	quickSortRecursion(array, 0, array.length - 1)
}
function quickSortRecursion(array, first, last) {
	if (first < last) {
		const splitPoint = division(array, first, last)
		quickSortRecursion(array, first, splitPoint - 1)
		quickSortRecursion(array, splitPoint + 1, last)
	}
}
function division(array, first, last) {
	let midValue = array[first],
		leftMark = first + 1,
		rightMark = last,
		flag = false
	while (!flag) {
		while (
			leftMark <= rightMark &&
			array[leftMark] <= midValue
		) {
			leftMark++
		}
		while (
			rightMark >= leftMark &&
			array[rightMark] >= midValue
		) {
			rightMark--
		}
		if (rightMark < leftMark) {
			flag = true
		} else {
			let temp = array[leftMark]
			array[leftMark] = array[rightMark]
			array[rightMark] = temp
		}
	}
	
	let temp = array[first]
	array[first] = array[rightMark]
	array[rightMark] = temp

	return rightMark
}
quickSort(arr)
console.log(arr) // [1, 2, 3, 4, 5, 6, 7, 8, 9]

算法分析：快速排序的时间复杂度和中值的选取有关，如果分裂的时候总能把数据表分为相等的两部分，那么分裂的时间复杂度就是O(log n)，而移动的时候则是需要将每个数据项都与中值进行对比，所以移动的时间复杂度为O(n)，综合起来就是O(nlog n)。但是如果中值取值过于偏离中部，一部分始终没数据，那么时间复杂度就变成了O(n²)。而且还需要递归的开销，比冒泡效率都低了。所以选好中值对快速排序的影响非常大。

小结

本章简单介绍了几种常见的而且经典的查找和排序算法，作者尽量使用通俗的话来使其更加容易理解。这些算法都是一些很常用的算法，我们都应该掌握它们。这些算法没有绝对的优劣之分，在实际应用中应该灵活的运用，根据不同的场景选择不同的算法，这样才能真正的提高代码的效率。如果觉得作者写的还行，可以给个赞鼓励一下。如有错误请尽管指出，作者会积极采纳，我们共同进步，加油！！！