程序员必备的几种常见排序算法和搜索算法总结
趣谈前端
共 4593字，需浏览 10分钟
·
2021-11-13 16:56
前言
冒泡排序及其优化 选择排序 插入排序 归并排序 快速排序 顺序搜索 二分搜索
正文
1. 冒泡排序及其优化
冒泡排序的实现思路是比较任何两个相邻的项, 如果前者比后者大, 则将它们互换位置.
为了更方便的展示冒泡排序的过程和性能测试,笔者先写几个工具方法,分别为动态生成指定个数的随机数组, 生成元素位置序列的方法,代码如下:
// 生成指定个数的随机数组
const generateArr = (num = 10) => {
let arr = []
for(let i = 0; i< num; i++) {
let item = Math.floor(Math.random() * (num + 1))
arr.push(item)
}
return arr
}
// 生成指定个数的元素x轴坐标
const generateArrPosX = (n= 10, w = 6, m = 6) => {
let pos = []
for(let i = 0; i< n; i++) {
let item = (w + m) * i
pos.push(item)
}
return pos
}
有了以上两个方法,我们就可以生成任意个数的数组以及数组项坐标了,这两个方法接下来我们会用到.
我们来直接写个乞丐版的冒泡排序算法:
bubbleSort(arr = []) {
let len = arr.length
for(let i = 0; i< len; i++) {
for(let j = 0; j < len - 1; j++) {
if(arr[j] > arr[j+1]) {
// 置换
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr
}
// 生成坐标
const pos = generateArrPosX(60)
// 生成60个项的数组
const arr = generateArr(60)
执行代码后会生成下图随机节点结构:
我们深入分析代码就可以知道两层for循环排序导致了很多多余的排序,如果我们从内循环减去外循环中已跑过的轮数,就可以避免内循环中不必要的比较,所以我们代码优化如下:
// 冒泡排序优化版
bubbleSort(arr = []) {
let len = arr.length
// 优化
for(let i = 0; i< len; i++) {
for(let j = 0; j < len - 1 - i; j++) {
if(arr[j] > arr[j+1]) {
// 置换
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr
}
经过优化的冒泡排序耗时:0.279052734375ms, 比之前稍微好了一丢丢, 但仍然不是推荐的排序算法.
2. 选择排序
选择排序的思路是找到数据结构中的最小值并将其放置在第一位,接着找到第二个最小值并将其放到第二位,依次类推.
选择排序代码如下:
selectionSort(arr) {
let len = arr.length,
indexMin
for(let i = 0; i< len -1; i++) {
indexMin = i
for(let j = i; j < len; j++){
if(arr[indexMin] > arr[j]) {
indexMin = j
}
}
if(i !== indexMin) {
[arr[i], arr[indexMin]] = [arr[indexMin], arr[i]]
}
}
return arr
}
点击排序时, 结果如下:
3. 插入排序
插入排序 的思路是每次排一个数组项,假定第一项已经排序,接着它和第二项比较, 决定第二项的位置, 然后接着用同样的方式决定第三项的位置, 依次类推, 最终将整个数组从小到大依次排序.
代码如下:
insertionSort(arr) {
let len = arr.length,
j,
temp;
for(let i = 1; i< len; i++) {
j = i
temp = arr[i]
while(j > 0 && arr[j-1] > temp) {
arr[j] = arr[j-1]
j--
}
arr[j] = temp;
}
}
执行结果如下:
4. 归并排序
归并排序是一种分治算法,其思想是将原始数组切分成较小的数组，直到每个小数组只有一个元素，接着将小数组归并成较大的数组，最后变成一个排序完成的大数组。
为了实现该方法我们需要准备一个合并函数和一个递归函数，具体实现如下代码：
// 归并排序
mergeSortRec(arr) {
let len = arr.length
if(len === 1) {
return arr
}
let mid = Math.floor(len / 2),
left = arr.slice(0, mid),
right = arr.slice(mid, len)
return merge(mergeSortRec(left), mergeSortRec(right))
}
// 合并方法
merge(left, right) {
let result = []
l = 0,
r = 0;
while(l < left.length && r < right) {
if(left[l] < right(r)) {
result.push(left[l++])
}else {
result.push(right[r++])
}
}
while(l < left.length) {
result.push(left[l++])
}
while(r < right.length) {
result.push(right[r++])
}
return result
}
5. 快速排序
从数组中选择中间项作为主元 创建两个指针，左边一个指向数组第一项，右边一个指向数组最后一项，移动左指针直到我们找到一个比主元大的元素，移动右指针直到找到一个比主元小的元素，然后交换它们的位置，重复此过程直到左指针超过了右指针 算法对划分后的小数组重复1，2步骤，直到数组完全排序完成。
代码如下：
// 快速排序
quickSort(arr, left, right) {
let index
if(arr.length > 1) {
index = partition(arr, left, right)
if(left < index - 1) {
quickSort(arr, left, index -1)
}
if(index < right) {
quickSort(arr, index, right)
}
}
}
// 划分流程
partition(arr, left, right) {
let part = arr[Math,floor((right + left) / 2)],
i = left,
j = right
while(i <= j) {
while(arr[i] < part) {
i++
}
while(arr[j] > part) {
j--
}
if(i <= j) {
// 置换
[arr[i], arr[j]] = [arr[j], arr[i]]
i++
j--
}
}
return i
}
7. 顺序搜索
之所以说顺序搜索效率低是因为每次都要从数组的头部开始查询，直到查找到要搜索的值，整体查询不够灵活和动态性。顺序搜索代码实现如下：
sequentialSearch(arr, item) {
for(let i = 0; i< arr.length; i++) {
if(item === arr[i]) {
return i
}
}
return -1
}
8. 二分搜索
找出数组的中间值 如果中间值是待搜索的值，那么直接返回中间值的索引 如果待搜索的值比中间值小，则返回步骤1，将区间范围缩小，在中间值左边的子数组中继续搜索 如果待搜索的值比选中的值大，则返回步骤1，将区间范围缩小，在中间值右边的子数组中继续搜索 如果没有搜到，则返回-1
binarySearch(arr, item) {
// 调用排序算法先对数据进行排序
this.quickSort(arr)
let min = 0,
max = arr.length - 1,
mid,
el
while(min <= max) {
mid = Math.floor((min + max) / 2)
el = arr[mid]
if(el < item) {
min = mid + 1
}else if(el > item) {
max = mid -1
}else {
return mid
}
}
return -1
}
其实还有很多搜索算法，笔者在js基本搜索算法实现与170万条数据下的性能测试有具体介绍。
参考文献：Learning JavaScript Data Structures and Algorithms
更多推荐
评论