文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

6大排序算法

2024-12-24 15:24

关注

6种排序如下👇

冒泡排序
计数排序
快速排序
归并排序
插入排序
选择排序
时间复杂度如下图👇

 

排序算法复杂度分析
冒泡排序
以下动图GIF来自知乎 帅地

冒泡排序
这个名字的由来是向泡泡一样浮起来,脑补一下,就是每次比较相邻的两个元素大小,然后慢慢'漂浮'起来,看思路吧。

「时间复杂度O(n*n)」

思路
1 比较相邻的元素,前者比后者大的话,两者交换位置。
2 对每一对相邻元素做相同操作,从开始第一对到最后一对,这样子最后的元素就是最大元素。
3 针对n个元素重复以上步骤,每次循环排除当前最后一个。
4 重复步骤1~3,直到排序完成。

代码实现

  1. // 最外层循环控制的内容是循环次数 
  2. // 每一次比较的内容都是相邻两者之间的大小关系 
  3. let BubbleSort = function (arr, flag = 0) { 
  4.     let len = arr.length 
  5.  
  6.     for (let i = 0; i < len - 1; i++) { 
  7.         for (let j = 0; j < len - 1 - i; j++) { 
  8.             if (arr[j] > arr[j + 1]) { 
  9.                 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] 
  10.             } 
  11.         } 
  12.     } 
  13.     return flag ? arr.reverse() : arr 
  14.  
  15. let arr = [2, 9, 6, 7, 4, 3, 1, 7] 
  16. console.log(BubbleSort(arr, 1)) 

计数排序
从名称上就知道,它的思想:就是把数组元素作为数组的下标,然后用一个临时数组统计该元素出现的次数。

数组的数据必须是整数,而且最大最小值相差的值不要过大,对于「数据是负数的话,我实现的方案对此有优化」。

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

思路
1.计算出差值d,最小值小于0,加上本身add

创建统计数组并统计对应元素个数

统计数组做变形,后面的元素等于前面的元素之和,也就是排名数组

遍历原始数组,从统计数组中找到正确位置,输出到结果数组

动画

