专栏首页g歌德a数据结构之内外排序

数据结构之内外排序

一、内排序

排序类别

排序方法

最好时间复杂度

平均时间复杂度

最坏时间复杂度

辅助空间

稳定性

备注

插入类

插入

O(n)

O(n2)

O(n2)

O(1)

稳定

大部分已排序时较好

希尔排序

-

O(ns),1<s<2

-

O(1)

不稳定

s是所选分组

交换类

冒泡排序

O(n)

O(n2)

O(n2)

O(1)

稳定

n小时较好

快速排序

O(nlogn)

O(nlogn)

O(n2)

O(logn)

不稳定

n大时较好

选择类

选择

O(n2)

O(n2)

O(n2)

O(1)

不稳定

n小时较好

堆排序

O(nlogn)

O(nlogn)

O(nlogn)

O(1)

不稳定

n大时较好

归并排序

O(nlogn)

O(nlogn)

O(nlogn)

O(n)

稳定

n大时较好

基数排序

O(d(n+rd))

O(d(n+rd))

O(d(n+rd))

O(rd)

稳定

见下文

1.插入排序(InsertSort)

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。这样,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序,或者重复排序超过200数据项的序列。

void insertSort(int a[],int n)   //插入排序  
{  
    int i,j;  
    int t;  
    for(i=1;i<n;i++)  
    {  
        t=a[i];   //保存当前无序表中的第一个数据  
        j=i-1;  
        while(j>=0 && a[j]>t)  
        {  
            a[j+1]=a[j];  
            j--;  
        }  
        a[j+1]=t;   //将数据插入有序表中  
    }  
}  

2.希尔排序(ShellSor)

希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比O(n2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

Shell排序的分组合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单,它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。

void shellSort(int a[],int n)   //希尔排序  
{  
    int i,j,gap;  
    int t;  
    for(gap=n/2;gap>0;gap/=2)  
        for(i=gap;i<n;i++)  
        {  
            t=a[i];  
            j=i-gap;  
            while(j>=0 &&a[j]>t)  
            {  
                a[j+gap]=a[j];  
                j-=gap;  
            }  
            a[j+gap]=t;  
        }  
}  

3.冒泡排序(BubbleSort)

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,就不会再把它们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

冒泡排序是最慢的排序算法,在实际运用中它是效率最低的算法。

void bubbleSort(int a[],int n)   //冒泡排序  
{  
    int i,j;  
    int t;  
    for(i=0;i<n;i++)  
        for(j=0;j<n-i-1;j++)  
            if(a[j]>a[j+1])  
            {  
                t=a[j];  
                a[j]=a[j+1];  
                a[j+1]=t;  
            }  
}  

4.快速排序(QuickSort)

快速排序有两个方向,左边的i下标一直往右走,当a[i]<= a[center_inde],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j]> a[center_index]。如果i和j都走不动了,i<= j, 和a[j],重复上面的过程,直到i>j。交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为{5,3,3,4,3,8,9,10,11},现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j]交换的时刻。

快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。 ⑴如果不多于1个数据,直接返回。 ⑵一般选择序列最左边的值作为支点数据。 ⑶将序列分成2部分,一部分都大于支点数据,另外一部分都小于支点数据。 ⑷对两边利用递归排序数列。

快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法,但是就通常情况而言,没有比它更快的了。快速排序是递归的,对于内存非常有限的机器来说,它不是一个好的选择。

void quickSort(int a[],int s,int e)  //对a[s]至a[e]的元素进行快速排序  
{  
    int i=s,j=e;  
    int t;  
    if(s<e)  
    {  
        t=a[s];  
        while(i!=j)  
        {  
            while(j>i && a[j]>t) j--;  //从右向左扫描,找第一个小于t的a[j]  
            if(i<j)  //表示找到这样的a[j]  
            {  
                a[i]=a[j];  
                i++;  
            }  
            while(i<j && a[i]<=t) i++;   //从左向右扫描,找第一个大于t的a[i]  
            if(i<j)   //表示找到这样的a[i]  
            {  
                a[j]=a[i];  
                j--;  
            }  
        }  
        a[i]=t;    //将a[s]放到a[s]至a[e]的恰当位置i处,使得其左边的元素都不大于它,其右边的元素都不小于它。  
        quickSort(a,s,i-1);    //对左区间递归排序  
        quickSort(a,i+1,e);    //对右区间递归排序  
    }  
}  

5.选择排序(SelectSort)

选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。例如,序列{5,8,5,2,9},第一趟选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段,在实际中使用较少。

void selectSort1(int a[],int n)   //选择排序  
{  
    int i,j;  
    int t;  
    for(i=0;i<n-1;i++)   //数据起始位置,从0到倒数第二个数据  
        for(j=i+1;j<n;j++)   ////在剩下的数据中循环  
        {  
            if(a[i]>a[j])    // //如果有比它小的,交换两者  
            {  
                t=a[i];  
                a[i]=a[j];  
                a[j]=t;  
            }  
        }  
}  
  
