你还不会大厂必考的10个经典排序算法吗?

公众号:程序员白特,欢迎一起交流学习~

前言

众所周知,10个经典排序算法在大厂的校招、社招面试中频繁出现,那么今天我们就来用JS语言实现一下这10个经典排序算法吧。

概念

  • 排序算法:

排序算法是《数据结构与算法》中最基本的算法之一。它可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。


常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等

  • 大O表示法:

算法效率的计算方法常用大O表示法,大O表示法的推导方式如下:

(1)用常量1取代运行时间中的所有加法常量

(2)在修改后的运行次数函数中,只保留最高阶项

(3)如果最高存在且不为1,则去除与这个项相乘的常数

  • 各排序算法复杂度对比:

实现

1、冒泡排序

1、代码实现

// 冒泡排序
function bubbleSort(array) {// 1、获取数组的长度let length = array.length;for(let j=length-1; j>=0; j--) {//第一次进来:    i=0, 比较0和1的位置//最后一次进来:  i=length-2, 比较length-2和length-1的位置for(let i=0; i<j; i++) {if(array[i] > array[i+1]) {let temp = array[i];array[i] = array[i+1];array[i+1] = temp;}}}return array;
}
console.log(bubbleSort([1,8,11,90,2,7,8]));//[1,2,7,8,8,11,90]

2、选择排序

1、代码实现

function selectionSort(array) {// 1、获取数组长度let length = array.length;// 2、外层循环:从0位置开始取数据for(let j=0; j<length-1; j++) {let min = j;// 3、内层循环: 从min+1位置开始,和后面的数据进行比较for(let i=min+1; i<length; i++) {if(array[min] >= array[i]) {min = i;}}let temp = array[j];array[j] = array[min];array[min] = temp;}console.log(array);
}selectionSort([91,8,11,90,2,7,8])//[ 2,  7,  8, 8,11, 90, 91]

3、插入排序

1、代码实现

function insertionSort(array) {// 1、获取数组的长度let length = array.length;// 2、外层循环: 从第一个位置开始,向前面局部有序插入数据for(let i=1; i<length; i++) {// 3、内层循环: 获取第i个位置的数据,和前面的数据依次进行比较let temp = array[i];let j = i;while(array[j-1] > temp && j > 0) {array[j] = array[j-1];j--;}// 4、将j位置的数据,放置temp即可array[j] = temp;}console.log(array);
}
insertionSort([91,8,1,90,2,7,8]);//[1,  2,  7, 8,8, 90, 91]

4、希尔排序

1、代码实现

function shellSort(array) {// 1、获取数组长度let length = array.length;// 2、初始化的增量(gap -> 间隔/间隙)let gap = Math.floor(length / 2);// 3、while循环,gap不断减少while(gap >= 1) {// 4、以gap作为间隙,进行分组,对分组进行插入排序for(let i=gap; i<length; i++) {let temp = array[i];let j = i;while((array[j-gap] > temp) && (j > gap - 1)) {array[j] = array[j-gap];j-=gap;}// 5、将j位置的元素赋值为temparray[j] = temp;}// 6、gap不断缩小gap = Math.floor(gap / 2);}console.log(array);
}
shellSort([91,8,1,90,2,7,8]);//[1,  2,  7, 8, 8, 90, 91]

5、快速排序

1、代码实现

function swap(m, n, array) {let temp = array[m];array[m] = array[n];array[n] = temp;
}// 一、枢纽的选择
function median(left, right, array) {// 1、取出中间位置let center = Math.floor((left + right) / 2);if(array[left] > array[right]) {swap(left, right, array)}// 2、判断大小,并进行交换if(array[left] > array[center]) {swap(left, center, array);}if(array[center] > array[right]) {swap(center, right, array);}// 3、将center换到right-1的位置上swap(center, right-1, array);return array[right-1];
}// 二、快速排序的实现
function quickSort(array) {quick(0, array.length-1, array);return array;
}// 因为要传很多参数,所以另起一个函数
function quick(left, right, array) {if(left >= right) return;let pivot = median(left, right, array);let i = left;let j = right-1;while(true) {while(array[++i] < pivot) {}while(array[--j] > pivot) {}if(i < j) {swap(i, j, array);}else {break;}}swap(i, right-1, array);quick(left, i-1, array);quick(i+1, right, array);
}console.log(quickSort([91,8,1,90,2,7,8]));

