Java教程

经典排序算法

本文主要是介绍经典排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

常见排序算法

在这里插入图片描述

  • 稳定性:如果a原本在b的前面,且a==b,经过排序后a仍然在b的前面。
  • 非稳定性:如果a原本在b的前面,且a==b,经过排序后a不在b的前面。
  • 原地排序:排序过程中不申请多余的存储空间,利用原来的存储空间进行交换和排序。
  • 非原地排序:需要额外的数组空间进行交换和排序。
  • 时间复杂度:执行算法所需要消耗的时间。
  • 空间复杂度:执行算法所需要消耗的空间。

关于时间复杂度

  • 平方阶(O(n2)):插入排序、选择排序和冒泡排序。
  • 线性阶(O(n)):基数排序和桶排序。
  • 线性对数阶(O(nlog n)):快速排序、堆排序和归并排序。

关于空间复杂度

  • 线性阶(O(n)):归并排序。
  • 线性对数阶(O(log n)):快速排序。
  • 线性+K阶(O(n+k)):桶排序、基数排序。
  • 常数阶(O(1)):冒泡排序、选择排序、插入排序、希尔排序和堆排序。

关于稳定性

  • 稳定排序:冒泡排序、插入排序、归并排序和基数排序。
  • 不稳定排序:选择排序、快速排序、希尔排序和堆排序。
    在这里插入图片描述

冒泡排序

重复地访问要排序的数列,一次比较两个元素,如果他们的顺序错误就交换过来。访问数列的工作是重复地进行直到没有在需要交换的元素,也就说明数列已经排序完成。

  • 比较相邻的元素,如果第一个比第二个大,则交换他们
  • 对每一对元素执行相同的操作,从开始第一对到结束最后一对,经过一轮后最后的元素是最大的。
  • 针对所有元素重复以上步骤,一直到最后一个。

选择排序

首先在未排序序列中找到最大(小)元素,存到排序序列的起始位置,然后在从剩余未排序元素中继续寻找最大(小)元素,然后放到已排序序列的末尾。

  • 初始状态:无序区R[1…n],有序区R[]
  • 第i趟排序,当有序区和无序区分别为R[1…i-1]和R[i…n]
  • 该趟排序从当前五序区中选出关键字最小的记录R[k]
  • 将它与无序区的第1个记录R交换,使R[1…i]和R[i+1…n]分别变为记录个数加1的新有序区和记录个数减少1的新无序区
  • n-1趟结束,数组有序化

表现最稳定的排序算法之一,无论数据规模大小时间复杂度都是o(n^2),所以数据规模越小越好

插入排序

通过构建有序序列,对于未排序的数据在已排序序列中从后向前扫描,找到相应位置插入。

  • 从第一个元素开始,该元素已经被认为有序
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描
  • 如果该元素大于新元素,将该元素移到下一个位置
  • 重复步骤3,直到找到已排序的元素小于或等于新的元素的位置
  • 将新元素插入到该位置后,重复以上步骤

希尔排序

1959年shell发明,第一个突破O(n2)的排序算法,简单插入排序的改进版。与插入排序不同的是,它会优先比较距离较远的元素,又称缩小增量排序。

  • 将整个排序序列分为若干个子序列分别执行直接插入排序
  • 选择一个增量序列t1、t2,… ,tk,ti > tj,tk=1,对增量序列按个数K,对序列进行K趟排序
  • 每趟排序根据对应的增量ti,对待排序序列分割成若干长度为m的子序列,分别对子表执行直接插入排序
  • 当增量仅为1时,整个序列作为一个表来处理,表的长度为整个序列的长度

算法的核心在于间隔序列的设定,既可以设定动态间隔,也可以设定默认间隔。

归并排序

归并排序是建立在归并操作上的一种排序,采用的是分治的思想。先使每个子序列有序,在使子序列段有序,然后将两个有序表合并。将已有序的子序列合并,得到完全有序的序列。

  • 把长度为n的输入序列分成两个长度为n/2的子序列
  • 对两个子序列分别执行归并排序,将两个子序列合并为有序序列

归并排序是稳定排序算法,和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,时间复杂度始终为O(nlog2)

快速排序

通过一趟排序将序列分为两部分,其中一部分的关键字比另一部分的关键字小,分别对两部分进行排序,达到有序。使用分治的方法把串分成两个字串

  • 从数列中挑出一个元素,称为基准,一般为首个元素
  • 重新排序数列所有比基准小的元素放在基准前面,所有比基准大的放在后面
  • 递归的把子序列按照步骤二执行,最终可得到一个有序的序列

堆排序

利用堆进行排序的一种算法,按照堆的子节点或索引总是大于或小于他的父节点的性质

  • 将初始序列(R1,R2,…,Rn)构建成大顶堆,堆的初始状态为无序
  • 将堆顶元素R[1]与最后一个元素R[n]进行交换,此时得到新的无序区(R1,R2,…,Rn-1)和有序区域Rn,且满足(R1,R2,…,Rn-1)<=Rn
  • 由于交换后的新堆顶可能违反堆的性质,因此需要对当前无序区(R1,R2,…,Rn-1)进行调整为新的堆
  • 然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)
  • 不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成

计数排序

将输入的数据值转换为键,存储在额外开辟的数组空间中,作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数,计数排序适用于小范围数

  • 找出待排序的数组中最大和最小的元素
  • 统计数组中每个值为i的元素出现的次数,存入数组c的第i项
  • 对所有的计数累加(从c中的第一个元素开始,每一项和前一项相加)
  • 反向填充目标数组,将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减1

计数排序是稳定排序,当输入的元素是n个0到k之间的整数时,时间复杂度为O(n+k),空间复杂度为O(n+k),速度比较快。当n不是很大时且数据比较集中时,计数排序是一个很有效的排序算法,。

桶排序

桶排序是计数排序的升级版,它利用了函数的映射关系,排序是否高效在于函数的映射关系。假设输入数据服从均匀分布,将数据分到有限个数量的桶里,然后在使用别的算法或者使用递归的方式对每个桶进行排序

  • 设定一个定量的数组当作是空桶
  • 遍历输入数据,把每个数据放入到对应的桶
  • 对每个不是空的桶进行排序,从不是空的桶里把有序的数据拼接起来

桶排序最好的情况下使用线性的时间复杂度O(n),桶排序的时间复杂度取决于每个桶之间数据排序的复杂度,因为其他的部分时间复杂度为O(n),显然,桶划分的越小,各个桶之间的数据越少,排序用的时间也越少。

基数排序

基数排序按照高低位先排序,然后收集,在按照高位排序,然后在收集,以此类推,直到最高位;有时间有些属性是有优先级顺序的,先按照低优先级,在按照高优先级排序,最后的次序是高优先级高的在前面,高优先级相同的低优先级高的在前面

  • 取得数组中的最大数,并取得位数,arr为原始数组,
  • 从最低位开始取每个位组成的radix数组,对radix进行计数排序

基数排序是基于分别排序、分别收集,所以是稳定的,但是基数排序的性能比桶排序要差,每一次关键字的桶分配都需要O(n)的时间复杂度

推荐

1、数据结构算法可视化网站-Visualgo.net

这篇关于经典排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!