跳到主要内容

排序 (Sort)

排序的概述​

排序算法​

  • 常用的：

    • 冒泡排序

    • 插入排序

    • 选择排序

    • 归并排序

    • 快速排序

    • 计数排序

    • 基数排序

    • 桶排序

  • 不常用的：

    • 猴子排序
    • 睡眠排序
    • 面条排序

排序算法分类​

按照时间复杂度进行分类

  • 冒泡、插入、选择 ： O(n^2)
  • 快排、归并： O(nlogn)
  • 桶、计数、基数：O(n)

如何分析一个排序算法？​

学习排序算法，除了学习算法原理、代码实现之外，更重要的是要学会如何评价、分析一个排序算法

分析执行效率​

  1. 最好情况、最坏情况、平均情况时间复杂度
    • 对于要排序的数据，有的接近排序，有的完全无序，有序度不同的数据，对于排序的执行时间效率会差别很大
  2. 时间复杂度的系数、常数、低阶
    • 在数据规模很大的时候，通常会忽略系数、常数、低阶，但实际开发中，通常需要排序的数据量级是相对较小的，所以此时需要考虑系数、常数、低阶对排序的执行时间效率的影响。
  3. 比较次数和交换（或移动）次数
    • 基于比较的排序算法，通常会涉及两种操作，元素大小比较和元素交换移动，

分析内存消耗​

  1. 算法的内存消耗可以通过空间复杂度来衡量，在排序算法的空间复杂度中，引入了原地排序概念，对于原地排序算法，就是特指空间复杂度是O(1)的排序算法。
    • 冒泡、插入、选择都是原地排序算法。

分析稳定性​

  1. 稳定性是衡量排序算法好坏的重要指标。
    • 稳定的排序算法：经过排序后，相等元素之间的原有的先后顺序不变
    • 不稳定的排序算法：经过排序后，相等元素之间的位置发生改变

冒泡排序（Bubble Sort）分析​

  • 概念：

    • 冒泡排序只会操作相邻的两个数据。

    • 每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满就让他俩互换。

    • 一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序。

  • 特点：

    • 冒泡排序是原地排序算法.
      • 冒泡过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以空间复杂度是O(1)
    • 最好情况时间复杂度：O(n)
    • 最坏情况时间复杂度：O(n^2)
    • 平均时间复杂度：O(n^2)
      • 结合概率论知识进行分析
      • 引入有序度和逆序度进行分析

  • 有序度：

    • 有序度是数组中具有有序关系的元素对的个数。

      有序元素对：a[i] <= a[j], 如果 i < j。

    • 满有序度：完全有序的数组的有序度叫做满有序度

  • 逆序度：

    • 和有序度相反

      逆序元素对：a[i] > a[j], 如果 i < j。

  • 公式分析：

    • 逆序度 = 满有序度 - 有序度
    • 排序的过程其实就是一种增加有序度，减少逆序度的过程，最后达到 满有序度，就说明排序完成。
    • 冒泡排序包含两个操作原子，比较和交换，每交换一次，有序度加1，不管算法怎么改变，交换次数总是确定的，即为逆序度，也就是：n*(n-1)/2–初始有序度。

插入排序（Insertion Sort）分析​

0%