数据结构 排序

数据结构第八章排序，展示了几种不同的排序算法，包括插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序和基数排序。每种排序算法的时间复杂度、空间复杂度、稳定性以及适用场景都有所不同。

排序

• 直接插入排序
  • 将一个待排序记录按关键字大小插入前面已经排好的子序列。
  • 空间复杂度O（1） 时间复杂度O（n2） 稳定的排序算法 适用于顺序存储和链式存储的线性表
• 折半插入排序
  • 折半查找找到应该插入的位置后进行插入。
  • 空间复杂度O（1） 时间复杂度O（n2） 稳定的排序算法 适用于顺序存储的线性表
• 希尔排序
  • 设置增量d，相隔d的记录组成子表进行直接插入排序。
  • 空间复杂度O（1） 时间复杂度O（n2） 不稳定的排序算法 适用于顺序存储的线性表（涉及随机存取
• 8.2插入排序
• 冒泡排序
  • 从后往前两两比较，若为逆序则交换。关键字最小的元素交换到待排序序列第一个位置。
  • 空间复杂度O（1） 时间复杂度O（n2）：逆序时进行n-1趟排序，第i趟要进行n-i次关键字比较，每次比较都必须移动元素3次交换元素位置。比较次数：n（n-1）/2，移动次数3n（n-1）/2。
• 快速排序
  • 在待排序列任取元素作为枢轴，右边的大于等于枢轴，左边的小于枢轴。将待排序列分为独立部分。重复上述过程。
  • 空间复杂度O（log2n）：最少的递归层数log2向下取整+1，最多n 时间复杂度O（n2） 不稳定的排序算法 适用于顺序存储的线性表
• 8.3交换排序
• 简单选择排序
  • 每一趟在待排序元素中选取关键字最小（最大）的元素加入有序序列；无论初始状态，一定需要n-1趟处理
  • 空间复杂度O（1） 时间复杂度O（n2）：移动次数不超过3（n-1）次，比较次数（n-1）+…+1=n（n-1）/2 不稳定的排序算法 适用于顺序存储和链式存储的线性表，和关键字较少的情况
• 堆排序
  • 初试堆堆顶元素最大，输出堆顶后堆底送入堆顶，再下坠调整保持大顶堆性质，再输出堆顶，如此反复
    • 如何建堆：检查非终端终端结点（i<=向下取整n/2），不满足则将当前结点与更大的孩子互换
    • 删除和调整：将堆的最后一个元素与堆顶交换，后调整
  • 空间复杂度O（1） 时间复杂度O（nlog2n）：建堆O（n），n-1次调整，每次调整O（h） 不稳定的排序算法 适用于顺序存储的线性表
• 8.4选择排序
• 归并排序
  • 把两个或多个有序序列合并成一个；m路归并，每选出一个元素需要对比m-1次
  • 空间复杂度O（n）：辅助空间为n个单元 时间复杂度O（nlog2n）：每趟归并为O（n），共归并向上取整log2n趟 稳定的排序算法 适用于顺序存储和链式存储的线性表
• 基数排序
  • 借助多个关键词排序
    • 最高位优先：关键字权重递减依次划分成若干更小的子序列
    • 最低位优先：关键字权重递增依次划分成若干更小的子序列
  • 空间复杂度O（r）：需要r个辅助队列 时间复杂度O（d（n+r））：d趟收集和分配工作，一趟遍历所有关键字O（n），一趟收集个队列O（r） 稳定的排序算法 适用于顺序存储和链式存储的线性表
• 8.5归并排序、基数排序和计数排序