排序算法学习总结
2021/12/2 12:36:11
本文主要是介绍排序算法学习总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
冒泡排序
思路:
- 依次对所有元素中将相邻两个元素作比较,较大者置于后位。一轮结束后固定最后一位元素的位置
- 重复进行以上操作 n - 1 轮(n为元素个数),由于每轮交换会固定最后一位的位置,故每轮交换的次数为 n - 1 - i ( i 为当前轮数)
const bubbleSort = function (arr) { for (let i = 0; i < arr.length - 1; i++) { for (let j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { const temp = arr[j] arr[j] = arr[j + 1] arr[j + 1] = temp } } } return arr }
复杂度 O(n^2)
选择排序
思路:
- 创建最小值的临时索引值 indexMin 并指向为该轮第一个元素
- 遍历元素,若当前元素值小于临时索引值所指向的元素,则将该索引更改为当前元素并交换对应的元素值
- 每轮结束后固定第一位元素
- 继续下一轮选择,共执行 n 轮,每轮判断 n - i 次
const selectionSort = function (arr) { for (let i = 0; i < arr.length - 1; i++) { let indexMin = i for (let j = i; j < arr.length; j++) { if (arr[j] < arr[indexMin]) { indexMin = j } } const temp = arr[i] arr[i] = arr[indexMin] arr[indexMin] = temp } return arr }
复杂度 O(n^2)
插入排序
思路
- 外层遍历所有元素
- 将当前元素赋值给临时变量 temp
- 在当前元素以前的区间中从后往前进行内层遍历
- 遇到比临时变量大的值,则将该值往后移动一位并继续遍历,否则终止
- 终止后将遍历到的位置赋值为临时变量
- 继续下一轮外层遍历
const insertSort = function (arr) { for (let i = 1; i < arr.length; i++) { const temp = arr[i] let j = i while (j > 0) { if (arr[j - 1] > temp) { arr[j] = arr[j - 1] } else { break } j-- } arr[j] = temp } return arr }
复杂度 O(n^2)
略好于冒泡和排序算法
归并排序
思路(分而治之)
- 创建函数并传入 arr
- 先使用二分法对数组进行切分,并递归调用,直至切分后的数组仅有一个元素
- 创建输出结果数组
- 对左右数组进行比较,当二者都有元素时,对比第一位元素大小,将较小者推入输出数组
- 若有一边已为空,则将另一边元素依次推入输出数组
- 循环执行以上两步直到左右数组为空
const mergeSort = function (arr) { // 递归终点 if (arr.length === 1) return arr // “分” const mid = Math.floor(arr.length / 2) const left = mergeSort(arr.slice(0, mid)) const right = mergeSort(arr.slice(mid)) // “合” const res = [] while (left.length || right.length) { if (left.length && right.length) { res.push(left[0] < right[0] ? left.shift() : right.shift()) } else if (left.length) { res.push(left.shift()) } else if (right.length) { res.push(right.shift()) } } return res }
复杂度 O(nlogn)
其中:分 O(logn) 合 O(n)
快速排序 ⭐️⭐️⭐️
思路:
- 创建 左 右 数组
- 创建中间元素并赋值
- 循环整个数组
- 若当前循环元素小于中间元素,则放置于 左数组,反之放置于右数组
- 对左右数组进行递归调用,并连接二者,返回该值
const quickSort = function (arr) { if (arr.length === 1) return arr const left = [], right = [] const mid = arr[0] for (let i = 1; i < arr.length; i++) { if (arr[i] < mid) { left.push(arr[i]) } else { right.push(arr[i]) } } return [...quickSort(left), mid, ...quickSort(right)] }
复杂度 O(nlogn)
这篇关于排序算法学习总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南