十大排序算法的复杂度、排序方式、稳定性

相关概念

• 1.算法复杂度
  • 时间复杂度：是指执行算法所需要的时间(计算工作量)。
    • 语句频度/时间频度：一个算法中的语句执行次数，记为T(n)。
  • 空间复杂度：是指执行这个算法所需要的内存空间。
• 2.排序方式
  • 根据是否需要借助额外的数组来辅助排序，分为：
    • In-place：不需要借助额外的数组，直接对待排序数组中的元素进行比较和交换。
    • Out-place：需要利用额外的数组来辅助排序。
  • 举例：冒泡排序，不需要借助额外数组，直接对待排序数组的相邻元素两两比较和交换，属于In-place。计数排序，需要一个额外的计数数组来辅助排序，属于Out-place。
• 3.稳定性
  • 稳定：等值元素的先后顺序，排序前后“不”发生改变，称这种排序算法是稳定的。
    • 包括：冒泡排序，直接插入排序，归并排序，计数排序，桶排序，基数排序。
  • 不稳定：等值元素的先后顺序，排序前后“可能”发生改变，称为不稳定的。
  • 包括：快速排序，希尔排序，简单选择排序，堆排序。

总结十大排序算法的复杂度、排序方式、稳定性

原理简述

• 1.冒泡排序
  1）比较相邻的元素，如果前一个比后一个大，就交换它们。
  2）对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这样一轮比较结束，最大的数被移动到了最后的位置。
  3）针对所有的元素重复以上的步骤，除了最后一个。
  4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

• 2.快速排序
  1）先从数列中取出一个数作为基准数。
  2）分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
  3）再对左右区间重复第二步，直到各区间只有一个数。
  更多参考「快速排序」，对挖坑填数进行总结:

  • 1．i=L; j=R; 将基准数挖出形成第一个坑a[i]。
  • 2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
  • 3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
  • 4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

• 3.直接插入排序
  1）先将数组arr分为左右两部分，左侧sorted_list=[arr[0]]，右侧unsorted_list=arr[1:]。
  2）依次遍历unsorted_list列表中的元素a：

  • 元素a与sorted_list中的元素b从后向前依次进行比较；
  • 满足条件a<b或a>b(根据排序顺序确定)时，b元素往后移动一格；
  • 直到最终不满足条件时，将元素a填入sorted_list中的索引空位。

• 4.希尔排序
  1）取序列长度的一半(向下取整)作为增量gap，对序列进行分组。
  2）然后对各组进行“直接插入排序”。
  3）增量gap依次减半(向下取整)，重复1）、2），最终一次的增量gap为1。

• 5.简单选择排序
  第一轮找最小的数并放到第一个位置。
  第二轮找第二小的数并放到第二个位置。
  依次迭代...

• 6.堆排序
  1）把无序数组构建成二叉堆(若从小到大排序，则构建成最大堆)。
  2）将堆顶元素与二叉堆末尾元素进行替换(此时，最后一个元素已经排序好了)。
  3）对剩余未排序的元素，循环重复1）、2）。

• 7.归并排序
  二路归并排序：将序列不断二分为多个子序列，对子序列从上到下依次进行排序合并。

• 8.计数排序
  定义一个计数数组，统计每个元素出现的次数。

• 9.桶排序
  先分桶，每个桶代表一个数值区间范围，将元素放入对应桶中。
  然后，对每个桶分别进行排序(可递归调用桶排序)。
  最后，合并所有的桶即可。

• 10.基数排序
  取数组中最大元素的位深(个、十、百...)。
  按个位分桶，然后取出。
  按十位分桶，然后取出。
  依次类推...