交换排序

交换排序

• 当排序算法基本有序时，每次选取第n个元素为基准，会导致区间分配不均匀，不利于发挥快速排序算法的优势

  • 相反，当待排序数据分布较为随机时，基准元素能将序列划分为两个长度大致相等的序列，这时才能发挥快速排序的优势

• 冒泡排序每趟都至少会有一个元素到达某端的最终位置

• 快速排序会将元素分为大于和小于枢轴元素的两个子序列

  • 若枢轴元素最终位置处于边界处，则一趟下来只会产生一个子序列
    • 再对子序列进行快排最多再产生两个子序列，
      • 此时两趟快排两个元素到达最终位置
  • 若枢轴元素最终位置不处于边界处，则一趟下来会产生两个子序列
    • 第二趟快排再分别对两个子序列进行快排，两个子序列每个又会分成两个子序列的子序列
      • 此时两趟快排会有至少三个元素到达最终位置，第一趟一个，第二趟在第一趟产生的两个子序列基础上分别产生一个

• 问最终位置的排序结果时，可以手动将序列的排序结果写下来，与题目进行比较，来进行最终位置是否合适的判断

• 快速排序的速度

  • 当每次的枢轴都把表分为长度相近的两个子表时，速度是最快的
  • 当表本身已经有序或逆序时，速度最慢

• 递归方式对顺序表的快速排序

  • 递归次数与各元素的初始排列有关
  • 若每次划分后分区比较平衡，则递归次数少
  • 若分区不平衡，递归次数多
  • 递归次数与处理顺序无关