当前位置： 首页 > Scala, 程序代码, 算法 > 正文

排序算法总结拾遗

Aug182020
作者：边城网事   发布：2020-08-18 17:39   分类：Scala, 程序代码, 算法   阅读：1,750   抢沙发  
目 录
 [ 隐藏 ]

排序算法总结拾遗

说到算法,脑子里最先想到的就是排序.
工作之后陆陆续续听说过,接触过的排序算法很多,真正掌握的的很少,有必要总结一下,便于查阅.
若无特别说明,本文提到的排序都是从小到大排序.

1. 桶排序/计数排序

考虑这样一个问题:
已知有一群人的身高数据都是整数,单位是cm. 现在需要将这组身高数据按照从小到大顺序排序.

一个解决办法:
假设我们将这群人请到了操场上了, 先找到这群人身高的最大值和最小值,分别用max和min表示.
然后在地上从min cm开始直到max cm,在地上每隔1cm做一个标记,共有 max – min + 1 个标记, 分别表示这个标记位置对应的身高.
然后让每个人根据自己的身高站到对应的标记上去,身高相同时,并排站着.

当所有人都站到对应的位置以后,他们其实已经按照身高排序的.
最后,从min标记开始,如果标记位置有人,就记录他们的身高,一直记录到max标记,所得到的身高数据,就是排好序的身高数据.

Scala代码实现:

package com.jack.yin.sorting

object BucketSort {
  def main(args: Array[String]): Unit = {
    val intArr: Array[Int] = Array(163, 175, 188, 174, 169, 176,175)
    sort(intArr)
    intArr.foreach(println)
  }

  private def sort(da'ta: Array[Int])= {
    val (min, max) = getArrayMinMax(data)
    val mark = Array.fill(max - min + 1)(0) // 地上的标记,从 min 到 max,每隔标记之间间隔1cm

    data.foreach(ele => {
      mark(ele - min )  = mark(ele - min) + 1
      // 每个人按照自己的身高站到指定的标记处,相同身高的人站成一排
    })

    var resultIdx = 0
    Range(0,max - min + 1).foreach(i => { // 从小到大遍历每一个标记
      if(mark(i) > 0) { // 标记处有人,则记录他们的身高,
        Range(0,mark(i)).foreach(_ => { // 标记处可能不止一个人(他们身高相同)
          data(resultIdx ) = min + i
          resultIdx += 1
        })
      }
    })

  }

  private def getArrayMinMax(data: Array[Int]): (Int, Int) = {
    var max = Int.MinValue
    var min = Int.MaxValue
    data.foreach(i => {
      if (i < min) min = i
      if (i > max) max = i
    })

    (min, max)
  }

}

优点:

  • 时间复杂度为O(n)

缺点:

  • 太浪费空间
  • 要排序的数一般只能是整数
  • 要计算最大值和最小值

类似的算法还有 基数排序

2. 冒泡排序

冒泡排序的思想是对于数组中的每一个元素,将该元素依次和其后面的元素比较,如果比后面的元素大,则交换.每一轮比较之后,最后一个元素都是最大的.
第一轮将一个元素归位,第二轮将倒数第二个元素归位,以此类推,知道所有元素都排序好.

package com.jack.yin.sorting

object BubbleSort {
  def main(args: Array[String]): Unit = {
    val intArr: Array[Int] = Array(163, 175, 188, 174, 169, 176,175)
    sort(intArr)
    intArr.foreach(println)
  }

  private def sort(data: Array[Int]) = {
    val arrLen = data.length
    // 与选择排序的区别: 冒泡排序两个循环下标都是从0开始的
    Range(0,arrLen - 1 - 1).foreach(i => { // 一共需要 arrLen - 1 轮处理,每轮处理之后,最后一个元素归位
      Range(0, arrLen - i - 1).foreach(j => { //每一轮处理需要比较的次数为 arrLen - i
        if(data(j) > data(j + 1) ) {
          val t = data(j)
          data(j) = data(j + 1)
          data(j + 1) = t
        }
      })
    })
  }
}

优点:

  • 逻辑简单,容易理解
  • 空间复杂度低,不占空间

缺点:

  • 时间复杂度为O(n2)

3. 选择排序

选择排序的思想是,遍历一遍数组种的前n – 1 个元素, 每次都将当前的元素和它后面的元素比较,将较小的数交换到前排.

package com.jack.yin.sorting

object SelectionSort {
  def main(args: Array[String]): Unit = {
    val intArr: Array[Int] = Array(163, 175, 188, 174, 169, 176, 175)
    sort(intArr)
    intArr.foreach(println)
  }

