阅读 42

快速入门数据结构与算法之查找和排序算法

前言

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

查找算法

这里介绍两个查找算法,分别为:

  • 顺序查找
  • 二分查找

顺序查找

顺序查找,顾名思义,是按照顺序来访问和查找数据项。从列表的第一个数据开始,逐个比对数据项,如果找到了对应的数据项则查找成功,如果直到最后一个都没有发现要查找的项,那么查找失败。下面我们用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²)。而且还需要递归的开销,比冒泡效率都低了。所以选好中值对快速排序的影响非常大。

小结

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

关注下面的标签,发现更多相似文章
评论