6、堆排序

1、代码实现

function swap(tree, m, n) {let temp = tree[m];tree[m] = tree[n];tree[n] = temp;
}// 1、将每一层进行堆化
// (函数headify只考虑到局部(例如,左子树堆化了。右子树可能没堆化),所以整棵树堆化需要重新调用 buildTree函数)
function headify(tree, n, i) {if(i >= n) {return;}let c1 = Math.floor(2*i+1);let c2 = Math.floor(2*i+2);let max = i;// 如果有赋值,要用赋值的结果,否则会出错if(c1 < n && tree[c1] > tree[max]) {max = c1;}if(c2 < n && tree[c2] > tree[max]) {max = c2;}if(max !== i) {swap(tree, max, i);headify(tree, n, max);}
}// 2、建立一棵完全堆化成功的树(即若数字的顺序很乱,怎么把整棵树都 heapify,需要调用buildTree)
function buildTree(tree, n) {let lastNode = n-1;//最后一个节点的index值let parent = Math.floor((lastNode - 1) / 2);for(let i=parent; i>=0; i--) {headify(tree, n, i);}
}// 3、堆排序
function heapSort(tree, n) {buildTree(tree, n);let i;for(i=n-1; i>=0; i--) {swap(tree, i, 0);headify(tree, i, 0);}
}// 4、调用堆排序函数
let tree = [91,8,1,90,2,7,8];
let size = tree.length;
heapSort(tree, size);
console.log(tree);//[1,  2,  7, 8, 8, 90, 91]

7、归并排序

1、思路地址

https://www.bilibili.com/video/BV1Pt4y197VZ?from=search&seid=8783899578846664847

2、实现代码

// 归并排序
// 2、合并
function merge(arr, tempArr, left, mid, right) {// 标记左半区第一个未排序的元素let left_pos = left;// 标记右半区第一个未排序的元素let right_pos = mid + 1;// 临时数组的下标let pos = left;// 合并while(left_pos <= mid && right_pos <= right) {if(arr[left_pos] < arr[right_pos]) {tempArr[pos++] = arr[left_pos++];}else {tempArr[pos++] = arr[right_pos++];}}// 合并左半区剩余的元素while(left_pos <= mid) {tempArr[pos++] = arr[left_pos++];}// 合并右半区剩余的元素while(right_pos <= right) {tempArr[pos++] = arr[right_pos++];}// 把临时数组中合并后的元素复制到原来的数组while(left <= right) {arr[left] = tempArr[left];left++;}
}
// 1、划分
function mergeSort(arr, tempArr, left, right) {// 如果只有一个元素,那么不需要继续划分// 只有一个元素的区域,本身就是有序的,只需要被归并就可以if(left < right) {// 找中间点let mid = Math.floor((left + right) / 2);// 递归划分左半区mergeSort(arr, tempArr, left, mid);// 递归划分右半区mergeSort(arr, tempArr, mid + 1, right);// 调用合并函数merge(arr, tempArr, left, mid, right);}
}
let arr = [1,8,11,90,2,7,8];
let n = arr.length;let tempArr = [];
mergeSort(arr, tempArr, 0, n - 1);
console.log(arr);

8、计数排序

1、实现代码

// 计数排序
function countingSort(arr, maxValue) {let bucket = new Array(maxValue+1),sortedIndex = 0;arrLen = arr.length,bucketLen = maxValue + 1;for (var i = 0; i < arrLen; i++) {if (!bucket[arr[i]]) {bucket[arr[i]] = 0;}bucket[arr[i]]++;}for (var j = 0; j < bucketLen; j++) {while(bucket[j] > 0) {arr[sortedIndex++] = j;bucket[j]--;}}return arr;
}

9、桶排序

1、实现代码

