排序算法的性能分析

标签：性能 元素 情况 算法 序列 n2 排序 复杂度

排序算法有很多，但适用的场景不尽相同，今天就做个总结，关注时间复杂度、稳定性，最好情况和最坏性能。算法稳定性的含义参见对排序算法稳定性的理解 - BeLady - 博客园 (cnblogs.com)

1 插入排序

　　1.1 直接插入

　　　　原理 将元素插入到已排好序的序列中，插入时需要与已排好序的序列进行多次比较和交换，直到找到合适的位置插入

　　　　时间复杂度 Ο(n²)

　　　　最好情况 初始序列已经是正序，每次插入只需要进行一次比较，时间复杂度为Ο(n)

　　　　最坏情况 初始序列是逆序，每次插入都需要与前面的元素进行比较，时间复杂度为Ο(n²)

　　　　稳定性 稳定

　　1.2 希尔排序

　　　　原理 直接插入排序的优化，相当于多次的直接插入排序，下图是一个直观的例子，相比于直接插入排序，希尔排序让元素每次跨越一大步，而不是一点一点的移动，从而加快排序速度

                        

　　　　时间复杂度 Ο(n^1.5)，证明太复杂了，有时间单独写一篇随笔出来

　　　　最好情况和最坏情况跟直接插入排序类似

　　　　稳定性 不稳定，因为多趟排序可能会使相同元素在不同的组中

2 选择排序

　　2.1 直接选择

　　　   原理 每次选择当前未排序序列中的最小(大)元素置于序列最前面，选择的过程中需要进行元素的比较和交换

　　　　时间复杂度 Ο(n²)，其实不管是什么情况，排序的过程都需要进行到底才能知道结果，所以最好情况和最坏情况也都是Ο(n²)

　　　　稳定性 不稳定，因为交换过程中会破坏相同元素的初始次序

　　2.2 堆排序

　　　　原理堆排序利用了二叉树可以实现对数级别搜索的原理，降低了直接选择排序中搜索最大(小)元素的时间，下面给出具体例子

1. 1. 给定无序数组 

　　　　　　　 

　　　　　　2. 建堆，按照初始数组的顺序构建二叉树

　　　　　　

　　　　　　3. 堆的初始调整，满足父节点大于等于任意一个子节点

　　　　　　

　　　　　　4. 堆排序，选择根节点与最底层的非有序区交换，然后调整堆，最终全部有序

　　　　　　

　　　　时间复杂度 建堆和初始调整堆的时间复杂度都是Ο(n)，排序的时间复杂度是Ο(nlogn)，对于所有情况都是一样，需要进行到底才能知道结果，因此最好和最坏情况都是Ο(nlogn)

　　　　稳定性 不稳定，当父节点和子节点相同时，父节点会先被换掉

3 交换排序

　　3.1 冒泡排序

　　　　原理 比较前后相邻两个值的大小，如果前边比后边大，则进行交换

　　　　 时间复杂度 Ο(n²)

　　　　 最好情况 Ο(n)，如果不对冒泡排序做优化的话任何情况的时间复杂度都是Ο(n²)，优化的点在于定义一个检测此趟冒泡是否发生了交换，如果不发生交换就表明当前序列已经有序，可以停止冒泡

　　　　最坏情况 Ο(n²)

　　3.2 快速排序

　　　　原理 指定一个pivot，遍历序列，将所有大于pivot的值放在右边，小于pivot的值放在左边，以上步骤递归进行，快速排序是对冒泡排序的改进，相比与冒泡排序，快速排序一次遍历除了确定一个元素的位置外，还进行了分区，下面举个例子

　　　　　　1. 给定无序数组

　　　　　　

　　　　　　2. 确定pivot，一般选第一个

　　　　　　

　　　　　　3. 分区

　　　　　　

　　　　时间复杂度 Ο(nlogn)

　　　　最好情况 Ο(nlogn)

　　　　最坏情况 Ο(n²)，序列一开始就有序，另外递归的深度也会限制其性能

　　　　稳定性 不稳定，pivot交换时有可能打乱次序

4 归并排序

　　原理 分治思想，将序列划分为两个长度相等的子序列，分别对子序列进行排序，然后合并两个有序子序列，递归进行，下面给出例子　　　　

　　

　　时间复杂度 Ο(nlogn)，任何情况的时间复杂度一样，最好情况和最坏情况的时间复杂度也是 Ο(nlogn)

　　稳定性 稳定

经过以上分析，可以发现排序算法的基本思路是通过相邻元素的比较确定元素位置，而优化的思路在于采取跨越式的元素移动，比如希尔排序对直接插入排序的优化，快速排序对冒泡排序的优化等

本人研究牲一枚，请各位大佬批评指正~~~　

标签：性能,元素,情况,算法,序列,n2,排序,复杂度
From： https://www.cnblogs.com/BeLady/p/17207666.html