管理咨询网站建设,中文网站建设英文,金融公司做网站域名,网站建设培训会讲话关于排序#xff0c;似乎很简单的很常见的概念#xff0c;却蕴含着很多技术#xff0c;下面是从不同的角度#xff0c;对排序的总结#xff1a;
直插希 冒泡快 选择堆
1 按照排序特性分类
首先按照排序本身的操作特性可以分为下面几种#xff1a; 插入排序 直接插入排…关于排序似乎很简单的很常见的概念却蕴含着很多技术下面是从不同的角度对排序的总结
直插希 冒泡快 选择堆
1 按照排序特性分类
首先按照排序本身的操作特性可以分为下面几种 插入排序 直接插入排序(Insert Sort) O(n^2)稳定 折半插入排序(Binary Insert Sort)不稳定 希尔排序(Shell Sort)不稳定 交换排序 冒泡排序(Bubble Sort) O(n^2)稳定 快速排序(Quick Sort)?? O(nlogn)不稳定 选择排序 直接选择排序(Select Sort) O(n^2)不稳定 锦标赛排序(Tournament Sort) O(nlogn)不稳定 堆排序(Heap Sort) O(nlogn)不稳定 归并排序(Merge Sort) O(nlogn) 稳定还取决与每段的排序算法选择。比如每段长度大于2 用稳定的直接插入排序然后再归并不一定要到长度为2 的粒度再归并。 基数排序(Radix Sort) O(d(nradix))稳定性 待定
2 每种排序算法的特点
冒泡排序在最优情况下只需要经过n- 1次比较即可得出结果这个最优情况那就是序列己是正序从100K的正序结果可以看出结果正是如此但在最坏情况下即倒序或一个较小值在最 后下沉算法将需要n(n-1)/2次比较。所以一般情况下特别是在逆序时它很不理想。它是对数据有序性非常敏感的排序算法。 冒泡排序它是冒泡排序的改良一次下沉再一次上浮最优情况和最坏情况与冒泡排序差不多但是一般情况下它要好过冒泡排序它一次下沉再一次上浮这样避免了因一个数的逆序而造成巨大的比较。如2,3,4,…,n- 1,n,1用冒泡排序需要n(n-1)/2次比较而此排序只要3轮,共比较(n-1)(n-2)(n-3)次第一轮1将上移一位第二轮1将 移到首位第三轮将发现无数据交换序列有序而结束。但它同样是一个对数据有序性非常敏感的排序算法只适合于数据基本有序的排序。 快速排序它同样是冒泡排序的改进它通过一次交换能消除多个逆序这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下它的排序时间复杂度为(nlog2n)。 即每次划分序列时能均匀分成两个子串。但最差情况下它的时间复杂度将是(n^2)。即每次划分子串时一串为空另一串为m-1程序中的100K正 序和逆序就正是这样如果程序中采用每次取序列中部数据作为划分点那将在正序和逆时达到最优。从100K中正序的结果上看“快速排序”会比“冒泡排 序”更慢这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”在理论上讲如果每次能均匀划分序列它将是最快的排序算法 因此称它作快速排序。虽然很难均匀划分序列但就平均性能而言它仍是基于关键字比较的内部排序算法中速度最快者。 直接选择排序简单的选择排序它的比较次数一定n(n- 1)/2。也因此无论在序列何种情况下它都不会有优秀的表现从上100K的正序和反序数据可以发现它耗时相差不多相差的只是数据移动时间可见对 数据的有序性不敏感。它虽然比较次数多但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。 堆排序由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤是建堆二是排序调整堆。所以一般在小规模的序列中不合适但对于较大的序列将表现出优越的性能。 直接插入排序简 单的插入排序每次比较后最多移掉一个逆序因此与冒泡排序的效率相同。但它在速度上还是要高点这是因为在冒泡排序下是进行值交换而在插入排序下是值 移动所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较在最坏情况下将需要n(n-1)/2次比较。 希尔排序增量的选择将影响希尔排序的效率。但是无论怎样选择增量最后一定要使增量为进行一次直接插入排序。但它相对于直接插入排序由于在子表中每进行一次比较就可能移去整个经性表中的多个逆序从而改善了整个排序性能。希尔排序算是一种基于插入排序的算法所以对数据有序敏感。 归并排序归并排序是一种非就地排序将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大那将不适合。但可改造成索引操作效果将非常出色。 基数排序在程序中采用的是以数值的十进制位分解然后对空间采用一次性分配因此它需要较多的辅助空间(10*n10), 但我们可以进行其它分解如以一个字节分解空间采用链表将只需辅助空间n256。基数排序的时间是线性的(即O(n))。由此可见基数排序非常吸引人但它也不是就地排序若节点数据量大时宜改为索引排序。但基数排序有个前提要关键字能象整型、字符串这样能分解若是浮点型那就不行了。
总结 各种排序方法比较 简单排序中直接插入最好快速排序最快当文件为正序时直接插入和冒泡均最佳。
3. 按平均时间将排序分为四类 1平方阶(O(n2))排序 一般称为简单排序例如直接插入、直接选择和冒泡排序 2线性对数阶(O(nlgn))排序 如快速、堆和归并排序 3O(n1)阶排序 是介于0和1之间的常数即01如希尔排序 4线性阶(O(n))排序 如桶、箱和基数排序。
4. 影响排序效果的因素 因为不同的排序方法适应不同的应用环境和要求所以选择合适的排序方法应综合考虑下列因素 ①待排序的记录数目n ②记录的大小(规模) ③关键字的结构及其初始状态 ④对稳定性的要求 ⑤语言工具的条件 ⑥存储结构 ⑦时间和辅助空间复杂度等。
5 .不同条件下排序方法的选择 (1)若n较小(如n≤50)可采用直接插入或直接选择排序。 当记录规模较小时直接插入排序较好否则因为直接选择移动的记录数少于直接插人应选直接选择排序为宜。 (2)若文件初始状态基本有序(指正序)则应选用直接插人、冒泡或随机的快速排序为宜 (3)若n较大则应采用时间复杂度为O(nlgn)的排序方法快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法当待排序的关键字是随机分布时快速排序的平均时间最短 堆排序所需的辅助空间少于快速排序并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 若要求排序稳定则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件然后再两两归并之。因为直接插入排序是稳定 的所以改进后的归并排序仍是稳定的。
6.排序算法的稳定性 1 稳定的如果存在多个具有相同排序码的记录经过排序后这些记录的相对次序仍然保持不变则这种排序算法称为稳定的。 插入排序、冒泡排序、归并排序、分配排序桶式、基数都是稳定的排序算法。 2不稳定的否则称为不稳定的。 直接选择排序、堆排序、shell排序、快速排序都是不稳定的排序算法