// 桶排序
function bucketSort(arr, bucketSize) {if (arr.length === 0) {return arr;}let i;let minValue = arr[0];let maxValue = arr[0];for (i = 1; i < arr.length; i++) {if (arr[i] < minValue) {minValue = arr[i];                // 输入数据的最小值} else if (arr[i] > maxValue) {maxValue = arr[i];                // 输入数据的最大值}}//桶的初始化let DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   let buckets = new Array(bucketCount);for (i = 0; i < buckets.length; i++) {buckets[i] = [];}//利用映射函数将数据分配到各个桶中for (i = 0; i < arr.length; i++) {buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);}arr.length = 0;for (i = 0; i < buckets.length; i++) {insertionSort(buckets[i]);                      // 对每个桶进行排序,这里使用了插入排序for (var j = 0; j < buckets[i].length; j++) {arr.push(buckets[i][j]);                      }}return arr;
}

10、基数排序

1、实现代码

// 基数排序
let counter = [];
function radixSort(arr, maxDigit) {let mod = 10;let dev = 1;for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {for(let j = 0; j < arr.length; j++) {let bucket = parseInt((arr[j] % mod) / dev);if(counter[bucket]==null) {counter[bucket] = [];}counter[bucket].push(arr[j]);}let pos = 0;for(let j = 0; j < counter.length; j++) {let value = null;if(counter[j]!=null) {while ((value = counter[j].shift()) != null) {arr[pos++] = value;}}}}return arr;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2803398.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

vscode远程调试服务器的Python代码

目录 1 配置vscode远程阅读代码 2 打开conda环境 3 配置相应的调试环境 4 开始调试 这篇博客首先参考了我自己之前的两篇博客 vscode怎么查看python库的源代码/vscode打开conda环境 ubuntu上安装vscode&#xff0c;并远程开发与远程调试服务器代码 1 配置vscode远程阅读…

Intel PT简介以及perf 使用 Intel pt

文章目录 前言一、工作原理二、追踪执行流程三、追踪定时信息四、perf使用 intel pt4.1 perf record4.2 perf report4.3 perf script 五、与 Intel LBR 比较六、perf 对 Intel pt 的支持参考资料 前言 代码插装是最古老的性能分析方法之一。我们经常使用它。在函数开头插入pri…

Oerlikon欧瑞康LPCVD system操作使用说明

Oerlikon欧瑞康LPCVD system操作使用说明

C++从入门到精通 第五章(指针与引用)

写在前面&#xff1a; 本系列专栏主要介绍C的相关知识&#xff0c;思路以下面的参考链接教程为主&#xff0c;大部分笔记也出自该教程&#xff0c;笔者的原创部分主要在示例代码的注释部分。除了参考下面的链接教程以外&#xff0c;笔者还参考了其它的一些C教材&#xff08;比…

怎么把ppt压缩到10m以内?立刻学会~

在分享PPT文件时&#xff0c;文件大小通常会成为一个重要考虑因素。过大的文件不仅会增加传输和下载时间&#xff0c;还可能遇到一些网络限制。本文将介绍如何将PPT文件压缩到10M以内的方法&#xff0c;并详细介绍使用压缩工具的解决方案。 使用压缩工具的解决方法 工具一&…

http协议基础与Apache的简单介绍

一、相关介绍&#xff1a; 互联网&#xff1a;是网络的网络&#xff0c;是所有类型网络的母集因特网&#xff1a;世界上最大的互联网网络。即因特网概念从属于互联网概念。习惯上&#xff0c;大家把连接在因特网上的计算机都成为主机。万维网&#xff1a;WWW&#xff08;world…

Excel面试题及答案(1)

1.辅助列添加,快速填充方式填充隔行的编号;定位条件定位到空值后,右击---插入整行 2.利用通配符计算A3:A9含有车间的单元格个数(保留计算公式)。 3.利用身份证号提取 “性别”、“年月日”、“年龄” 性别:利用mid()方法,添加了一列辅助列,根据提取身份证后面第2位…

【Python笔记-设计模式】工厂模式

一、说明 (一) 解决问题 提供了一种方式&#xff0c;在不指定具体类将要创建的情况下&#xff0c;将类的实例化操作延迟到子类中完成。可以实现客户端代码与具体类实现之间的解耦&#xff0c;使得系统更加灵活、可扩展和可维护。 (二) 使用场景 希望复用现有对象来节省系统…

Leetcoder Day17| 二叉树 part06

语言&#xff1a;Java/C 654.最大二叉树 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下&#xff1a; 二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。 …

力扣随笔之两数之和 Ⅱ -输入有序数组(中等167)

思路&#xff1a;在递增数组中找出满足相加之和等于目标数 定义左右两个指针&#xff08;下标&#xff09;从数组两边开始遍历&#xff0c;若左右指针所指数字之和大于目标数&#xff0c;则将右指针自减&#xff0c;若左右指针所指数字之和小于目标数&#xff0c;则左指针自加&…

petalinux_zynq7 驱动DAC以及ADC模块之五:nodejs+vue3实现web网页波形显示

前文&#xff1a; petalinux_zynq7 C语言驱动DAC以及ADC模块之一&#xff1a;建立IPhttps://blog.csdn.net/qq_27158179/article/details/136234296petalinux_zynq7 C语言驱动DAC以及ADC模块之二&#xff1a;petalinuxhttps://blog.csdn.net/qq_27158179/article/details/1362…

【Unity】MySql +Navicat 安装教程

问题描述 在使用Unity开发的时候&#xff0c;有的时候我们是需要使用Mysql数据库的&#xff0c;本教程使用的MySql 和Navicat均为免安装版 ❶mysql安装 1.下载mysql解压至任意目录&#xff0c;此处以“C:\mysql-5.6.39-winx64”为例. mysql百度云连接&#xff1a; 链接&…

mybatis 集成neo4j实现

文章目录 前言一、引入jar包依赖二、配置 application.properties三、Mybatis Neo4j分页插件四、Mybatis Neo4j自定义转换器handler五、MybatisNeo4j代码示例总结 前言 MyBatis是一个基于Java语言的持久层框架&#xff0c;它通过XML描述符或注解将对象与存储过程或SQL语句进行…

有名管道的大小

管道&#xff1a;有名管道、无名管道 通信&#xff1a; 单工通信&#xff1a;固定的读端和写端 -- 广播 半双工通信&#xff1a;同一时刻&#xff0c;只有有一方写&#xff0c;另外一方读:对讲机 全双工通信&#xff1a;随时两方都能读写 -- 电话 特点&#xff1a; 管道属…

小红书x-s算法及补环境 单旋转验证码

前言 大家好呀!新的一年,先祝大家新年快乐咯.祝大家逆向,风控都一把过咯. 新年第一篇文章,后续会持续更新哦! 春晚见证了中国经济的新风口,今年春晚互联网企业赞助商就两家,小红书和京东.小红书类似国外的ins,有预感未来小红书会大火,所以写了这篇文章,有需要的加我,联系方式…

统计图扇形图绘制方法

统计图扇形图绘制方法 常用的统计图有条形图、柱形图、折线图、曲线图、饼图、环形图、扇形图。 前几类图比较容易绘制&#xff0c;饼图环形图绘制较难。 还有一种扇形图的绘制也较难&#xff0c;扇形图的各个变类&#xff0c;饼图、环形图、半圆图、玫瑰图等都是统计图扇形的变…

线程的同步(synchronized的原理和用法,解决线程同步时的通信问题)

线程的同步锁&#xff08;synchronized&#xff09; 为什么会出现线程的同步锁&#xff1f; 因为JVM虚拟机是抢占调度模型&#xff0c;当多个线程在同时访问一个资源时会发生两个线程争抢一个资源&#xff0c;在一个线程没有执行结束时&#xff0c;另一个线程抢到资源&#x…

动态规划--持续更新篇

将数字变成0的操作次数 1.题目 2.思路 在numberOfSteps函数中&#xff0c;首先设置f[0]为0&#xff0c;因为0已经是0了&#xff0c;不需要任何步骤。然后&#xff0c;使用一个for循环从1迭代到输入的整数num。对于每个整数i&#xff0c;如果i是奇数&#xff0c;则将f[i]设置为…

igolang学习3,golang 项目中配置gin的web框架

1.go 初始化 mod文件 go mod init gin-ranking 2.gin的crm框架 go get -u github.com/gin-gonic/gin 3.go.mod爆红解决

uniapp开发微信小程序跳转到另一个小程序中

注意&#xff1a;一开始我的云上务工模块是单独的tabbar界面&#xff0c;但是小程序跳转好像不能直接点击tabbar进行&#xff0c;所以我将这里改成了点击首页中的按钮进行跳转 点击这里进行小程序跳转 目录 基础讲解 uniapp小程序跳转的两个方法 调用说明&#xff08;半屏跳转…