我是靠谱客的博主 兴奋寒风,最近开发中收集的这篇文章主要介绍数据结构与算法分析——第七章 排序,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

注:发此文谨以记录初学《数据结构与算法分析——C语言描述》的个人理解,希望能够得到宝贵意见与建议。(文中转载有相关文章片段,在学习时帮助理解作用较大,在此对作者表示感谢)

7.1 预备知识

     1,算法接收 含元素的数组和包含元素个数的整数

     2,基于比较的排序

7.2 插入排序

     代码实现

​
void InsertionSort(ElementType A[],int N)
{
    int i,j;
    ElementType Tmp;
    for(i = 1 ; i < N ; i++)
    {
        Tmp = A[i];
        for(j = i ; j > 0 && A[j - 1] > Tmp ; j--)
        {
            A[j] = A[j - 1];
        }
        A[j] = Tmp;//避免明显使用交换
    }
}

​

理解描述

  位置i上元素存于Tmp中,i之前所有更大的元素向右移一位(i前所有元素已排序),Tmp被置于正确位置。

  分析

  1,(未排序)嵌套循环每个花费N次迭代,为O(N^2)

  2,(已排序)为O(N)

  *由于差距较大,故值得分析平均情形

 

7.3 一些简单排序算法的下界

  1,怎样概括“一些”的共性?       

       引入逆序 —— 插排交换次数=逆序数(O(N) <=> O(N + I),N:其他工作,I:逆序数)—— 平均运行时间 <=> 平均逆序数

       * 以插排为例分析(插排 代表 通过交换相邻元素进行排序的算法),得出共性
 

  2,结论

     定理7.1  N个互异数的数组的平均逆序数是N(N-1)/4

  定理7.2  通过交换相邻元素进行排序的任何算法平均需要Ω(N^2)时间

7.4 希尔排序

  代码实现

void ShellSort(ElementType A[],int N)
{
    int i,j,Increment;
    ElementType Tmp;
    for(Increment = N / 2 ; Increment > 0 ; Increment /= 2)
    {
        for(i = Increment ; i < N ; i++)//小型插排
        {
            Tmp = A[i];
            for(j = i ; j >= Increment && A[j - Increment] > Tmp ; j -= Increment)
            {
                A[j] = A[j - Increment];
            }
            A[j] = Tmp;
        }
    }
}

理解描述

  不断缩小增量的插入排序,通过远距离交换以达到一次消除多对逆序(需保证增量变换时不干扰已处理的顺序),减小每一趟工作量,即亚二次运行时间。

  分析

  定理7.3  使用希尔增量的希尔排序的最坏运行时间为Θ(N^2)

  定理7.4  使用 Hibbard 增量的希尔排序的最坏运行时间为Θ(N^2)  (Hibbard增量形如 1,3,7,...,2^k - 1)

7.5 堆排序

  代码实现

#define LeftChild(i) (2 * (i) + 1)//下标从0开始,因此为 2*i+1
void PercDown(ElementType A[],int i,int N)
{
    int Child;
    ElementType Tmp;
    for(Tmp = A[i] ; LeftChild(i) < N ; i = Child)//下标从0开始,注意边界
    {
        Child = LeftChild(i);
        if(Child != N - 1 && A[Child + 1] > A[Child])//Child != N - 1 即右边还有数据
        {
            Child++;//选出较大的儿子
        }
        if(Tmp < A[Child])
        {
            A[i] = A[Child];
        }
        else
        {
            break;
        }
    }
    A[i] = Tmp;
}
void HeapSort(ElementType A[] , int N)
{
    int i;
    //BuildHeap
    for(i = N / 2 ; i >= 0 ; i--)//从右向左,从下向上,逐步下滤
    {
        PercDown(A,i,N);
    }
    //DeleteMax
    for(i = N - 1 ; i > 0 ; i--)
    {
        Swap(&A[0] , &A[i]);
        PercDown(A , 0 , i);//位置0处元素下滤,且元素个数改变
    }
}

