算法学习--10大排序归纳总结

文章目录[x]
  1. 1:比较排序
  2. 2:非比较的排序

10种排序算法也是必须要掌握的知识,这里小生仅做学习总结归纳一下。

  • 在此之前我先推荐一个网站,可以用于动态观察各种排序的过程

数据结构可视化:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

  • 时间关系,这里我只是总结,具体的代码实现我会总结在CSDN博客上。

  • 时间复杂度
排序方法 时间复杂度(平均)
冒泡排序 O(n的平方)
选择排序 O(n的平方)
插入排序 O(n的平方)
希尔排序 O(n的1.3次方)
快速排序 O(n*long2n)
归并排序 O(n*long2n)
堆排序 O(n*long2n)
计数排序 O(n+k)   K=n*(logN/M)
桶排序 O(n+k)
基数排序 KN      k是最大值的位数

比较排序

  • 基础排序

冒泡:效率太低-->掌握SWap(两个数交换)。

插排:虽然平均效率低,但是在序列基本有序时,它很快,所以也有其适用范围Arrays这个工具类在1.7里面做了较大改动(就是有的情况下会自己调用插排)。

希尔:是插入排序的改良,倾向于空间思维。

选择排序:效率较低,但经常用它内部的循环方式来找最大值和最小值。

  • 分治法

分治法就是将一个大问题划分成若干小问题,然后递归解决,最后将结果合并。大致分为3步:

  1. 子问题拆分
  2. 递归求解子问题
  3. 合并子问题的解

快排(重视子问题的拆分):效率较低,但经常用它内部的循环方式来找最大值和最小值快排是软件工业中最常见的常规排序法,其双向指针扫描和分区算法是核心,往往用于解决类似问题,特别地 partition--selectK(选择特定的主元)算法用来划分不同性质的元素,也用于著名的topk问题。

归并排序:空间换时间(以牺牲空间提升效率,开辟了辅助空间),它重视合并,如求逆序数对。

堆排序:用到了二叉堆的数据结构(大顶堆,小顶堆)

非比较的排序

计数排序:可以说是最快的:0(N+k),k=max0f( sourceArr),用它来解决问题时必须注意如果序列中的值分布非常广(最大值很大,元素分布很稀疏),空间将会浪费很多。

桶排序:分桶,再用其他排序方法对桶內元素排序,按桶的编号依次检岀。用它解决问题必须注意序列的值是否均匀地分布在桶中如果不均匀,那么个别桶中的元素会远多于其他桶,桶内排序用比较排序,极端情况下,全部还是会退化成NgN其时间复杂度是:时间复杂度:0(N+C),其中C=N(LogN-LogM),约等于N*lgN。

基数排序:KN级别是数值型排序里面又快又稳的。开辟固定的辅助空间。

 

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00