排序算法之比较排序

    本文主要是记录在学习《算法笔记》等书籍中的排序算法，排序算法按照是否基于“比较”操作可以分为比较排序和非比较排序两大类，这一篇文章主要是记录比较排序算法时的知识点和相关总结！

一、概述

    排序算法是非常基础和重要的一类算法，本文主要是介绍比较排序算法的思想，主要涉及到冒泡排序、梳排序、堆排序、归并排序（递归版与非递归版）、快速排序（递归版与非递归版）、内省排序、Timsort！

(1)基于比较的排序算法，也即根据待排序对象之间的大小关系进行排序的，比较规则必然是需要满足传递性和全序性！

    排序算法下界 O(nlog2(n))推导：

2^f(n) >= n!

=>

f(n) >= log2(n!) = nlog2(n)

(2)“合并多个有序列”问题

(3)“前 k 个小数”问题

二、冒泡排序与梳排序

1、冒泡排序

    冒泡排序是最最最基本的一个排序算法，如果连这个都手写不出来伪代码，那也还是不要做程序员了早点滚蛋算了！

    思想：调整相邻两个对象的位置，每进行一次内循环，就可以将最大值调整到最后！

因此，在经过 n-1 次内循环之后就可以得到整个完整的有序列！时间复杂度 O(n^2)

伪代码如下：

for i = 1,2,……,n-1 do
  for j = 1,2,……,n-i do
    if a(j) > a(j+1) then
      交换a(j) 和 a(j+1)
    end if
  end for
end for
​

2、梳排序

    梳排序是冒泡排序的一种改进，虽然没有很好的理论结果，但是实际效果非常好！

    思想：对固定距离处的对象进行比较和交换，即在冒泡排序之前做了一些排序工作！

固定距离是待排序列长度 n 除以 1.3 向下取整（若小于 1 则取 1）！时间复杂度 O(nlog1.3(n))

伪代码如下：

j <- n, s <- 1.3, flag <- false
while j > 1 或者 flag = true do
  i <- 0, j <- max{j/s,1}, flag <- false
  while i + j <= n do
    if a(i) > a(i+j) then
      交换a(j) 和 a(j+1)
      flag <- true
    end if
    i <- i+1
  end while
end while
​

三、堆排序

    堆排序，即借助堆这个数据结构来进行排序的！

    思想：对全部待排序对象建堆，然后反复查找并删除最小值（最大值）！

    应用：

（1）多个序列合并问题：n 个有序列，第 i 个序列长度为 m(i)

    将每个有序列中的第 1 个对象即最小值放入堆中，进行建堆 => 然后查找并删除最小值 => 若最小值来自第 j 个序列，则将第 j 序列中的下一个尚未处理的对象放入堆中 => 继续查找并删除最小值 => 直至全部比较完

    建堆时间复杂度 O(n)，每次查找并删除最小值的复杂度是 O(log(n))共需要次数 sum[m(i)]「i=1……n」，每次插入的复杂度是 O(log(n))共需要次数 sum[m(i)-1]「i=1……n」 => 总的时间复杂度是 O(sum[m(i)log(n)]「i=1……n」)

(2)查找前 k 个数问题：    将每个有序列中的第 1 个对象即最小值放入堆中，进行建堆 => 然后查找并删除最小值 => 若最小值来自第 j 个序列，则将第 j 序列中的下一个尚未处理的对象放入堆中 => 继续查找并删除最小值 => 直至第 k 个最小值即可

    建堆时间复杂度 O(n)，，每次查找并删除最小值的复杂度是 O(log(n))共需要次数 k => 总的时间复杂度是 O(n+klog(n))

四、归并排序

五、快速排序

六、内省排序

七、Timsort