上图为构建初始堆及排序过程,数组中表,97.58,31,26,41,58,31  

  理解描述

  1,对已有数组元素进行整理,构建max堆(max堆便于实施从小到大排序)

  2,排序时通过回收利用空间,避免使用第二个数组

  分析

  定理7.5  对N个互异项的随机排列进行堆排序,所用的平均比较次数为 2NlogN - O(NlogN)

7.6归并排序

  代码实现

void MergeSort(ElementType A[],int N)//驱动例程
{
    ElementType *TmpArray;
    TmpArray = malloc(N * sizeof(ElementType));
    if(TmpArray != NULL)
    {
        MSort(A,TmpArray,0,N - 1);
        free(TmpArray);
    }
    else
    {
        FatalError("No space for tmp array");
    }
}
void MSort(ElementType A[],ElementType TmpArray[],int Left,int Right)
{
    int Center;
    if(Left < Right)//条件成立时再对Center赋值
    {
        Center = (Left + Right) / 2;
        MSort(A , TmpArray , Left , Center);
        MSort(A , TmpArray , Center + 1 , Right);
        Merge(A , TmpArray , Left , Center + 1 , Right);//Center + 1 即右半部分始位置
    }
}
void Merge(ElementType A[] , ElementType TmpArray[] , int Lpos , int Rpos , int RightEnd)
{
    int i , LeftEnd , TmpPos , NumElements;
    //NumElements 存放每次排序时元素总数(临时数组元素转移至原数组时使用)
    //TmpPos 记录排序元素在新建数组中*对应*位置
    
    LeftEnd = Rpos - 1;
    NumElements = RightEnd - Lpos;
    TmpPos = Lpos;
    
    while(Lpos < LeftEnd && Rpos < RightEnd)
    {
        if(A[Lpos] < A[Rpos])
        {
            TmpArray[TmpPos++] = A[Lpos++];
        }
        else
        {
            TmpArray[TmpPos++] = A[Rpos++];
        }
    }
    
    //Copy rest of each half
    while(Lpos <= LeftEnd)
    {
        TmpArray[TmpPos++] = A[Lpos++];
    }
    while(Rpos <= RightEnd)
    {
        TmpArray[TmpPos++] = A[Rpos++];
    }
    
    for(i = 0 ; i < NumElements ; i++ , RightEnd--)
    {
        A[RightEnd] = TmpArray[RightEnd];
    }
}

理解描述

  1,递归是怎样实施的?

  答:以8个元素为例,左右各分成4 个元素,先处理左边4 个,将左边4个元素重复分隔,直到左边只剩一个元素,达到基准条件,返回最近主程序中,处理右边一个元素,达到基准条件,进行合并,此时这两个元素作为左侧,返回最近主程序中,处理右边两个元素,继续先左后右,处理合并,返回最近主程序中,进行合并。此时总体来看,8个元素,左侧4个已实施“分治”,接下来继续进行递推,过程类似。

  2,小块元素合并后怎样存放?

  答:小块元素在临时数组*对应位置*进行合并存放,排序后依次放入原数组中,不影响后面元素及其排序。

  分析 

  运行时间:T(N) = O(NlogN)

  应用:很难用于主存排序。首先,合并两个线性表需要线性附加内存,其次,数据在数组间拷贝需要时间。 

7.7 快速排序

  代码实现

//驱动例程
void QuickSort(ElementType A[] , int N)
{
    QSort(A , 0 , N - 1);
}

//选取枢纽元
//对三元素排序,最值放两边,枢纽元置于 right-1 处(此方法便于设置警戒标志,防止越界)
ElementType Median3(ElementType A[] , Left , Right)
{
    int Center;
    Center = (Left + Right) / 2;
    if(A[Left] > A[Center])
    {
        Swap(&A[Left] , &A[Center]);
    }
    if(A[Left] > A[Right])
    {
        Swap(&A[Left] , &A[Right]);
    }
    if(A[Center] > A[Right])
    {
        Swap(&A[Center] , &A[Right]);
    }
    Swap(&A[Center] , &A[Right - 1]);
    return A[Right - 1];
}