  private def sort(data: Array[Int]) = {
    val arrLen = data.length
    Range(0, arrLen - 1).foreach(i => {
      Range(i + 1, arrLen).foreach(j => { // 第二层循环是从 i + 1 开始,表示从当前处理元素的下一个开始比较,直到最后一个
        if (data(i) > data(j)) {
          val t = data(i)
          data(i) = data(j)
          data(j) = t
        }
      })
    })
  }
}

优点:

  • 逻辑简单,容易理解
  • 空间复杂度低,不占空间

缺点:

  • 时间复杂度为O(n2)

4. 快速排序

快速排序基本思想是,先取数组的第一个元素作为基准,将数组分成两个子数组:比基准大的和比基准小的.
然后再递归处理子数组,直到子数组无法再细分(仅包含一个元素).

动图演示

img

package com.jack.yin.sorting

object QuickSort {
  def main(args: Array[String]): Unit = {
    val intArr: Array[Int] = Array(163, 175, 188, 174, 169, 176,175)
    sort(intArr)
    intArr.foreach(println)
  }

  private def sort(data: Array[Int]):Unit = {
    quickSort(data,0,data.length - 1);
  }

  private def quickSort(data: Array[Int], start:Int, end:Int):Unit = {
    if(start >= end) {
      return
    }

    val base = data(start)
    var left = start
    var right = end

    while (left < right) {
      while(data(right) >= base && left < right) { // 从右向左,跳过比基准大的,找比基准小的,找到之后停止,保存位置到right
        right -= 1
      }
      while(data(left) <= base && left < right) { // 从左向右, 跳过比基准小的,找比基准大的,保存位置到left
        left += 1
      }
      // 此时,在左侧找到一个大的,右侧找到一个小的,需要将两者交换,保证较小的数在左侧,较大的在右侧
      if(left < right) {
        val t = data(left)
        data(left) = data(right)
        data(right) = t;
        //做完这个交换,上面连个while之一又可以继续执行,直到left和right相遇
      }
    }

    //此时 left = right, 左右两侧搜索相遇了,left和right所在的位置就是排序完成之后base所在的位置,因此需要将base和data(left)交换
    data(start) = data(left)
    data(left) = base

    //交换完成之后,以left/right 为分界点,生成两个待排序的子数组,继续用递归排序子数组
    quickSort(data, start, left - 1)
    // 特殊情况, 当第一个元素就是最小值时,此时left - 1 = -1, 不影响递归调用,因为在本函数开头有判断 start >= end 时,return了
    quickSort(data, left + 1, end)
    return
  }
}

优点:

  • 性能好,平均时间复杂度为O(NlogN)
  • 空间复杂度低

缺点:

  • 逻辑复杂,实现起来有些难度

5. 插入排序

插入排序 工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

动图演示

img

package com.jack.yin.sorting

object InsertionSort {
  def main(args: Array[String]): Unit = {
    val intArr: Array[Int] = Array(163, 175, 188, 174, 169, 176,175)
    sort(intArr)
    intArr.foreach(println)
  }

  private def sort(data: Array[Int]):Unit = {
    val len = data.length
    //从数组的第二个元素开始,假设该元素前面的部分是排序好的
    //初始状态从第二个元素开始, 其前面部分当成排好序的,因为只有一个元素看成是排序好的
    //对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
    Range(1,len).foreach( i => {
      var preIdx = i - 1;
      val current = data(i)
      //将当前待排序的元素之前的 已经排好序的元素(比当前元素大的) 往后移一位
      while (preIdx >= 0 &&  data(preIdx) > current) {
        data(preIdx + 1) = data(preIdx)
        preIdx -= 1
      }
      data(preIdx + 1) = current
    })
  }
}

优点:

  • 原理易于理解,排序过程跟打牌时,将新抓到的牌插入手上已排好序的牌中类似

缺点:

  • 时间复杂度为O(n2)

6. 希尔排序

希尔排序 是插入排序的优化. 插入排序,每次都需要比较移动元素,而且每次只能移动一个元素.最坏的情况,在做升序排序时,最小的元素出现在最后,那么将最小的元素移动到开头需要经过
繁琐的比较与移动. 在做插入排序时,加入要排序的元素中大部分都时排序好的,就比较省时间. 希尔排序已递减的间隔,取一些元素,然后对这些元素应用传统的插入算法,
因为,这些元素之间间隔比较大,在做插入排序时,可以交换间隔较大的元素,每一轮排序完成之后,所有元素的顺序逐渐趋于有序, 然后会缩小元素间隔,继续做插入排序.
直到最后间隔为1时,做一个完整的插入排序,因为此时大部分元素都已排序好,插入排序算法越来越快.

下图有希尔排序过程的图解.

shell

package com.jack.yin.sorting