计数排序
代码实现

  1. // 计数排序 
  2. let countingSort = function(arr, flag = 0) { 
  3.     let min = arr[0], 
  4.         max = arr[0], 
  5.         len = arr.length; 
  6.     // 求最大最小值 
  7.     for(let i = 0; i < len; i++) { 
  8.         max = Math.max(arr[i], max
  9.         min = Math.min(arr[i], min
  10.     } 
  11.     // 1.计算出差值d,最小值小于0,加上本身add 
  12.  
  13.     let d =  max - min
  14.         add = min < 0 ? -min : 0; 
  15.     //2.创建统计数组并统计对应元素个数     
  16.     let countArray  = new Array(d+1+add).fill(0) 
  17.     for(let i = 0; i < len; i++){ 
  18.         let demp = arr[i]- min + add 
  19.         countArray[ demp ] += 1  
  20.     } 
  21.      
  22.     //3.统计数组做变形,后面的元素等于前面的元素之和,也就是排名数组 
  23.     let sum = 0; 
  24.  
  25.     // 这里需要遍历的是countArray数组长度 
  26.     for(let i = 0; i < d+1+add; i++){ 
  27.         sum += countArray[i] 
  28.         countArray[i] = sum
  29.     } 
  30.     let res = new Array(len) 
  31.     //4.遍历原始数组,从统计数组中找到正确位置,输出到结果数组 
  32.     for(let i = 0; i < len; i++){ 
  33.         let demp = arr[i] -min + add 
  34.         res[ countArray[demp] -1 ] = arr[i] 
  35.         countArray[demp] --; 
  36.     } 
  37.     return flag ? res.reverse() : res 
  38.  
  39. let arr = [2, 9, 6, 7, 4, 3, 1, 7,0,-1,-2] 
  40. console.log(countingSort(arr)) 

快速排序
基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

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

思路
选择数组中间数作为基数,并从数组中取出此基数
准备两个数组容器,遍历数组,逐个与基数比对,较小的放左边容器,较大的放右边容器;
递归处理两个容器的元素,并将处理后的数据与基数按大小合并成一个数组,返回。
动画

快速排序

  1. let quickSort = function (arr) { 
  2.     // 递归出口就是数组长度为1 
  3.     if (arr.length <= 1) return arr 
  4.     //获取中间值的索引,使用Math.floor向下取整; 
  5.     let index = Math.floor(arr.length / 2) 
  6.     // 使用splice截取中间值,第一个参数为截取的索引,第二个参数为截取的长度; 
  7.     // 如果此处使用pivot=arr[index]; 那么将会出现无限递归的错误; 
  8.     // splice影响原数组 
  9.     let pivot = arr.splice(index, 1)[0], 
  10.         left = [], 
  11.         right = []; 
  12.     console.log(pivot) 
  13.     console.log(arr) 
  14.     for (let i = 0; i < arr.length; i++) { 
  15.         if (pivot > arr[i]) { 
  16.             left.push(arr[i]) 
  17.         } else { 
  18.             right.push(arr[i]) 
  19.         } 
  20.     } 
  21.     return quickSort(left).concat([pivot], quickSort(right)); 
  22.  
  23. //let arr = [2, 9, 6, 7, 4, 3, 1, 7] 
  24. // console.log(quickSort(arr)) 

归并排序

将两个有序数列合并成一个有序数列,我们称之为“归并”

基本思想与过程:先递归的分解数列,再合并数列(分治思想的典型应用)

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

思路
将一个数组拆成A、B两个小组,两个小组继续拆,直到每个小组只有一个元素为止。
按照拆分过程逐步合并小组,由于各小组初始只有一个元素,可以看做小组内部是有序的,合并小组可以被看做是合并两个有序数组的过程。
对左右两个小数列重复第二步,直至各区间只有1个数。
动画

归并排序
代码实现

  1. const merge = (leftright) => { // 合并数组 
  2.  
  3.     let result = [] 
  4.     // 使用shift()方法偷个懒,删除第一个元素,并且返回该值 
  5.     while (left.length && right.length) { 
  6.         if (left[0] <= right[0]) { 
  7.             result.push(left.shift()) 
  8.         } else { 
  9.             result.push(right.shift()) 
  10.         } 
  11.     } 
  12.     while (left.length) { 
  13.         result.push(left.shift()) 
  14.     } 
  15.  
  16.     while (right.length) { 
  17.         result.push(right.shift()) 
  18.     } 
  19.     return result 
  20.  
  21. let mergeSort = function (arr) { 
  22.     if (arr.length <= 1) 
  23.         return arr 
  24.     let mid = Math.floor(arr.length / 2) 
  25.     // 拆分数组 
  26.     let left = arr.slice(0, mid), 
  27.         right = arr.slice(mid); 
  28.     let mergeLeftArray = mergeSort(left), 
  29.         mergeRightArray = mergeSort(right
  30.     return merge(mergeLeftArray, mergeRightArray) 
  31.  
  32. let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2] 
  33. console.log(mergeSort(arr)) 

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

「时间复杂度: O(n*n)」

思路
从第一个元素开始,该元素可以认为已经被排序;
取出下一个元素,在已经排序的元素序列中从后向前扫描;
如果该元素(已排序)大于新元素,将该元素移到下一位置;
重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
重复步骤2~5。

代码实现

  1. let insertionSort = function (arr) { 
  2.     let len = arr.length 
  3.  
  4.     for (let i = 0; i < len; i++) { 
  5.         let preIndex = i - 1, 
  6.             cur = arr[i]; 
  7.         while (preIndex >= 0 && arr[preIndex] > cur) { 
  8.             arr[preIndex + 1] = arr[preIndex] 
  9.             preIndex--; 
  10.         } 
  11.         arr[preIndex + 1] = cur 
  12.     } 
  13.     return arr 
  14.  
  15.  
  16. let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2] 
  17. console.log(insertionSort(arr)) 

选择排序
思路:每一次从待排序的数组元素中选择最大(最小)的一个元素作为首元素,直到排完为止

「时间复杂度O(n*n)」

思路
1.有n个数,需要排序n-1次
2.第一次选择最小值,放在第一位
3.第二次选择最小值,放在第二位
4.…..重复该过程
5.第n-1次选择最小值,放在第n-1位
代码实现

  1. let selectSort = function (arr, flag = 0) { 
  2.     let len = arr.length, 
  3.         temp = 0; 
  4.  
  5.     // 一共需要排序len-1次 
  6.     for (let i = 0; i < len - 1; i++) { 
  7.         temp = i; 
  8.         for (let j = i + 1; j < len; j++) { 
  9.             if (arr[j] < arr[temp]) 
  10.                 temp = j; 
  11.         } 
  12.         // 每一趟保证第i位为最小值 
  13.         if (temp !== i) { 
  14.             [arr[i], arr[temp]] = [arr[temp], arr[i]] 
  15.         } 
  16.     } 
  17.  
  18.     return flag ? arr.reverse() : arr 
  19.  
  20.  
  21.  
  22. let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2] 
  23. console.log(selectSort(arr, 1)) 

 

 

来源:前端UpUp内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