#define Cutoff (3)
void QSort(ElementType A[] , int Left , int Right)
{
    int i , j;
    ElementType Pivot;
    if(Left + Cutoff <= Right)//数组内大于3个元素时,分割加递归
    {
        Pivot = Median3(A , Left , Right);
        i = Left;//因为下方使用的是前自增
        j = Right - 1;
        for( ; ; )
        {
            while(A[++i] < Pivot){}
            while(A[--j] > Pivot){}
            if(i < j)
            {
                Swap(&A[i],&A[j]);
            }
            else
            {
                break;
            }
        }
        Swap(&A[i],&A[Right - 1]);//Restore pivot
        QSort(A , Left , i - 1);
        QSort(A , i + 1 , Right);
    }
    else
    {
       InsertionSort(A + Left , Right - Left + 1); 
    }
}

理解描述

  与归并排序类似,区别是选取枢纽元,以枢纽元为界分割为大小两数组。(适用于大数组)

  选取枢纽元:随机选取;三数中值分割法(左,右,中心位置里的中值,同时将三元素排序,便于设置警戒标志,防止越界)

  分割策略:1,枢纽元与位置right - 1处元素互换

          2,设置i(left),j(right - 1),i 向右滑动直至 i 处元素 >= 枢纽元,j 向左滑动直至 j 处元素 <= 枢纽元,交换i,j处元素

          3,i,j交错时,i 处元素与枢纽元交换

  分析

  最坏情况分析:枢纽元始终为最小元素,T(N) = O(N^2)

  最好情况分析:枢纽元位于中间,T(N) = O(NlogN)

  平均情况分析:每个文件大小等可能,求出平均分布,T(N) = O(NlogN)

  扩展(选择问题的线性期望时间算法)

  选择问题:查找集合S中第k个最小元

  与快速排序类似,区别在于分割后,若 k <= |S1|,则返回quickselect( S1 , k ),若k = |S1| + 1 ,则枢纽元即为所求,否则返回quickselect(S2 , k - |S1| - 1)

  代码实现

#define Cutoff (3)
void QuickSelect(ElementType A[] , int k , int N)
{
    QSelect(A , k , 0 , N - 1);
}

ElementType Median3(ElementType A[] , Left , Right)
{
    int Center;
    Center = (Left + Right) / 2;
    if(A[Left] > A[Center])
    {
        Swap(&A[Left] , &A[Center]);
    }
    if(A[Left] > A[Right])
    {
        Swap(&A[Left] , &A[Right]);
    }
    if(A[Center] > A[Right])
    {
        Swap(&A[Center] , &A[Right]);
    }
    Swap(&A[Center] , &A[Right - 1]);
    return A[Right - 1];
}

//位置k - 1处即为第k个最小值
void QSelect(ElementType A[] , int k , int Left , int Right)
{
    int i , j;
    ElementType Pivot;
    if(Left + Cutoff <= Right)
    {
        Pivot = Median3(A , Left , Right);
        i = Left;
        j = Right - 1;
        for( ; ; )
        {
            while(A[++i] < Pivot){}
            while(A[--j] > Pivot){}
            if(i < j)
            {
                Swap(&A[i],&A[j]);
            }
            else
            {
                break;
            }
        }
        Swap(&A[i],&A[Right - 1]);//Restore pivot
        if(k <= i)
        {
            QSelect(A , k , Left , i - 1);
        }
        else if(k > i + 1)
        {
            QSelect(A , k - i - 1 , i + 1 , Right);
        }
    }
    else
    {
       InsertionSort(A + Left , Right - Left + 1);
    }
}

7.8 大型结构的排序

  排序时交换整个结构代价是昂贵的,解决办法是让输入数组包含指向结构的指针,通过指针比较关键字,必要时交换指针来进行排序。

