7-7各种排序方法的比较

7-7各种排序方法的比较v第七章排序技术学什么？各种排序方法的使用范例各种排序方法的综合比较使用范例#include<iostream>#include<cmath>usingnamespacestd;//将排序类定义和各个排序算法的成员函数定义放到这里

intmain(){intselect,r[10]={2,5,1,7,9,4,3,6,5,8};SortL{r,10};cout<<"1.直接插入排序2.希尔排序"<<endl;cout<<"3.起泡排序4.快速排序"<<endl;cout<<"5.简单选择排序6.堆排序"<<endl;cout<<"7.二路归并递归排序8.二路归并非递归排序"<<endl;cout<<"请输入使用的排序技术编号：";cin>>select;switch(select){case1:L.InsertSort();break;case2:L.ShellSort();break;case3:L.BubbleSort();break;case4:L.QuickSort(0,9);break;case5:L.SelectSort();break;case6:L.HeapSort();break;case7:L.MergeSortRecusion(0,9);break;case8:L.MergeSort();break;default:cout<<"输入排序编号错误"<<endl;break;}L.Print();return0;}排序方法平均情况直接插入排序O(n2)希尔排序O(nlog2n)~O(n2)起泡排序O(n2)快速排序O(nlog2n)简单选择排序O(n2)堆排序O(nlog2n)归并排序O(nlog2n)（1）直接插入排序、简单选择排序和起泡排序属于一类，时间复杂度为O(n2)；从平均情况看快速排序是目前最快的一种排序方法（3）希尔排序的时间性能取决于增量序列，介于O(n2)和O(nlog2n)之间。（2）堆排序、快速排序和归并排序属于一类，时间复杂度为O(nlog2n)；比较时间性能排序方法最好情况直接插入排序O(n)希尔排序O(n1.3)起泡排序O(n)快速排序O(nlog2n)简单选择排序O(n2)堆排序O(nlog2n)归并排序O(nlog2n)从最好情况看（1）直接插入排序和起泡排序最好，O(n)；（2）其他排序算法的最好情况与平均情况相同。如果待排序序列接近正序，首选直接插入排序和起泡排序比较时间性能排序方法最坏情况直接插入排序O(n2)希尔排序O(n2)起泡排序O(n2)快速排序O(n2)简单选择排序O(n2)堆排序O(nlog2n)归并排序O(nlog2n)（1）快速排序的时间复杂度为O(n2)；从最坏情况看（3）最坏情况对直接选择排序、堆排序和归并排序影响不大。（2）直接插入排序和起泡排序虽然与平均情况相同，但系数大约增加一倍，所以运行速度将降低一半；如果待排序序列接近正序或逆序，不推荐使用快速排序比较时间性能从空间性能看排序方法辅助空间直接插入排序O(1)希尔排序O(1)起泡排序O(1)快速排序O(log2n)~O(n)简单选择排序O(1)堆排序O(1)归并排序O(n)（1）归并排序的空间复杂度为O(n)；（2）快速排序的空间复杂度为O(log2n)~O(n)；（3）其它排序方法的空间复杂度为O(1)。比较空间性能稳定性与简单性（1）稳定：包括直接插入排序、起泡排序和归并排序；（1）简单算法：包括直接插入排序、简单选择排序和起泡排序，从算法简单性看（2）不稳定：包括希尔排序、简单选择排序、快速排序和堆排序。从稳定性看（2）改进算法，较复杂：包括希尔排序、堆排序、快速排序和归并排序。记录本身信息量从记录本身信息量的大小看记录本身信息量越大，占用的存储空间就越多，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。记录个数不多且记录本身的信息量较大时，首选简单选择排序算法排序方法最好情况最坏情况平均情况直接插入排序O(n)O(n2)O(n2)起泡排序0O(n2)O(n2)简单选择排序0O(n)O(n)关键码的分布从关键码的分布看（1）当待排序记录按关键码有序时，插入排序和起泡排序能达到O(n)的时间复杂度；对于快速排序而言，这是最坏情况，时间性能蜕化为O(n2)；（2）简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键码的分布而改变。各种排序算法各有优缺点，应该根据实际情况选择合适的排序算法更深入的比较对于一般的内部排序应用插入排序、希尔排序、归并排序和快速排序是经常选用的方法，究竟使用哪个方法依赖于输入规模和底层环境。快速排序不如插入排序好。因为快速排序是递归执行的，所以这种情况会经常发生。解决方法是对于小数组不使用递归快速排序，而使用插入排序等对小数组高效的排序算法，相对于自始至终使用快速排序节省大约15%的运行时间。对于字符串排序对于少量的输入如果字符串中的字符取自较小字母表，并且字符串或者相对较短或者非常相似，对字符串进行基数排序的效率会特别好。更深入的比较Java标准库使用归并排序算法在Java中执行泛型排序，由于不容易使用内联，动态调度的开销会减慢执行速度，因此比较元素非常费时。但是移动元素相对省时，可以采用引用赋值，而不是庞大的对象拷贝。归并排序的比较次数是所有常