常见的排序算法解析 Domi●Cat

关于排序算法,从大学到工作,一直都在接触,奈何老是学了忘,忘了学。很是蛋疼,索性就把我自己看过的几个排序算法做个笔记,加深一下记忆。

比较常用的排序算法:

  • 冒泡排序 (面试常用 - -!)
  • 快速排序
  • 直接选择排序
  • 红黑树排序

冒泡排序

这个排序算法,是比较基础的算法,该算法的核心在我自己的理解是: 两两交换。 只要记住这个算法就是依次比较相邻的两个元素的大小。

假如要参与排序的元素个数为 n,那么需要排序的轮数为 n - 1。而在具体的每一轮 的排序中,只用排序上一轮剩下的。这里有一个可以优化的细节,在每一轮开始循环 比较大小的时候,给一个标示位,如果这一轮排序结束后,该标示位没有变化,说明 已经是有序的了,后面的轮数也可以跳过了。但是最坏的情况还是需要排玩 n -1 轮。

具体的实现我用go实现了一遍,很简单,代码在这里 升序和降序只需要改下比较大小的顺序就OK了,很容易实现。

快速排序

该算法的效率很高,所以敢称快速排序。它的思想是基于二分法。算法思想:从无序的 元素中选取一个基准元素,一般都选第一个元素,然后用这个基准与其他元素对比,大的 放一边(这一堆元素暂时是无序的,暂且称为大子队列),小的放另外一边(也是无序的,暂且称为小子队列), 然后再分别对这两个队列进行同样的对比操作,一直递归下去,直到子队列的元素小于1。 其实就是基准元素不断归为的过程。

balabala说了一堆,来个例子就明白了:

无序队列: list = {5,2,3,7,9,1}

直接选择排序

这个是比较“笨”的一种算法,就是拿元素一个个比下去。 如果是想升序,就拿每一轮第一个元素和后面的元素比较大小,在每一轮结束后,把找到的最小的元素 交换到该轮起始位置。一共轮 n - 1次。

代码在这里