上海制作网站公司哪家好,大连响应式网站建设,郑州手工外发加工网,四川网络推广公司哪家好1.从时间复杂度比较 从平均时间复杂度来考虑#xff0c;直接插入排序、冒泡排序、直接选择排序是三种简单的排序方法#xff0c;时间复杂度都为O(n2)#xff0c;而快速排序、堆排序、二路归并排序的时间复杂度都为O(nlog2n)#xff0c;希尔排序的复杂度介于这两者之间。…1.从时间复杂度比较 从平均时间复杂度来考虑直接插入排序、冒泡排序、直接选择排序是三种简单的排序方法时间复杂度都为O(n2)而快速排序、堆排序、二路归并排序的时间复杂度都为O(nlog2n)希尔排序的复杂度介于这两者之间。若从最好的时间复杂度考虑则直接插入排序和冒泡排序的时间复杂度最好为O(n)其它的最好情形同平均情形相同。若从最坏的时间复杂度考虑则快速排序的为O(n2)直接插入排序、冒泡排序、希尔排序同平均情形相同但系数大约增加一倍所以运行速度将降低一半最坏情形对直接选择排序、堆排序和归并排序影响不大.2从空间复杂度比较 归并排序的空间复杂度最大为O(n)快速排序的空间复杂度为O(log2n)其它排序的空间复杂度为O1。 3.从稳定性比较 直接插入排序、冒泡排序、归并排序是稳定的排序方法而直接选择排序、希尔排序、快速排序、堆排序是不稳定的排序方法。 4从算法简单性比较 直接插入排序、冒泡排序、直接选择排序都是简单的排序方法算法简单易于理解而希尔排序、快速排序、堆排序、归并排序都是改进型的排序方法算法比简单排序要复杂得多也难于理解。 迄今为止已有的排序方法远远不止本章讨论的这些方法人们之所以热衷于研究多种排序方法不仅是由于排序在计算机中所处的重要地位而且还因为不同的方法各有其优缺点可适用于不同的场合。选取排序方法时需要考虑的因素有待排序的记录数目n记录本身信息量的大小关键字的结构及分布情况对排序稳定性的要求语言工具的条件辅助表的大小等。依据这些因素可得出如下几点结论1若n较小譬如n50)可采用直接插入排序或直接选。由于直接插入排序所需记录移动操作较直接选择排序多因此若记录本身信息量较大时则选用直接选择排序为宜。 2若文件的初始状态已是按关键字基本有序则选用直接插入排序泡排序为宜。 3若N较大则应根据其时间复杂度来选择排序方法快速排序\堆排序或归并排序快速排序是目前基于内部排序的中被认为是最好的方法档待排序的关键字是随机时快速排序的平均时间最少但堆排序所需的辅助空间少于快速排序并且不会出现序可能出现的最坏情况这两种排序方法都是不稳定的若要求排序稳定则可选用归并排序。但本文章结合介绍的两两归并排算法并不值得提倡通常可以将它和直接排序结合在一起用。先利用直接插入排序求得的子文件然后再两两归并之。因为直接插入排序是稳定的所以改进后的归并排序是稳定的。4前面讨论的排序算法除排序外都是在一维数组上实现的当记录本身信息量较大时为了避免浪费大量时间移动记录可以用链表作为存储结构如插入排序和归并排序都易于在链表上实现并分别称之为表和归并表但有的方法如快速排序和堆排序在链表上难于实现在这种情况下可以提取关键字建立索引表然后对索引表进行排序。然而更为简单的方法是;引入一个整形向量作为辅助表排序前若排序算法中要求交换则只需交换R[I]和R[j]即可排序结束后向量就指示了记录之间的顺序关系.转载于:https://www.cnblogs.com/sheropan/p/5022437.html
