十大排序算法

算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。

排序算法是《数据结构与算法》中最基本的算法之一,常见的共有十种:

 

1. 排序算法的分类

排序算法可以分为两大类:

  • 比较类排序
  • 通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。

     

  • 非比较类排序
  • 不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

     

 

2. 排序算法的复杂度

 

3. 排序算法的相关概念

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。
  • 不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。
  • 空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。

    • 冒泡排序(Bubble Sort):冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。冒泡排序的算法描述。比较相邻的元素。如果第一个比第二个大,就交换它们两个。