《算法与数据结构》整理6大排序算法供offer！

6种排序如下

冒泡排序

计数排序

快速排序

归并排序

插入排序

选择排序

时间复杂度如下

冒泡排序：star:

这个名字的由来是因为它像泡沫一样漂浮。想一想，就是每次比较两个相邻元素的大小，然后慢慢‘浮动’。

「时间复杂度O(n^2)」

思路

比较相邻元素，如果前者大于后者，则两个交换位置。

对每对相邻元素执行相同的操作，从第一对到最后一对，使最后一个元素是最大的元素。

对n个元素重复上述步骤，每次循环排除当前的最后一个。

重复步骤1~3，直至排序完成。

动画

冒泡排序

代码实现

//最外层循环控制的内容是循环次数

//每次比较的内容是相邻两个的大小关系

让冒泡排序=函数(arr) {

让len=arr.length

for (令i=0; i len - 1; i++) {

for (让j=0; j len - 1 - i; j++) {

if (arr[j] arr[j + 1]) { //从大到小

[arr[j], arr[j + 1]]=[arr[j + 1], arr[j]]

}

}

}

返回目的地

}

让arr=[2, 9, 6, 7, 4, 3, 1, 7]

安慰。日志（冒泡排序（arr））

计数排序

从名字就知道，它的思想是用数组元素作为数组的下标，然后用一个临时数组来统计该元素出现的次数。

数组中的数据必须是整数，并且最大值和最小值的差值不能太大。对于**“如果数据为负，我实施的解决方案已对其进行了优化”**。

「时间复杂度：O(n+k)」

思路

1.计算差值d，最小值小于0，加上add本身

2、创建统计数组，统计对应元素的个数

3、统计数组变形，后面的元素等于前面元素的和，就是排名数组

4、遍历原数组，从统计数组中找到正确的位置，输出到结果数组

动画

计数排序

代码实现

//按数量排序

让计数排序=函数(arr) {

令min=arr[0],

最大值=arr[0],

长度=arr.长度；

//求最大值和最小值

for(让i=0; i len; i++) {

max=Math.max(arr[i], max)

min=Math.min(arr[i], min)

}

//1.计算差值d，最小值小于0，加上add本身

让d=最大值- 最小值，

添加=分钟0 ？ -分钟： 0；

//2.创建一个统计数组，统计对应元素的个数

让countArray=new Array(d+1+add).fill(0)

for(令i=0; i 长度； i++){

让demp=arr[i] - min + add

countArray[ demp ] +=1

}

//3.统计数组变形，后面的元素等于前面元素的和，就是排名数组

令总和=0；

//这里需要遍历的是countArray数组的长度

for(令i=0; i d+1+add; i++){

总和+=countArray[i]

countArray[i]=总和；

}

让res=新数组(len)

//4.遍历原数组，从统计数组中找到正确的位置，输出到结果数组

for(令i=0; i 长度； i++){

让demp=arr[i] -min + add

res[ countArray[demp] -1 ]=arr[i]

countArray[demp] --;

}

返回资源

}

让arr=[2, 9, 6, 7, 4, 3, 1, 7,0,-1,-2]

安慰。日志（计数排序（arr））

快速排序：star:

基本思想：通过一次排序将待排序的记录分成两个独立的部分，并且一部分记录的关键字小于另一部分记录的关键字，然后可以将两部分记录分别排序实现整个序列。顺序。

「时间复杂度：O(nlogn)」

思路

选择数组中间的数字作为底数，并将这个底数从数组中取出

准备两个数组容器，遍历数组，将其与基数一一比较，较小的放入左侧容器，较大的放入右侧容器；

递归处理两个容器的元素，将处理后的数据和基数按照大小组合成一个数组，返回。

优化：三数取中,交换分割

三数取中：

在快速排序的过程中，每次我们都需要以一个元素作为基准值，并用这个数字将序列分为两部分。这里我们采用三个数取中间的方法，即取左端、中间、右端三个数，然后排序，以中间的数为基准值。

根据枢纽值进行分割：

https://juejin.cn/post/6844903657616441352

动画

快速排序

代码实现

让快速排序=函数(arr) {

//递归退出是数组长度为1

if (arr.length=1) 返回arr

//获取中间值的索引，使用Math.floor向下取整；

让索引=数学。楼层（到达长度/2）

//使用splice截取中间值，第一个参数为截取的索引，第二个参数为截取的长度；

//如果pivot=arr[索引];这里使用的话，会出现无限递归错误；

//splice影响原数组，splice影响原数组，应该删除

让pivot=arr.拼接（索引，1）[0]，

左=[]，

右=[]；

for (let i=0; i arr.length; i++) {

if (pivot arr[i]) {

左边。推(arr[i])

} 别的{

正确的。推(arr[i])

}

}

return fastSort(left).concat([pivot], fastSort(right));

}