void selectSort2(int a[],int n)   //选择排序的改进,减少了交换的次数  
{  
    int i,j,small;  
    int t;  
    for(i=0;i<n-1;i++)  //数据起始位置,从0到倒数第二个数据  
    {  
        small=i;    //记录最小数据的下标  
        for(j=i+1;j<n;j++)   //在剩下的数据中寻找最小数据  
        {  
            if(a[j]<a[small])   //如果有比它更小的,记录下标  
                small=j;  
        }  
        t=a[small];    //将最小数据和未排序的第一个数据交换  
        a[small]=a[i];  
        a[i]=t;  
    }  
}  

6.堆排序(HeapSort)

堆的结构是结点i的孩子为2i和2i+1节点,大顶堆要求父结点大于等于其2个子结点,小顶堆要求父结点小于等于其2个子结点。在一个长为n的序列,堆排序的过程是从第n/2开始和其子结点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1,n/2-2, ...1这些个父结点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父结点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

堆排序适合于数据量非常大的场合(百万数据)。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,由于快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。

void max_heapify(int a[], int start, int end)   //调整为大顶堆  
{  
    //父结点和子结点下标  
    int dad = start, son = start * 2 + 1;  
    while(son <= end)   //子结点下标在数组范围内才能比较  
    {  
        //先比较左右孩子的大小,选择大孩子的下标  
        if(son+1 <= end && a[son+1] > a[son]) son++;   
  
        if(a[son] > a[dad])  
        {  
            int t = a[son];  
            a[son] = a[dad];  
            a[dad] = t;  
            dad = son;  
            son = dad * 2 + 1;  
        }  
        else  
            break;  
    }  
}  
  
void heapSort(int a[], int n)   //堆排序  
{  
    int i;  
    //初始化数组为大顶堆,i=n/2-1表示最后一个父结点的下标  
    for(i=n/2-1; i>=0; i--) max_heapify(a, i, n-1);  
  
    for(i=n-1; i>0; i--)    //根作为最大值调整到当前序列的最后  
    {  
        int t = a[0];  
        a[0] = a[i];  
        a[i] = t;  
        max_heapify(a, 0, i-1);  
    }  
}  

7.归并排序(MergeSort)

归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

归并排序比堆排序稍微快一点,但是需要比堆排序多一倍的内存空间,因为它需要一个额外的数组。

void mergearray(int a[], int first, int mid, int last, int temp[])  //将有二个有序数列a[first...mid]和a[mid+1...last]合并。  
{  
    int i=first, j=mid+1;  
    int m=mid, n=last;  
    int k=0;  
    while (i<=m && j<=n)  
    {  
        if (a[i]<a[j])  
            temp[k++]=a[i++];  
        else  
            temp[k++]=a[j++];  
    }  
    while (i<=m)  
        temp[k++]=a[i++];  
    while (j<=n)  
        temp[k++]=a[j++];  
    for (i=0;i<k;i++)  
        a[first+i]=temp[i];  
}  
  
void mergesort(int a[], int first, int last, int temp[])  
{  
    if (first<last)  
    {  
        int mid=(first+last)/2;  
        mergesort(a, first, mid, temp);    //左边有序  
        mergesort(a, mid+1, last, temp);  //右边有序  
        mergearray(a, first, mid, last, temp);   //再将二个有序数列合并  
    }  
}  
  
void MergeSort(int a[], int n)  
{  
    int *p=(int *)malloc(n*sizeof(int));  
    mergesort(a, 0, n - 1, p);  
    free(p);  
}  

8.基数排序(RadixSort)

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法,但是它只能用于整数的排序,如果我们要把同样的办法运用到浮点数上,我们必须了解浮点数的存储格式,并通过特殊的方式将浮点数映射到整数上,然后再映射回去,这是非常麻烦的事情,因此,它的使用同样也不多。而且,最重要的是,这样算法也需要较多的存储空间。

时间效率:设待排序列为n个记录,d个关键码,关键码的取值范围为radix,则基数排序的时间复杂度为O(d(n+radix)),其中,一趟分配时间复杂度为O(n),一趟收集时间复杂度为O(radix),共进行d趟分配和收集。

int maxbit(int a[],int n)    //求数组元素的最大位数  
{  
    int d=1,i=0;  //保存最大的位数  
    int p=10;  
    for(i=0;i<n;i++)  
    {  
        while(a[i]>=p)  
        {  
            p*=10;  
            d++;  
        }  
    }  
    return d;  
}  
  
void radixsort(int a[],int n)    //基数排序  
{  
    int d = maxbit(a,n);  
    long *tmp=(long *)malloc(n*sizeof(long));  
    long count[10];  //计数器,统计每位基数的个数  
    long i,j,k;  
    int radix=1;  
    for(i=1;i<=d;i++)  //进行d次排序  
    {  
        for(j=0;j<10;j++)    //每次分配前清空计数器  
            count[j]=0;  
        for(j=0;j<n;j++)   //统计基数出现的次数  
        {  
            k=(a[j]/radix)%10;  
            count[k]++;  
        }  
        for(j=1;j<10;j++)  //将tmp中的位置依次分配给每个计数器  
            count[j]=count[j-1]+count[j];  
        for(j=n-1;j>=0;j--)  //根据计数器,将记录依次收集到tmp中  
        {  
            k=(a[j]/radix)%10;  
            count[k]--;  
            tmp[count[k]]=a[j];  
        }  
        for(j=0;j<n;j++)  //将临时数组的内容复制到数组a中  
            a[j] = tmp[j];  
        radix = radix*10;  
    }  
    free(tmp);  
}  

