各种排序的比较

àì夳堔傛蜴生んèń 2022-08-19 13:11 180阅读 0赞

**（一）直接插入排序**

算法简洁，但是只有当待排元素n比较少的时候效率才高  
所需空间：一个当前元素的哨兵array\[0\]即可  
所需时间：主要与所需关键字的比较次数及移动的次数有关  
最坏的情况——逆序：总的比较次数为n(n-1)/2，记录的移动次数也为n(n-1)/2  
最好的情况——正序：比较次数为n-1，记录移动次数为0  
由此可以推断出插入排序算法的平均时间为O(n^2)，最坏的情况为O(n^2),辅助存储为O(1)，算法优化：减少比较和移动的次数  
稳定性：稳定的，插入排序本就是在一个有序的序列里插入一个新的元素，当遇到两个或多个一样的元素时，自然是一律放到相同元素的最后面，所以这是稳定的  
**（二）希尔排序**  
也属于插入排序类，又称减小增量排序  
基本思想：将序列由某一个变化的增量分为若干子序列，再对这些子序列进行直接插入排序，等到整个序列基本有序的时候，再对整体进行一次直接插入排序  
出发点：直接插入排序在n值较小以及在序列大致有序的时候效率很高  
稳定性：我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。  
希尔排序的时间会比直接插入排序少，但是少多少依赖于增量序列的函数，无法讨论  
**（三）冒泡排序**  
最坏情况——逆序：需要进行n(n-1)/2次比较，n-1次排序，n(n-1)/2次记录的移动  
最好情况——正序：需要进行n-1次比较，0次排序，0次移动  
稳定性:冒泡排序交换的是两个相邻元素，如果两个元素相等，我们是不会交换两个元素的位置的，所以这个排序是稳定的  
**（四）快速排序**  
平均时间：O(nlogn)，在平均时间性能上来说属于最佳的排序算法  
最坏情况——逆序：O(n^2)  
辅助存储：O(logn)  
快排所需时间为：一次对整体记录进行划分的时间 + 对前k-1个记录进行快排的时间 + 对后n-k个记录进行快排的时间，当然，一次对整体进行划分的时间和n值成正比的  
稳定性：快排有两个指针low、high和一个key，key一般为第一个元素，也就是枢轴，j往前走，当j的内容小于key的时候，i就往后走，当i的内容大于key的时候，i和j的内容就互换，当i>j的时候，i和key互换内容，这是一趟排序，这时候很容易把稳定性打乱的  
**（五）堆排序**  
堆排序适用于n值较大的文件，但对于n值较小的还是选择希尔排序之类吧  
最坏情况和平均时间是一样的：O(nlogn)  
辅助空间：O(1)即：一个记录大小共交换的空间  
性能分析：1、堆排序是基于完全二叉树的，对于深度为k的堆，至多2^k-1个记录，我们从最后一个非终端结点2^(k-1)的记录开始筛选并建立一个大顶堆，此时与关键字的比较次数至多为2(k-1)次；2、在建立堆的时候，由第i层记录至多2^(i-1)次，以它们为根的记录深度为h-i-1，那么调用n/2次筛选算法的时候，与关键字比较的次数至多为4n次；再看，n记录的完全二叉树深度为log2n+1，那么建立新堆调用n-1次筛选算法，总共的比较次数不超过2n(log2n)，也就是O(nlog2n)  
稳定性：目前只知道这是不稳定的。。。。。有木有大牛能解释清楚  
**（六）归并排序**  
性能分析：一次归并排序会调用n/2h次归并两个相邻有序序列的算法，得到一个长度为2h的有序序列，整个算法会进行log2n次  
时间：O(nlogn)，最坏情况亦如此  
辅助空间：归并排序需要的空间的比较多，因为需要存储一个经过归并的序列，它所需要的空间为O(n)  
稳定性：归并排序把序列分为若干含有1个或2个元素的序列，1个元素的序列默认为有序，2个元素的可以直接排序，同样，我们是不会去交换两个相等元素的值的，这样将第一次归并的序列看为新的子序列，重复归并直到有序，这期间都是稳定的  
**（七）基数排序**  
基本思想：基数排序与前几种排序均不同，它是将关键字分解成若干个原子关键字，通过对原子关键字的排序来实现对关键字的排序，例如3位数的排序可以分为个位数的排序、十位数的排序、百位数的排序  
（采用链式存储结构来实现吧，需要用到队列）  
性能分析：对n个数进行一次未被排序的最低位数的收集时，先对其进行一次分配，时间复杂度为O(n)，然后对其收集，其时间复杂度为O(rd)（已知关键字所含原子关键字的取值范围为0～d，rd为原子关键字的取值范围），即一次分配收集的时间复杂度为O(d(n+rd))，整个排序的收集分配次数依据数值而定，三位数的就需要3次  
辅助空间：O(2rd)即：2rd个队列  
所需时间：平均时间和最坏情况的时间一致：O(d(n+rd))，也为O(d\*n)  
稳定性：基数排序从低位开始分配、收集，一直到最高位排序完成，是分配和收集的时候是不可能调整两个相同元素的位置的，是稳定的  
**（八）综合分析**  
1、就平均时间而言，快排最为优秀，但在最坏情况下不是最好的  
2、在n值较大的时候，使用堆排序和归并排序较为有效，这其中以归并排序时间最少，但是需要更多的空间  
3、n值较大且关键字较小时，基数排序较适合，空间也只需要多加几个队列指针即可；而且基数排序是稳定性最强的，快排、堆排序、希尔排序都不稳定

4、从数据存储结构来看，若排序中记录未大量移动，可采用顺序存储结构，若记录大量移动，则可采用静态链表实现（表插入排序、链式基数排序）