排序算法(理论篇)

插入排序

• 直接插入：时间：O(n²)；空间：O(1)
  • 比较次数分析
    • 最好情况(全正序)：n-1次
    • 最坏情况(全逆序)：n(n-1)/2次
    • 一般情况分析举例：对于21,32,46,40的序列从小到大排序来说，32和46比前面的数都大，故只比较一次，40比46小(比较第一次)，比32大(比较第二次)，故40共比较2次
  • 特性：前n趟只保证前n个元素相对有序，最后一趟才能确定元素最终位置
  • 稳定性：稳定
  • 适用：顺序存储和链式存储的线性表
• 折半插入：时间：O(n log n)，O(n²)，对直接插入排序进行二分查找优化
• 希尔排序：时间：O(n²)；空间：O(1)
  • 特性：增量为n，2个元素一组，组内排序，然后缩小增量后重复该过程
  • 稳定性：不稳定
  • 适用：顺序存储的线性表

交换排序

• 冒泡排序：时间：O(n²)；空间：O(1)
  • 比较次数分析：取最后一个数开始，两两比较、交换
  • 特性：每趟可以确定一个数的最终位置
  • 稳定性：稳定
• 快速排序：时间：最好O(n log₂n) ,最坏O(n²),平均O(n log₂n)；空间：最好O(log₂n),最坏O(n),平均O(log₂n)
  • 比较次数分析
    • 最好情况：每次基准x都将序列分为等长的子表
    • 最坏情况：基本有序时
    • 一般情况：取x为基准，先从后向前扫描比x小的数并交换，再从前向后扫描比x大的数并交换，重复
  • 特性：第i趟排序有i个及以上的数放在最终位置（左边的数都比它小，右边的数都比它大）
  • 稳定性：不稳定
  • 是内部排序算法平均性能最优的排序算法

选择排序

• 简单选择排序：时间：O(n²)；空间：O(n log₂n)
  • 比较次数分析：与初始序列无关，恒定为n(n-1)/2 次
  • 特性：元素移动的操作次数较少，不超过 3(n-1) 次
  • 稳定性：不稳定
• 堆排序：时间：建堆的复杂度O(n)，调整的复杂度O(h)，本质上是二叉树，h为树高=log₂n（向下取整）+1
  • 大根堆：L(i)>=L(2 *i) && L(i)>=L(2 *i+1)
  • 小根堆：L(i)<=L(2 *i) && L(i)<=L(2 *i+1)
  • 建堆：自下而上逐步交换位置不对的子结点和父结点
  • 弹出堆顶元素：将最后一个数换到堆顶，再向下交换调整
  • 稳定性：不稳定
  • 最后一个非叶子结点存在 n/2（向下取整）：所以小根堆的最大值 存在 n/2 + 1~n

其他排序

• 归并排序：时间：O(n log₂n)；空间：O(n)
  • merge() + 归并：共进行log₂n趟归并，归并时间复杂度O(n)
  • 比较次数分析：比较次数数量级与初始序列无关，最少比较次数N，最多比较次数2N-1
  • 稳定性：稳定
  • 将n个元素的排序表视为n个有序子表，两两归并成最终长度为n的有序表
• 基数排序：时间：O(d*(n+r))；空间：O(r)（r个队列）
  • MSD最高位优先：从高位到低位对每一位进行排序
  • LSD最低位优先：从低位到高位对每一位进行排序
  • 模拟过程：10个队列，分别为q[0],q[1],q[2]……q[9]
    • step 1：对个位排序，则在q[0 ~ 9]下分别建一个队列，分别放入所有个位为0~9的数字，得到第一趟排序结果
    • step 2：再对十位进行排序，……，得到第二趟排序结果
    • step 3：直到对最高位排序结束，得到最终的排序结果
  • 不基于比较和移动进行排序，而是基于关键字各位的大小进行排序