黑马程序员技术交流社区

标题: 各种排序算法的实现及其比较 [打印本页]

---

作者: 18942668193    时间: 2015-1-29 12:34
标题: 各种排序算法的实现及其比较

3、2-路插入排序
        先读入前面两个数，大的放队首，小的放队尾，并分别用final和first作为指针指向它们，两个都向中间延伸，first向右增长，final向左减小。
如对 int src[] = {49,38,65,97,76,13,27,49_} 进行排序(这里为了区分两个49，
我给第二个49加了一个下划线。。。)
第一步得：

final                                                                       first
49        x        x        x        x        x        x        38
放入第三个数时，和队首first和队尾final分别进行比较，如果比first大则放它右边，并用first指向它。如果比final小，则放final的左边，并用final指向它。如果大小final，小于first，则插入到当前的first或final的位置。
第二步得：


final                                                           first
49          65        x        x        x        x        x        38
第三步：


         final                                                  first
49         65          97        x        x        x        x        38
第四步：


                  final                                      first
49         65          76           97        x        x         x        38
第五步：


                  final                              first         
49         65          76           97        x        x          13        38
第六步：


                  final                   first                 
49         65          76           97        x         13         27        38
第七步：


                           final          first                 
49         49_         65         76           97         13         27        38
这样做的好处是可以减少移动的次数。。。具体的程序实现留给读者去实现。。。

4、希尔排序
        又称为 缩小增量排序，它的基本思想是，先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本”有序时，再对全体记录进行一次直接插入排序。
以 int src[] = {49,38,65,97,76,13,27,49_,55,4} 为例，共有10个数，
我们先以10/2=5为跨度，进行第一趟排序。
第一趟：
49和13比较，38和27比较，65和49_比较，97和55比较，76和4比较，得：
13,27,49_,55,4,49,38,65,97,76 (从这里可以看出，希尔排序是不稳定的，当然下结论前还要看最后的结果。)
第二趟，我们以5-2=3为跨度，进行排序，可得：
13,4,49_,38,27,49,55,65,97,76 (到这时一看，有序多了！)
第三趟，心3-2=1为跨度，进行排序，得：
4，13，27，38，49_，49，55，65，76，97
当跨度减小到1时，就算是排序结束了。由结果可以断定，希尔排序是不稳定的排序。

Cpp代码  收藏代码
#include<iostream>  
using namespace std;  
  
int main()  
{  
    int src[] = {49,38,65,97,76,13,27,49,55,4}; //大家可试一试奇数个的情况  
  
    int i,j,tmp,cnt = sizeof(src)/4,dk = (cnt+1)/2,c=1;  
  
    while(dk > 0)  
    {  
        cout<<c++<<endl;  
        for(i = 0; i < cnt; i ++) cout<<src[i]<<" ";  
        cout<<endl;  
        for(i = dk; i < cnt; i ++)  
        {  
            if(src[i] < src[i-dk])  
            {  
                tmp = src[i];  
                src[i] = src[i-dk];  
                src[i-dk] = tmp;  
            }  
        }  
        dk = dk - 2 == 0 ? 1:dk-2;   
    }  
    cout<<c<<endl;  
    for(i = 0; i < cnt; i ++) cout<<src[i]<<" ";  
    cout<<endl;  
  
    getchar();  
    return 0;  
}  


六、各种内部排序的比较
        1、时间复杂度达到O(nlgn) 的排序算法有：快速排序、堆排序、归并排序。
        2、上面前四大类排序中，不稳定的排序有：希尔排序、快速排序、堆排序、简单的选择排序。
                        稳定的排序有：插入排序（除希尔外）、冒泡排序、归并排序。
        3、从平均时间性能而言，快速排序最佳，其所需要的时间最少，但快速排序在最坏的情况下，时间性能还不如堆排序和归并排序。

七、外部排序
        外部排序指的是大文件的排序，面试的时候，面试官喜欢问，给你一个非常非常大的文件（比如1T），一行一个数（或者一个单词），内存最多只有8G，硬盘足够大，CPU很高级……然后要你给这个文件里面的数据排序。你要怎么办？
这其实就要用到外部排序。就是说要借助外存储器进行多次的内/外存数据的交换，因为内存不足以加载所有的数据，所以只能一部分一部分地加载。
所以外部排序的思想就是：分两个独立的阶段。
首先，可按内存的大小，将外存上含n个记录的文件分成若干长度为 x 的子文件或段，依次读入内存，并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件 重新写入外存，通常称这些有序的子文件为归并段或顺串。然后，对这些归并段进行逐趟归并，使归并段逐渐由小到大，直至得到整个有序文件为止。
因此现在的问题就转化为如何归并两个大文件。这个读者朋友们想一下就明白了。就是把这两个文件按内存的大小，一部分一部分从小到大加载出来并，再写回外存。
当然归并的方法有很多种，作者本人也没怎么去研究。。。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2