object ShellSort {
  def main(args: Array[String]): Unit = {
    val intArr: Array[Int] = Array(163, 175, 188, 174, 169, 176,175)
    sort(intArr)
    intArr.foreach(println)
  }

  private def sort(data: Array[Int]) = {
    val len = data.length
    var gap = 1

    // 最优初始gap的选择据说是数学难题,图中使用 len/2为初始gap据说会有问题
    // 这里 换一种,保证最后一步gap能迭代成1即可
    while (gap < len) {
      gap = gap * 3 + 1
    }
    gap /= 3

    while (gap > 0) {
      /**从这里开始,如果gap=1,就是一个标准的插入排序 */
      Range(gap, len).foreach(i => {  //这里从gap开始,后面的每一个元素都要处理一下,并且后面的每一个元素都属于不同的分组
        val current = data(i)
        var preIdx = i - gap   // 所以这里preIdx 是 i - gap
        while (preIdx >= 0 && current < data(preIdx)) {
          data(preIdx + gap) = data(preIdx)  // 后面的等于前面的,相当于前面的元素移动到后面
          preIdx -= gap
        }
        data(preIdx + gap) = current

      })
      /**如果gap=1时,标准插入排序结束 */
      gap /= 3
    }

  }
}

优点:

  • 优化的插入排序算法,
  • 最好情况下,时间复杂度可达O(NlogN2)

缺点:

  • 不稳定
  • 由代码实现可知,实际上是做了若干轮(while(gap > 0))的插入排序
  • 最坏情况下,时间复杂度可达O(N2)

7. 归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略.
分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之.

原理图解, 图片来自这里
div

归并排序的工作原理如下：

将未排序的列表划分为n个子列表，每个子列表包含一个元素（一个元素的列表被认为是排序的）。
一般采用递归方式划分,初始化时,将数组从中间截断一分为二,得到两个子数组,然后再将子数组一分为二,直到每个子数组只包含一个元素.
然后,反复合并子列表以产生新的排序子列表，直到只剩一个子列表。合并子列表时将小的元素放左边,大的放右边,产生排序子列表.

算法图解

img

package com.jack.yin.sorting

object MergeSort {
  def main(args: Array[String]): Unit = {
    val intArr: Array[Int] = Array(163, 175, 188, 174, 169, 176,175)
    sort(intArr)
    intArr.foreach(println)
  }

  private def sort(data: Array[Int]): Unit = {
    val tmpResult = new Array[Int](data.length)
    sort(data,0,data.length - 1,tmpResult)
  }

  private def sort(data: Array[Int], start: Int, end: Int, tmpResult: Array[Int]): Unit = {
    if (start == end) {
      return
    }

    val len = end - start
    val mid = len / 2 + start

    sort(data, start, mid, tmpResult)
    sort(data, mid + 1, end, tmpResult)
    merge(data, start, mid, end,tmpResult)
  }

  //merge时, start - mid, mid + 1 - end 两个子数组已经排好序了
  private def merge(data: Array[Int], start:Int, mid:Int, end:Int, tmpResult: Array[Int]): Unit = {
    var i  = start
    var j = mid + 1
    var tmpIdx = 0

    while ( i <= mid && j <= end ) {
      if(data(i) < data(j)) {
        tmpResult(tmpIdx) = data(i)
        i += 1
      } else{
        tmpResult(tmpIdx) = data(j)
        j += 1
      }
      tmpIdx += 1
    }

    //防止出现特殊情况 比如 左侧 = 1,8,9 右侧 = 4,5,6 上面的循环结束后左侧还有
    while(i <= mid) {
      tmpResult(tmpIdx) = data(i)
      i += 1
      tmpIdx += 1
    }
    //同上,处理类似 左侧 = 4,5,6 右侧 7, 1, 2
    while(j <= end) {
      tmpResult(tmpIdx) = data(j)
      j += 1
      tmpIdx += 1
    }

    //将tmpResult中排序完成的元素覆盖源数组的data的下标为 (start - end) 部分
    i  = start
    tmpIdx = 0
    while (i <= end) {
      data(i) = tmpResult(tmpIdx)
      i += 1
      tmpIdx += 1
    }
  }
}

8. 堆排序

待续

参考

赞 赏

   微信赞赏  支付宝赞赏


本文固定链接: https://www.jack-yin.com/coding/3230.html | 边城网事

该日志由 边城网事 于2020年08月18日发表在 Scala, 程序代码, 算法 分类下， 你可以发表评论，并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 排序算法总结拾遗 | 边城网事
【上一篇】
【下一篇】

您可能还会对这些文章感兴趣！

排序算法总结拾遗 暂无评论

发表评论

快捷键：Ctrl+Enter