当前位置:   article > 正文

数据结构各排序算法【时间复杂度+空间复杂度+稳定性】比较_2、对这四种排序方法的时间复杂度、空间复杂度、稳定性做比较

2、对这四种排序方法的时间复杂度、空间复杂度、稳定性做比较

一、附加条件

        TJ1:比较次数与序列初态无关的算法

        TJ2:排序在一趟结束后不一定能选出一个元素放在其最终位置上

        TJ3:待排序数据已有序时,花费时间反而最多的是

        TJ4:就平均性能而言,目前最好的内排序方法

        TJ5:占用辅助空间最多的是

        TJ6:对初始状态为递增的表按递增顺序排序,最省时间的是

        TJ7:在最后一趟开始之前,所有元素可能都不在最终位置上

二、稳定性的口诀

情绪不稳定,快(快速排序)些(希尔排序)选(简单选择排序)一堆(堆排序)好友来聊天。

三、排序对比表格

类别排序方法时间复杂度空间复杂度稳定性条件备注
平均最好最坏辅助空间
插入排序直接插入O(n2)O(n)O(n2)O(1)稳定TJ6、TJ7 
希尔排序O(n3/2)O(n)O(n2)O(1)不稳定  
交换排序冒泡排序O(n2)O(n)O(n2)O(1)稳定  
快速排序O(nlog2n)O(nlog2n)O(n2)O(n)或O(logn)不稳定TJ3、TJ4

最坏情况栈为

单支树是为O(n)

选择排序简单选择O(n2)O(n2)O(n2)O(1)不稳定TJ1 
堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定  
归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定TJ1、TJ2、TJ5大数据处理 
基数排序O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd)稳定  
注:基数排序中,r代表关键字的基数,d代表长度,n代表关键字的个数。

01.冒泡排序
所谓冒泡排序就跟冒泡是个道理。想象一下水底的泡泡慢慢冒出水面的过程,跟这个算法其实就是一个思想,不断将底部的数据调整到目的顺序类似冒泡。图中是该序列第一趟冒泡的整个过程,当i=1时将1冒到了顶端。

显然以后的每一趟都是重复这样的规则,每一趟都找出了待排序序列中最小的数,并且能使得大的数往下沉,小的数往上冒。那么很容易想到,这样执行只需要执行到没有数再交换位置或者最后一个数,序列便排序完毕。
 

02.简单选择排序

举个例子,军训排序,从矮到高,教官这个时候开始找最矮同学放到排头,之后在剩下的队伍中找最矮的排到第二,依次类推。这便是简单选择排序的思想。

03.直接插入排序


插入排序顾名思义,即插入式排序。还是前面的例子,故事是这样的:教官已经排完了,但是又来了一批新同学要加入队伍,这时要使得队伍有序,教官这时就用了插入排序的办法,拉过来一个同学便开始从尾到头开始比较身高,遇到又身高比手里这个同学还要矮的便放在那个同学后面。当然极端情况就是没有更矮便放在排头了。这样便把新来的同学插入到了原来有序的队列中形成了新队列。

如图所示1~7是升序排列,现在要把5,8,6,9插入到队列中。这时就是一个插入排序的过程,显然当5和7比,小于成立于是往前移,遇到4,小于不成立(遇到了更矮的)于是就将该数放到4后面,就使得插入数并保持旧序列有序。
 

04.希尔排序

希尔排序可能在现实中用得比较少,其核心精神就是增量排序。实质就是给定待排序的序列,选择一个增量从头开始和每一增量位置的数进行直接插入排序。每一趟过后缩小一半,直到最后增量为1执行最后一趟。

 

 

05.   堆排序

堆排序即将原序列以完全二叉树的模型(i的祖先结点为i/2,i=1,2,3……), 每次调整序列为最大根或最小根(O(logn)),即每一趟找出当前剩余数中的最大值或最小值,经过n次堆调整就完成了最终的排序。时间复杂度O(nlogn)。

06.   归并排序

对于一个序列,将其划分为子序列,每个子序列经过排序,两两合并成最终的有序序列。

 

07.   快速排序


快速排序相对应用较多 ,核心思想将序列中选出的数作为划分依据,将序列划分为比这个数大部分(右侧序列),和比这个数小的部分(左侧序列)。这样最终确定了这个数的位置,同时左右侧序列可以再次递归下去。每一趟时间复杂度O(n),需要递归O(logn)次,时间复杂度为O(nlogn)。

 

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Guff_9hys/article/detail/785158
推荐阅读
相关标签
  

闽ICP备14008679号