//令arr=[2, 9, 6, 7, 4, 3, 1, 7]

//安慰。日志（快速排序（arr））

归并排序：star:

将两个已排序的序列合并为一个已排序的序列，我们称之为“合并”

基本思想及流程：先递归分解序列，然后合并序列（分而治之思维的典型应用）

「时间复杂度： O(nlog(n))」

思路

将一个数组分为A、B两组，继续分割两组，直到每组只有一个元素。

群体按照分裂的过程逐渐合并。由于每个组最初只有一个元素，因此可以认为组内是有序的，而合并组可以看作是合并两个有序数组的过程。

对左右小数列重复第二步，直到每个间隔中只有一个数字。

动画

合并排序

代码实现

const merge=(left, right)={ //合并数组

让结果=[]

//使用shift()方法偷懒，删除第一个元素，并返回值

while (左.长度右.长度) {

if (左[0]=右[0]) {

结果。推(左.shift())

} 别的{

结果。推(右.shift())

}

}

while (左.长度) {

结果。推(左.shift())

}

while (右.长度) {

结果。推(右.shift())

}

返回结果

}

让mergeSort=函数(arr) {

if (arr.长度=1)

返回目的地

让中=数学。楼层（到达长度/2）

//分割数组

让左=arr。切片（0，中间），

右=到达。切片（中）；

让mergeLeftArray=mergeSort(左),

mergeRightArray=mergeSort(右)

返回合并（mergeLeftArray，mergeRightArray）

}

让arr=[2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]

安慰。日志（合并排序（arr））

插入排序：star:

顾名思义：通过构造有序序列，对于未排序的数据，在已排序的序列中从后向前扫描，找到对应的位置并插入。

「时间复杂度： O(n^2)」

思路

从第一个元素开始，可以认为该元素已排序；

取出下一个元素，在排序后的元素序列中从后向前扫描；

如果该元素（已排序）大于新元素，则将该元素移动到下一个位置；

重复步骤3，直到找到已排序元素小于等于新元素的位置；

重复步骤2~5。

动画

代码实现

让插入排序=函数(arr) {

让len=arr.length

//双指针，当前和上一个

for (令i=0; i len; i++) {

令preIndex=i - 1，

当前=arr[i];

//第一个元素没有前一个元素，可以直接赋值

while (preIndex=0 arr[preIndex] cur) {

arr[preIndex + 1]=arr[preIndex]

前索引--;

}

arr[preIndex + 1]=cur

}

返回目的地

}

让arr=[2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]

安慰。日志（插入排序（arr））

选择排序：star:

思路：每次从要排序的数组元素中选择最大(最小)的一个元素作为首元素，直到排完该行

「时间复杂度O(n^2)」

思路

有n个数，需要排序n-1次

第一次选择最小值，放在前面

第二次选择最小值，放在第二位

.重复该过程

选择第n-1次的最小值，放在第n-1位

动画

代码实现

让selectSort=函数(arr) {

让len=arr。长度，

温度=0；

//总共len-1次需要排序

for (令i=0; i len - 1; i++) {

//设置替换目标，从数组中的第一个开始

温度=我；

for (让j=i + 1; j len; j++) {

if (arr[j] arr[temp])

温度=j；

}

//每次行程保证第i位为最小值

如果（温度！==我）{

[arr[i], arr[temp]]=[arr[temp], arr[i]]

}

}

返回目的地

}

让arr=[2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]

安慰。日志（选择排序（arr））

: hljs-中心

:

网址：《算法与数据结构》整理6大排序算法供offer！ http://www.mxgxt.com/news/view/1192339

相关内容

钉钉杯常用数据挖掘算法总结
一文弄懂数据挖掘的十大算法，数据挖掘算法原理讲解
【学习】十大数据挖掘算法及各自优势
大数据与数据挖掘技术 数据挖掘算法应用
数据挖掘算法有哪些
算法博士+人工智能+大数据=企业供应链智慧化决策？
从小白视角理解『数据挖掘十大算法』
关于数据挖掘的十种算法原理讲解
从小白视角理解<数据挖掘十大算法>
抖音与快手新圈层增长背后的数据和算法

随便看看