数据结构笔记（排序）

• N是正整数
• 只讨论基于比较的排序
• 只讨论内部排序（所有数据可以被读取到内存）
• 稳定性：任意两个相等的数据，排序前后的相对位置不发生变化

简单排序

• 冒泡排序

• 插入排序

交换两个相邻元素刚好削去一个逆序对

插入排序：O(N,I) = O(N+I)

任意N个不同元素组成的序列，平均具有N(N-1)/4个逆序对

任意以交换两个元素排序的算法，平均时间复杂度为 平均时间复杂度

其他排序

希尔排序（Shell's Sort）

• 是插入排序的一种缩小增量排序

  原始希尔排序

  • DM = |N/2|，Dk = |Dk+1/2|

  其他增量序列

  • Hibbard增量序列 Dk = 2^k - 1
  • Sedgewick增量序列

选择排序

• 从未排序部分找出最小元素，与有序部分的最后元素进行交换

堆排序

• 先构造一个大顶堆，然后将根结点元素与最后一个子结点元素的值交换，然后堆元素减一，调整成最大堆，继续交换，直到最后只剩根结点，堆就变成逆序了

归并排序

• 核心：有序子列的归并
  • 方法一：递归算法：分而治之
    • 特点：稳定 O(Nlog(N))
  • 方法二：非递归算法
    • 先合并最小子列，然后再依次合并，需要额外空间，不适合内排序

快速排序

• 选主元，将元素分为左右两个部分，左边都小于主元，右边都大于主元
• 小规模数据不如简单排序快

表排序

• 间接排序
• 物理排序（O(N)）

基数排序（稳定）

是桶排序变体，适用于多关键字排序

• 次位优先（LSD）
• 建立N个桶，N是数的进制
• 从最低位开始依次把元素放进桶里，然后再到次低位，一直到主位