常用排序算法
本文地址: ()
avatar
作者: FeRookie 类型: 原创
更新时间:2022-06-26 阅读:331

目录:

前言

对于算法的理解可深可浅,深呢,可以打开链接去了解一下,浅呢,算法一直伴随着我们左右,从小学习数学,到大学的高数等,从易到难,从简单地1+1=2到复杂地排序、查找等,但是他们都有一个特点就是都会有一个结果,无论是简单的方式还是复杂的方式,它都是一种算法。但是现在人们定义的算法包含了时间复杂度和空间复杂度来比较算法的效率。作为前端的我,一接触到算法就感觉特别高深,所以在学习的同时,我就将他记录下来,所谓好记性不如烂笔头。但是学习算法最好是需要理解,写一篇博客,是为了看清自己的理解程度。今天先为大家介绍一下排序算法中一些常用的排序算法。

常用的排序算法

冒泡排序

两两比较相邻记录的关键词,如果反序则交换位置。因此冒泡排序的时间复杂度最好的情况是O(n),最坏的情况是O(n2) exp:给定一个数组,将其通过冒泡排序方式进行排序

<script>
    function sort(arr) {
      let j, i, temp, len = arr.length
      for (j = 0; j < len; j++) {
        for (i = 0; i < len; i++) {
          if (arr[i] > arr[i + 1]) {
            flag = arr[i]
            arr[i] = arr[i + 1]
            arr[i + 1] = flag
          }
        }
      }
      return arr
    }
    var arr = [6, 3, 2, 5, 8]
    console.log(sort(arr)) // [2, 3, 5, 6, 8]
  </script>

上面的列子是一个简单的冒泡排序列子,还可以优化,比如加一个标志flag在排序两两比较的时候,如果序列是正序 则不用在进行比较了,可以直接退出 flag设为false等等,这样可以减少性能消耗,但是冒泡排序在众多排序中算是比较复杂的了。

冒泡排序性能分析

  • 时间复杂度: 正序的时间复杂度是O(n)也是最好的情况,倒序的时间复杂度是O(n2)是最坏的情况。
  • 空间复杂度 冒泡排序排序过程中需要一个临时变量进行两两交换,所需要的额外空间为1,因此空间复杂度为O(1)。
  • 稳定性 冒泡排序在排序过程中,元素两两交换时,相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

直接插入排序

将一个记录插入到已经排好序的有序表中,从而得到一个新的有序表。 详细描述: 插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间排序),因此在排序过程中,需要反复把已经排好序的元素逐步往后移动,直到将最新的一个元素插入进去。 具体步骤:

  1. 从第一个元素开始,默认第一个元素是已排好序状态
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,则将其向下一个位置移动
  4. 不断重复,直到找到已排序的元素小于新元素的位置,并将其插入到该位置
  5. 重复以上(2-4)步骤 exp: 给定一个数组,将其通过插入排序方式进行排序
    <script>
     function sorting(A) {
         for (var i = 1; i < A.length; i++) {
             var get = A[i]
             for (var j = i - 1; j >= 0 && A[j] > get; j--) {
                   A[j + 1] = A[j]
             }
             A[j + 1] = get
           }
     return A
     }
     console.log(sorting([5, 651, 8, 9, 6, 4])) // [4, 5, 6, 8, 9, 651]
    </script>
    目前都是采用 嵌套for循环进行排序,其实也可以通过while来进行循环,至于有什么意义呢,那就毫无意义吧。区别肯定是有的,细微的区别,也能做到极致的优化

    插入排序的性能分析

  • 时间复杂度: 正序的时间复杂度是O(n)也是最好的情况,倒序的时间复杂度是O(n2)是最坏的情况,但比冒泡排序性能更好一些
  • 空间复杂度 冒泡排序排序过程中需要一个临时变量进行两两交换,所需要的额外空间为1,因此空间复杂度为O(1)。
  • 稳定性 插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间排序),所以冒泡排序是一种稳定排序算法。

快速排序

快速排序,简称快排,是由东尼·霍尔发展的一种排序算法。采用的内部比较排序; 排序原理:从序列中选出一个元素作为基准数,根据基准数,先从右开始比较,找到比基准数小的元素,则停止查找;再从左开始比较,找到比基准数大的元素,则停止查找;最后将两个元素进行位置交换,这样就完成一次排序 exp: 给定一个数组arr=[6, 2, 3, 8, 5, 1, 9, 4, 5, 7],通过使用快排方式进行排序

function sorting(arr) {
    quickSort(arr, 0, arr.length - 1)
    return arr
}
console.log(sorting([6, 2, 3, 8, 5, 1, 9, 4, 5, 7])) // [1,2,3,4,5,6,7,8,9]
// 建立快排递归函数
function quickSort(arr, left, right) {
    // base 基准数
    var base, l, r, temp;
    base = arr[left]
    l = left
    r = right
    while(l != r) {
        // 查找右边, 如果大于基准数,则继续查找
        while(arr[r] >= base && l < r) r--
        // 查找右边, 如果小于基准数,则继续查找
        while(arr[l] <= base && l < r) l++
        // 将左右查找的元素进行交换位置
        if (l < r) {
            temp = arr[l]
            arr[l] = arr[r]
            arr[r] = temp
        }
    }
    // 将基准数归位
    temp = arr[l]
    arr[l] = base
    // l 当前基准数索引,递归执行左右分区
    quickSort(arr, left, l - 1)
    quickSort(arr, l + 1, right)
}

快速排序性能分析

  • 数据结构 数组
  • 时间复杂度 最优情况下为O(nlogn) 每次选择的基准都是中位数,这样每次都均匀的划分出两个分区,只需要logn次划分就能结束递归,最坏情况下为O(n2)每次选择的基准都是最大或者最小的数,导致每次只划分出了一个分区,需要进行n-1次划分才能结束递归。
  • 空间复杂度 主要是递归造成的栈空间的占用(用了保存left和right等局部变量),取决于递归树的深度,一般为O(logn),最差为O(n)。
  • 稳定性 快排采用分区进行排序,所以每次排序可能会有大幅度的变化,所以是不稳定排序

简单选择排序

希尔排序

归并排序

堆排序

计数排序

基数排序

桶排序

总结

致谢

(未完待续。。。)