二、外排序

当待排序的文件比内存的可使用容量还大时,文件无法一次性放到内存中进行排序,需要借助于外部存储器(例如硬盘、U盘、光盘),这时就需要用外部排序算法来解决。

外部排序算法由两个阶段构成: 按照内存大小,将大文件分成若干长度为 l 的子文件(l 应小于内存的可使用容量),然后将各个子文件依次读入内存,使用适当的内部排序算法对其进行排序(排好序的子文件统称为“归并段”或者“顺段”),将排好序的归并段重新写入外存,为下一个子文件排序腾出内存空间; 对得到的顺段进行合并,直至得到整个有序的文件为止。

例如,有一个含有 10000 个记录的文件,但是内存的可使用容量仅为 1000 个记录,毫无疑问需要使用外部排序算法,具体分为两步: 1. 将整个文件其等分为 10 个临时文件(每个文件中含有 1000 个记录),然后将这 10 个文件依次进入内存,采取适当的内存排序算法对其中的记录进行排序,将得到的有序文件(初始归并段)移至外存。 2. 对得到的 10 个初始归并段进行如图所示的两路归并,直至得到一个完整的有序文件。

有 10 个初始归并段到一个有序文件,共进行了 4 次归并,每次都由 m 个归并段得到 ⌈m/2⌉ 个归并段,这种归并方式被称为 2-路平衡归并。

对于外部排序算法来说,影响整体排序效率的因素主要取决于读写外存的次数,即访问外存的次数越多,算法花费的时间就越多,效率就越低。

对于同一个文件来说,对其进行外部排序时访问外存的次数同归并的次数成正比,即归并操作的次数越多,访问外存的次数就越多。使用2-路平衡归并的方式,举一反三,还可以使用 3-路归并、4-路归并甚至是 10-路归并的方式,下图为 5-路归并的方式: 对于 k-路平衡归并中 k 值得选择,增加 k 可以减少归并的次数,从而减少外存读写的次数,最终达到提高算法效率的目的。除此之外,一般情况下对于具有 m 个初始归并段进行 k-路平衡归并时,归并的次数为:s=」logk⁡m」(其中 s 表示归并次数)。

从公式上可以判断出,想要达到减少归并次数从而提高算法效率的目的,可以从两个角度实现: 1. 增加 k-路平衡归并中的 k 值; 2. 尽量减少初始归并段的数量 m,即增加每个归并段的容量。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C程序设计(第四版)课后习题完整版 谭浩强编著

    答:程序就是一组计算机能识别和执行的指令。 程序设计是指从确定任务到得到结果,写出文档的全过程。(一般经历6个阶段:①问题分析;②设计算法;③编写程序;④对源程...

    用户2417870
  • 线性表的基本操作

    实现线性表的增加删除定位等功能。(编译执行环境vc6.0,因为目标院校上机考是用这个版本的)

    用户2417870
  • 微信开发准备 一、微信公众号的申请二、开发环境三、内网穿透四、项目搭建

      不过我们测试开发还是申请一个平台测试账号来的方便,功能还多。微信扫码登陆即可,一个微信账号只能开通一个测试账号。平台测试账号地址:点我。

    用户2417870
  • 基础算法|7 希尔排序 HDU 1425

    我们从最初的冒泡排序算法,到上篇文章的折半插入排序算法,我们一共学习了5种排序算法,相信以大家的聪明才智肯定都消化了^_^。在本篇文章中,我们又将学习第6种排序...

    ACM算法日常
  • 面试中可能被问到的常用排序算法

    排序算法是一种比较简单的算法,从我们一开始接触计算机编程开始接触的可能就是排序或者搜索一类的算法,但是因为排序在其他的一些算法中应用较多,所以为了提高性能已经研...

    本人秃顶程序员
  • hdu1066

    @坤的
  • c++之引用

    b引用a,b和a指向相同的内存地址, 所以当其中一个变化,另一个的值也会进行相应的变化。

    绝命生
  • HDOJ(HDU) 2109 Fighting for HDU(简单排序比较)

    Problem Description 在上一回,我们让你猜测海东集团用地的形状,你猜对了吗?不管结果如何,都没关系,下面我继续向大家讲解海东集团的发展情况...

    谙忆
  • 经典笔试题-数据结构、算法及计算机基础篇

    181、常用UNIX 命令(Linux 的常用命令)(至少10 个)【基础】 答:ls pwd mkdir rm cp mv cd ps ftp telnet...

    cwl_java
  • 项目需求讨论- 自定义圆形排版的ViewGroup来构成动态弹框菜单

    大家好,又到了新的一次需求分析,这次我们的需求是:在不同的条件的前提下,点击一个菜单按钮,出来不同的菜单。

    青蛙要fly

扫码关注云+社区

领取腾讯云代金券