数据结构排序算法

数据结构常考排序算法，包括插入排序，希尔排序冒泡排序等几乎所有排序算法，排序是 重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程。

排序

• 排序的基本概念
  • 排序
    • 重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程
  • 算法的稳定性
    • 若排序算法中有两个元素Ri和Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，若排序后，Ri仍在Rj前面，在这个算法是稳定的。否则不稳定。
    • 稳定性不能衡量算法的优劣
• 插入排序
  • 直接插入排序
    • 将序列分为有序和无序两个部分，后面的无序部分每次在有序中查找到合适的位子插入
    • 原理
      • 待排序表 L [1···n] 在某次排序过程中的某一时刻状态
      • 1、查找出L(i) 在 L[1···i-1] 中的插入位置k
      • 2、将L[ k ··· i-1] 中所有元素全部后移一个位置
      • 3）将 L(i）复制到 L(k）
    • 性能
      • 空间复杂度O(1)
      • 最好时间复杂度O(n)
      • 最坏时间复杂度O(n^2)
      • 平均时间复杂度O(n^2)
      • 稳定
      • 适用
        • 顺序表、链表
  • 折半插入排序
    • 折半查找的直接插入排序
    • 元素比较次数
    • 性能
      • 空间复杂度O(1)
      • 最好时间复杂度
      • 最坏时间复杂度O(n^2)
      • 平均时间复杂度O(n^2)
      • 稳定
      • 适用
        • 顺序表
  • 希尔排序
    • 排序表分成若干个子表，每个子表进行直接插入排序，最后再进行一次整个的插入排序
    • 性能
      • 空间复杂度O(1)
      • 时间复杂度O(n^1.3)
        • 估算
      • 最坏时间复杂度O(n^2)
      • 不稳定
      • 适用
        • 顺序表
• 交换排序
  • 冒泡排序
    • 从头开始，对每个两两相邻的元素比较，大就往后排，比较完后最大的元素将在末尾。 重复上述过程，不比已经排出来最大的那个，一直重复得到顺序序列
    • 性能
      • 空间复杂度O(1)
      • 最好时间复杂度
        • 序列有序时，比较次数n-1，移动次数0，时间复杂度O(n)
      • 最坏时间复杂度O(n^2)
        • 序列逆序时
      • 平均时间复杂度O(n^2)
      • 稳定
      • 适用
        • 顺序表、链表
  • 快速排序
    • 1．先从数列中取出一个数作为基准数。 2．分区过程：将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。
    • 最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素. 长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n^2)
    • 性能
      • 空间
        • 最坏空间复杂度O(n)
        • 平均空间复杂度
      • 时间
        • 最好时间复杂度
        • 最坏时间复杂度
          • O(n^2)
        • 平均时间复杂度
      • 不稳定
      • 适用
        • 顺序表
• 选择排序
  • 简单选择排序
    • 每次选出最小的与位指定置交换
    • 比较次数 n(n-1)/2 时间复杂度O(n^2)
    • 性能
      • 空间复杂度O(1)
      • 最好时间复杂度O(n^2)
      • 最坏时间复杂度O(n^2)
      • 平均时间复杂度O(n^2)
      • 不稳定
      • 适用
        • 顺序表、链表
  • 堆排序
    • 堆
      • n个关键字序列 L[1 ... n] 称为堆，当且仅当该序列满足：
        • • 小根堆
        • • 大根堆
    • 排序
      • 先将待排序列构造为堆，选出堆中最大（或最小）元素即 堆顶元素输出 堆顶元素输出后，堆底元素送入堆顶，堆的性质被破坏，将堆顶元素向下调整使其再次成堆，反复输出堆顶元素
    • 建堆
      • 1、按序列顺序构造二叉树
        • • {5, 2, 6, 0, 3, 9, 1, 7, 4, 8}
      • 2、找到⌊n/2⌋处，以它为根结点的树进行调整
      • 3、找到之前结点的前一个结点，继续调整，一直重复 调整过程中要保证已经调整过的堆还是符合规则的
    • 插入
      • 将结点加入到最后一个结点，自底向上依次调整
    • 删除
      • 只能删除根结点
      • 将最后一个结点替换根结点，从上至下依次调整
• 归并排序
  • 二路归并排序
    • 待排序表含有n个记录，看成是n个有序的子表，每个子表长度为1， 然后两两归井 得到 ⌈n/2⌉ 个长度为2或1的有序表，再两两归井，如此重复，直到合并成一个长度为n的有序表 注意区分递归归并和非递归归并
    • 性能
      • 空间复杂度O(n)
      • 最好时间复杂度
      • 最坏时间复杂度
      • 平均时间复杂度
      • 稳定
      • 适用
        • 顺序表
• 基数排序
  • 基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位.