7.9 排序的一般下界

  引入决策树,通过只使用比较进行排序的每一种算法都可以用决策树表示。

  引理7.1:令T是深度为d的二叉树,则T最多有2^d个树叶

  引理7.2:具有L片树叶的二叉树深度至少是[ logL ]

  定理7.6:只使用元素间比较的任何排序算法在最坏情况下至少需要[ log( N! ) ]次比较

  定理7.7:只使用元素间比较的任何排序算法需要进行Ω(NlogN)次比较

7.10 桶式排序

  以线性时间进行排序,构建数组,大小包含所有待排元素,初始为0,元素出现以1代替。

7.11 外部排序

  简单算法(该部分内容转自@Judy518)——二路合并

  例如要对外存中4500个记录进行归并,而内存大小只能容纳750个记录,在第一阶段,我们可以每次读取750个记录进行排序,这样可以分六次读取,进行排序,可以得到六 个有序的归并段,如下图:

  

每个归并段的大小是750个记录,记住,这些归并段已经全部写到临时缓冲区(由一个可用的磁盘充当)内了,这是第一步的排序结果。

1、将内存空间划分为三份,每份大小250个记录,其中两个用作输入缓冲区,另外一个用作输出缓冲区。首先对Segment_1和Segment_2进行归并,先从每个归并段中读取250个记录到输入缓冲区,对其归并,归并结果放到输出缓冲区,当输出缓冲区满后,将其写道临时缓冲区内,如果某个输入缓冲区空了,则从相应的归并段中再读取250个记录进行继续归并,反复以上步骤,直至Segment_1和Segment_2全都排好序,形成一个大小为1500的记录,然后对Segment_3和Segment_4、Segment_5和Segment_6进行同样的操作。

2、对归并好的大小为1500的记录进行如同步骤1一样的操作,进行继续排序,直至最后形成大小为4500的归并段,至此,排序结束。

  多路合并

  1,2-路合并扩充为k-路合并,区别在于寻找k个元素中最小元过程稍微复杂,可通过优先队列寻找最小元,进行DeleteMin操作,得到下一个写到磁盘上的元素

  2,在初始顺串构造阶段之后,k-路合并所需趟数为[ logk( N / M ) ]。(N为数据总量,M为内存容量)

  多相合并

  k-路合并需要2k盘磁带,然而使用 k + 1 盘磁带也有可能完成排序工作,作为例子,这里阐述只用三盘磁带(T1,T2,T3)如何完成2-路合并。

  假设T1上有一个输入文件,它将产生34个顺串。

  选择一:每盘磁带存入17个,然后合并存放至T1,再将T1前个8顺串存至T2,再次合并存至T3,依次类推。这样每一趟合并附加额外半趟工作。

  选择二:将34个顺串不均衡地分成2份,例如21,13,再次进行合并。此时需考虑顺串最初的分配,事实上,若初始顺串为斐波那契数,则将其分裂为2个斐波那契数之和,否则需添加哑顺串填补磁带,将其补足为斐波那契数

  替换选择(该部分内容转自@kph_Hajash)  

  在标准的外排中,一次读入内存可容纳的 M 个记录,排序完依次输出到空磁带上;但这里其实有个小技巧,排完序后输出第一个记录到磁带上时,内存让出了一个记录的空间,这时我们可以从输入磁带取出一个记录,判断它是否大于刚输出的记录,若是,说明它可以放入当前顺串中(顺串是从小到大有序),否则,应暂存内存,等下一个顺串的构造; 这里暂存内存书上讲是放在最小堆的死区(dead space)。

初始顺串的构造详解,绿色箭头表示当前输入状态,Tbn 表示输出状态,内存缓冲表示当前内存中存在的记录(括号内记录表示存在最小堆的死区) 
这里写图片描述
从上图可知,与标准顺串构造方式生成的 5 个顺串相比,替换选择构造的初始顺串记录数更多,顺串数更少,只有 3 个,且前者需要 12 趟完成排序,替换选择只需 3 趟。

最后

以上就是兴奋寒风为你收集整理的数据结构与算法分析——第七章 排序的全部内容,希望文章能够帮你解决数据结构与算法分析——第七章 排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(56)

评论列表共有 0 条评论

立即
投稿
返回
顶部