现在的位置: 首页 > 自动控制 > 工业·编程 > 正文

排序算法汇总

2019-10-03 07:23 工业·编程 ⁄ 共 1782字 ⁄ 字号 暂无评论

冒泡:

第i个元素与第 i+1个元素俩俩相比然后互换位置,第一次循环会把最大的元素挪到最后,第二次是把第二大的元素挪到倒数第二。。。。。每次都会把最大的元素不断往后冒,与选择排序刚好相反。复杂度:n^2

选择:

用第i个元素比较后面的所有元素,从前往后比较,一直找到最小的一个挪到最左边,其实就是替换i的位置,与冒泡排序相反,第一次能找到最小的元素,第二次能找到第二小的元素。。。。复杂度:n^2

插入:

从前往后,把每个数往前面合适的地方插入。复杂度:n^2

归并:

把待排序队列分为n个有序的子队列,再合并他们,其实也是分治法思想的一种使用。复杂度:n*logn

快速:

冒泡排序的进化版,第一个数据把做全量对比,把比这个数小的放到它左边,大的放到右边,然后分别对左右两部分再进行快排,递归计算完成排序。也是分治法的使用,与归并某种意义上相反:归并是不断分成两份然后合并,快排是不断分成两个部分排序,快排一般会比归并快3倍,并且可以通过随机化快速排序规避最差情况(n^2),保证nlgn复杂度。复杂度:n^2,但是平均情况很快,达到nlgn

树型选择排序:

是一种按锦标赛的思想进行排序的方法。
基本思想与体育比赛时的淘汰赛类似。首先将n个对象的排序码进行两两比较,得到n/2个比较的优胜者,作为第一步比较的结果保留下来;然后对这n/2个对象再进行排序码的两两比较,…,如此重复,知道选出一个排序码最小的对象为止。类似于一颗二叉树,只需要把每次比较出的最小值的结点重新设置为∞,再比较出新一轮的最小值出来。复杂度:n*logn

堆排序:

对树形排序的进一步改进,使用一个大根堆(或者小跟堆)进行排序。堆排序的两个问题:
1.如何由一个无序序列“建初堆”。
2.输出堆顶后,如何“筛选”。筛选指对一颗子树均为堆的完全二叉树,调整根节点,使整个二叉树也成为一个堆。循环输出堆顶。

统计排序:

适用于知道数据范围的整数排序,预先分配好固定范围数组,统计每一个数组中数值在待排数组中出现的频率,统计结束后也就知道了每一个数在“排序后”数组中的位置,知道待排数组都是10以内的正整数,如:1,2,2,3,2,4,7,7,1。我们用一个长度为10的数组统计这个数组,得到{0,2,5,6,7,7,7,9,9,9}分别对应0~9这个数字知道1在数组中出现2次,则1在“排序后数组”中应该出现在(0,1)这两个索引位置,2在数组中也出现3次,所以2应该在(2,3,4)这三个索引上,刚好对应上面统计数组中的index=1,2的值减一。复杂度:n

多关键字排序:

以扑克牌排序为例,每张扑克牌有两个关键字:花色和面值。可以先按花色排序,之后再按面值排序;也可以先按面值排序,之后再按花色排序。

基数排序:

类似于一堆0~999的数据,先按个位排序,再按十位排序,再按百位排序,得到的结果就是最终的排序结果。一般每个位的排序选择统计排序复杂度:n

以上排序思想可以做一个大概的分类,如下:

插入类排序:将无序子序列中的一个或几个记录插入到有序序列中,从而增加记录的有序子序列的长度。例:插入排序。
交换类排序:通过“交换”无序序列中的记录,从而得到其中关键字最小或最大的记录,并将它加入有序子序列中。例:冒泡排序、快速排序。
选择类排序:从记录的无序子序列中,“选择”关键字最小或最大的记录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度。例:简单选择排序,树型选择排序,堆排序。
归并类排序:将两个或两个以上的有序数据序列,合并成一个有序数据序列的过程。例:归并排序。
分配类排序:主要利用分配和收集两种基本操作,典型的就是基数排序和多关键字排序。

再介绍两个排序的相关概念:

比较排序:只允许比较操作,以上的排序都是比较排序。
决策树排序:通常会有n个元素需要排序,<a1,a2...an>,对于每一个内节点(非叶子节点),都会有一个下标i:j,i和j分别在1~n之间,这个节点表示我们要比较ai和aj,每个内节点下会分出两颗子树,左边的子树说明ai<aj的情况下,算法要做什么,后续会进行哪些比较,考虑到会有等于的情况,我们让左边子树代表ai<=aj的情况,右边子树对应大于的情况,而每一个叶节点代表一个排序,若某个排序是正解,这这个排序更好地表达了数的特定排序。比较排序都可以转换成决策树模型,决策树是排序的一种图形表示。

给我留言

留言无头像?