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

一、附加条件

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

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

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

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

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

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

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

二、稳定性的口诀

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

三、排序对比表格

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）。