分类 标签 存档 社区 博客 友链 GitHub 订阅 搜索

排序算法之比较排序

228 浏览

ZERO

    持续更新 请关注:https://zorkelvll.cn/blogs/zorkelvll/articles/2018/11/20/1542723005557

背景

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

一、概述

     排序算法是非常基础和重要的一类算法,本文主要是介绍比较排序算法的思想,主要涉及到冒泡排序、梳排序、堆排序、归并排序(递归版与非递归版)、快速排序(递归版与非递归版)、内省排序、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

评论  
留下你的脚步
推荐阅读