算法学习笔记：排序算法(一)

renweihub 发布于2019-08-23 14:25 / 3500人阅读

摘要：如果有错误或不严谨的地方，欢迎批评指正，如果喜欢，欢迎点赞收藏

算法对大多数前端工程师来说都是一个比较不愿意提及的话题，因为学了，感觉在工作中直接应用的场景不多，不学，大厂面试必考算法，总结来说就是：没有学习算法的源动力，为面试学习算法总不会令人动力去学习，没有动力想要学好算法自然也很难，对我来说，学习算法的动力就是希望写出更高效率的代码，更好的理解各种前端框架的设计思路，因此，后面会写几篇有关算法的学习笔记，下面进入这篇文章正题：排序算法

冒泡排序

排序算法中最简单最基础的就是冒泡排序，这种排序的思想就是相邻两个元素进行两两比较，大的放后面，每一轮选出最大的元素，让我们来看具体代码：

function bubbleSort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    for (var j = 0; j < arr.length - i - 1; j++) {
      var temp;
      if (arr[j] > arr[j + 1]) { // 相邻两个元素比较，大的往后移动
        temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp
      }
    }
  }
  console.log(arr)
}
bubbleSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])

为了更好的看到排序的过程，让我们来看下面动态图片：

冒泡排序，在数组本身就是有序的情况下(最好情况)，需要需要n-1次比较能完成，但是在最坏的情况下需要比较和交换n-1+n-2+n-3+...+1=n(n-1)/2次，其算法复杂度为O(n^2)

选择排序

选择排序是最直观简单的一种排序算法，具体实现思路就是：把第一个元素假定为最小元素，遍历后面没有排序的元素，如果发现比当最小元素小的值，就记下数组下标，循环执行，当一轮循环结束，将最小下标对应的值和当前元素调换位置，来看具体代码实现：

function selectionSort(arr) {
  var index,temp // index:最小值下标索引，temp:临时变量
  for (var i = 0; i < arr.length; i++) {
    index = i
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[index]) {
        index = j
      }
    }
    temp = arr[i]
    arr[i] = arr[index]
    arr[index] = temp
  }
  console.log(arr)
}
selectionSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])

为了更直观的展示排序的过程，让我们来看动态图片展示：

对于选择排序来说，比较次数是固定的，而交换次数则和数组的是否有序有关，但数组是正序时，不需要交换，当数组是倒序时，需要交换n-1次，它的时间复杂度是O(n^2)

插入排序

插入排序的实现思路和选择排序的实现思路有点类似，先将第一个元素设为已排序，然后遍历剩余的元素，如果已排序的元素大于当前的提取元素，已排序的元素向右移动一位，否则就将当前提取的元素插入，来看具体的代码实现：

function insetSort(arr) {
  for (var i = 0; i < arr.length; i++) {
    var temp = arr[i] // 提取出来的元素
    var j = i - 1
    while (arr[j] > temp) { // 比较已排序元素和当前提取出来的元素
      arr[j+1] = arr[j]
      j--
    }
    arr[j+1] = temp
  }
  console.log(arr)
}
insetSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])

插入排序在最好的情况下，也就是数组正序排列的时候，只要执行n-1次比较和0次交换时间复杂度为O(n)，当为倒序时，需要n^2/2次比较和n^2/2次交换，其时间复杂依然为O(n^2)

总结

这篇文章主要介绍了几个最简单的排序算法，后面的文章会继续介绍排序算法相关的内容。
如果有错误或不严谨的地方，欢迎批评指正，如果喜欢，欢迎点赞收藏

GPU云服务器云服务器学习排序算法排序算法图解排序算法总结桶排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/100577.html

算法学习笔记一、时空复杂度

摘要：动态规划背包士兵路径复杂度谈算法一定要考虑复杂度时间复杂度和空间复杂度时间复杂度计算机基本操作的次数汇编指令的条数寻址跳转空间复杂度所需占用的内存字节数两者区别空间是可以返回利用的。面试求职班一笔记算法主要研究：时空复杂度算法的特征：有穷性，确定性，可行性，可能没有输入，但一定有输出常用算法穷举法（eg：求N个数的全排列；8皇后问题）减而治之（二分查找...

wuyumin 2019-08-16 11:08 评论0 收藏0
JavaScript学习笔记 - 基础排序算法

摘要：本文记录了我在学习前端上的笔记，方便以后的复习和巩固。冒泡排序算法步骤比较相邻的元素。这步做完后，最后的元素会是最大的数。重复第二步，直到所有元素均排序完毕。得到序列第二趟，，和进行交换。本文记录了我在学习前端上的笔记，方便以后的复习和巩固。推荐大家去看看这一本gitBook上的书十大经典排序算法本文就是看这本书记录的笔记。冒泡排序 1.算法步骤 1.比较相邻的元素。如果第一个比第...

mindwind 2019-08-20 15:33 评论0 收藏0
javaScript排序算法学习笔记

摘要：排序算法学习笔记用于创建数组冒泡排序冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们。归并排序归并排序是一种分治算法。完成下列操作的前提是数组均已经完成。 javaScript排序算法学习笔记 // 用于创建数组 function createNonSortedArray(size) { var array = new ArrayList(); for( ...

lentoo 2019-08-26 13:35 评论0 收藏0
算法学习笔记：排序算法(二)

摘要：上一篇中已经介绍了几个简单的排序算法，这一篇文章我将继续向大家介绍排序算法相关的内容，本篇的会介绍希尔排序快速排序归并排序以及分治算法的思想，希望通过本文章能够加深大家对排序算法的理解。上一篇中已经介绍了几个简单的排序算法，这一篇文章我将继续向大家介绍排序算法相关的内容，本篇的会介绍希尔排序、快速排序、归并排序以及分治算法的思想，希望通过本文章能够加深大家对排序算法的理解。希尔排序...

William_Sang 2019-08-23 14:40 评论0 收藏0
优秀程序员都应该学习的 GitHub 上开源的数据结构与算法项目

摘要：强烈推荐上值得前端学习的数据结构与算法项目，包含图的演示过程与视频讲解。该仓库包含了多种基于的算法与数据结构，提供进一步阅读的解释和链接。数据结构和算法必知必会的个代码实现。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言算法为王。想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手；只有内功深厚者，前端之路才会走得...

cheukyin 2019-08-26 10:17 评论0 收藏0