小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Computer & DL
  4. Data Structure
  5. 正文

数据结构【浙江大学】(第9节)整理

2018年5月12日 1543点热度 0人点赞 0条评论

第九节:排序(上)

9.1 概述

对于之后应用到的一些说明:

(1)void X_Sort(ElementType A[], int N) X为排序名称。

①大多数情况下,为了简单起见,讨论从小到大的整数排序。

②默认N为正整数。

③只讨论基于比较的排序(>=<都是有定义的)。

④只讨论内部排序(一次性可以写入内存,然后只在内存里面的数据排序)。

⑤稳定性:任意两个相等的数据,排序前后的相对位置不发生改变。

没有一种排序是任何情况下都表现最好的!!!

9.2 简单排序算法

9.2.1 冒泡排序

在一次排序完成后,最后面的一定是最大的,第二次排序的时候只需要对前N-1个排序即可,然后N-2……一直到最后完成。

冒泡排序的伪码描述如下:

void Bubble_Sort(ElementType A[], int N)
{
       for(P=N-1;P>=0;P--)
       {
              flag = 0;
              for(i=0;i<P;i++)
              {/*一趟冒泡*/
                     if(A[i]>A[i+1])
                     {
                            Swap(A[i],A[i+1);]
                            flag = 1;/*标志发生了交换*/
                     }
              }
              if(flag==0)
                     break;/*全程无交换,已经排好*/
       }
}

最好情况:顺序T=O(N);最差情况:逆序T=O(N2)

这个算法具有稳定性!

9.2.2 插入排序

类似于打扑克的时候拿到牌之后进行排序 。

源代码:

void InsertionSort( ElementType A[], int N )
{ /* 插入排序 */
     int P, i;
     ElementType Tmp;
     
     for ( P=1; P<N; P++ ) {
         Tmp = A[P]; /* 取出未排序序列中的第一个元素*/
         for ( i=P; i>0 && A[i-1]>Tmp; i-- )
             A[i] = A[i-1]; /*依次与已排序序列中元素比较并右移*/
         A[i] = Tmp; /* 放进合适的位置 */
     }
}

最好情况:顺序T=O(N)

最坏情况:逆序T=O (N2)

此方法也具有稳定性。

举例,问序列{34,8,64,51,32,21}中用插入排序和冒泡排序分别需要交换多少次?

答:冒泡法:9次;插入法,9次。

    它们的次数相等,是巧合还是必然?见下一节。

9.2.3 时间复杂度下界

1.逆序对

对于下标i<j,如果A[i]>A[j],则称(i,j)是一对逆序对(inversion)。

我们来看上一节中最后的序列{34,8,64,51,32,21},它里面有多少逆序对呢?

(34,8)(34,42)(34,21)(64,51)(64,21)(64,21)(51,32)(51,21)(32,21)

一共9个逆序对。这说明,前面两种算法,交换2个相邻元素正好消去1个逆序对!

插入排序时间复杂度:T(N,I)=O(N+I)。这里面N是元素个数,I是逆序对个数。这个可以这样理解,时间复杂度最低为元素个数N,即逆序对为0,也就是顺序排列情况下;然后随着多一个逆序对,复杂度加1。

如果序列基本有序,那么插入排序简单且高效。

2.定理1:任意N个不同元素组成的序列平均具有N(N-1)/4个逆序对。

3.定理2:任何仅以交换相邻两元素来排序的算法,其平均时间复杂度为Ω(N2)。(注意:Ω是下界,O是上界)

    这意味着,要提高算法效率,我们必须:每次消去不止1个逆序对!每次交换相隔较远的2个元素!

9.3 希尔排序

1.简单举例

它利用了插入排序的简单,同时克服了交换每次只交换相邻两个元素的缺点。

用下面这个序列来进行希尔排序的举例:

81

94

11

96

12

35

17

95

28

58

41

75

15

(1)首先以每5个元素取一个的规律进行排序:这里取了81、35、41。用插入排序对其进行排序:

35

94

11

96

12

41

17

95

28

58

81

75

15

然后取94、17、75进行插入排序,得到下面的结果:

35

17

11

96

12

41

75

95

28

58

81

94

15

然后考虑11、95、15,得到下面结果:

35

17

11

96

12

41

75

15

28

58

81

94

95

然后考虑96、28,得到下面结果:

35

17

11

28

12

41

75

15

96

58

81

94

95

然后考虑12和58:

35

17

11

28

12

41

75

15

96

58

81

94

95

(2)再用每3个元素取一个的规律进行排序:这里取35、28、75、58、95,结果如下:

28

12

11

35

15

41

58

17

94

75

81

96

95

(3)再做1间隔排序(即普通插入排序)。我们可以发现,此时整个序列已经基本有序,所以此时插入排序简单高效。

11

12

15

17

28

35

41

58

75

81

94

95

96

该算法的步骤:

①.定义增量序列DM>DM-1>…>D1=1

②对每个Dk进行“Dk-间隔”排序。

注意:“Dk-间隔”有序的序列,在执行“Dk-1-间隔”排序后,仍然是“Dk-间隔”有序的。

2.希尔增量序列

(1)原始希尔排序:DM=[N/2],Dk=[Dk+1/2]。其中,[]代表取整。

伪代码如下:

void Shell_Sort(ElementType A[], int N)
{
       for(D=N/2;D>0;D/=2)
       {
               for(P=D;P<N;P++)
               {
                      Tmp= A[P];
                      for(i=P;i>=D&&A[i-D]>Tmp;i-=D)
                             A[i]=A[i-D];
                      A[i]=Tmp;
               }
       }
}

最坏情况:T=θ(N2)(θ代表即使上界也是下界,即可以达到的值)

这种情况即,增量元素不互质,则小增量可能根本不起作用。

3.其它增量序列

(1)Hibbard增量序列:Dk=2k-1(相邻元素互质)。最坏情况:T=θ(N3/2),猜想Tavg=O(N5/4)。

(2)Sedgewick增量序列:{1,5,19,41,109}(9×4i-9×2i+1或4i-3×2i+1),猜想Tavg=O(N7/6),Tworst=O(N4/3)。

4.稳定性:不稳定。

9.4 堆排序

9.4.1 选择排序

void Selection_Sort(ElementType A[], int N)
{
       for(i=0;i<N;i++)
       {
              MinPosition = ScanForMin(A, i N-1);
              /*从A[i]到A[N-1]中找最小元,并将其位置赋给MinPosition*/
              Swap(A[i], A[MinPosition]);
              /*将未排序部分的最小元换到有序部份的最后位置*/
       }
}

无论如何,T=θ(N2)。

如何快速寻找到最小元?见下一节。

9.4.2 堆排序(选择排序的改进)

1.算法1:

void Heap_Sort ( ElementType A[], int N )
{
       BuildHeap(A); /*调整为最小堆,复杂度为O(N) */
       for ( i=0; i<N; i++ )
              TmpA[i] = DeleteMin(A); /*以此把最小元弹出来放到这个临时数组中*/
/*复杂度为O(logN) */
       for ( i=0; i<N; i++ )/* O(N) */
              A[i] = TmpA[i];/*把临时数组的数组返回原来的数组*/
}

时间复杂度:T(N)=O(NlogN)

缺点:需要额外O(N)空间,并且复制元素需要时间。

2.算法2:

注意,在堆排序里面的这个堆,元素是从0的位置开始的;原来学堆的时候,0是用来放哨兵的。

    因此,在堆排序中,元素下标从0开始。则对于下标为i的元素,其左、右孩子的下标分别为:2i+1, 2i+2。

    伪码描述如下:

void Heap_Sort ( ElementType A[], int N )
{
       for ( i=N/2-1; i>=0; i-- )/* BuildHeap */
              PercDown( A, i, N );
       for ( i=N-1; i>0; i-- ) {
              Swap( &A[0], &A[i] ); /* DeleteMax */
              PercDown( A, 0, i );
       }
}

定理:堆排序处理N个不同元素的随机排列的平均比较次数是2NlogN-O(Nlog logN)。

注意:虽然堆排序给出最佳平均时间复杂度,但实际效果不如用Sedgewick增量序列的希尔排序。

整体C语言源代码:

void Swap( ElementType *a, ElementType *b )
{
     ElementType t = *a; *a = *b; *b = t;
}
 
void PercDown( ElementType A[], int p, int N )
{ /* 改编代码4.24的PercDown( MaxHeap H, int p )    */
  /* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
    int Parent, Child;
    ElementType X;
 
    X = A[p]; /* 取出根结点存放的值 */
    for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
        Child = Parent * 2 + 1;
        if( (Child!=N-1) && (A[Child]<A[Child+1]) )
            Child++;  /* Child指向左右子结点的较大者 */
        if( X >= A[Child] ) break; /* 找到了合适位置 */
        else  /* 下滤X */
            A[Parent] = A[Child];
    }
    A[Parent] = X;
}
 
void HeapSort( ElementType A[], int N )
{ /* 堆排序 */
     int i;
      
     for ( i=N/2-1; i>=0; i-- )/* 建立最大堆 */
         PercDown( A, i, N );
     
     for ( i=N-1; i>0; i-- ) {
         /* 删除最大堆顶 */
         Swap( &A[0], &A[i] ); /* 见代码7.1 */
         PercDown( A, 0, i );
     }
}

9.5 归并排序

9.5 1有序子列的归并

1.举例:假设我们有两个有序序列如下:

1

13

24

26

 

2

15

27

38

我们要将它们合并成一个序列并按照顺序排序。我们需要设置三个指针,如图1所示。Aptr指向A序列的第一个元素(1),Bptr指向B序列的第一个元素(2),Cptr指向合并后的第一个元素。这里的指针其实是三个整数,分别存储的三个元素的下标。首先比较Aptr和Bptr指向的元素那个比较小,选择比较小的放入Cptr所代表的下标的那个位置。然后将Aptr加1,Cptr加1,用Bptr所代表的的下标的元素和Aptr所代表的的下标的元素比较,发现Bptr下标的元素(2)小,将2存入Cptr代表下标的元素,即C[Cptr]。然后依次类推。

 1.jpg

图1

时间复杂度T(N)=O(N)。

伪代码描述如下:

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置 */
void Merge( ElementType A[], ElementType TmpA[],
            int L, int R, int RightEnd )
{
       LeftEnd = R - 1; /* 左边终点位置。假设左右两列挨着 */
       Tmp = L; /* 存放结果的数组的初始位置 */
       NumElements = RightEnd - L + 1;
       while( L <= LeftEnd && R <= RightEnd )
       {
              if( A[L] <= A[R] )
                     TmpA[Tmp++] = A[L++];
              else TmpA[Tmp++] = A[R++];
       }
       while( L <= LeftEnd ) /* 直接复制左边剩下的 */
              TmpA[Tmp++] = A[L++];
       while( R <= RightEnd ) /*直接复制右边剩下的 */
              TmpA[Tmp++] = A[R++];
       for(i=0;i<NumElements;i++,RightEnd--)
              A[RightEnd] = TmpA[RightEnd];
}

9.5.2递归算法

1.分而治之

如图2所示,该算法是稳定的。

2.jpg 

图2

伪码描述如下:

void MSort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{
       int Center;
       if ( L < RightEnd ) {
              Center = ( L + RightEnd ) / 2;
              MSort( A, TmpA, L, Center );
              MSort( A, TmpA, Center+1, RightEnd );
              Merge( A, TmpA, L, Center+1, RightEnd );
       }
}

    时间复杂度为:T(N)=T(N/2)+T(N/2)+O(N),即T(N)=O(NlogN)。

2.统一函数接口

为了与前面的函数接口统一,因此我们需要再写一个函数来统一函数接口。其伪码描述如下:

void Merge_sort( ElementType A[], int N )
{
       ElementType *TmpA;
       TmpA = malloc( N * sizeof( ElementType ) );
       if ( TmpA != NULL )
       {
              MSort( A, TmpA, 0, N-1 );
              free( TmpA );
       }
       else Error( “空间不足" );
}

如果只在Merge中声明临时数组,那么两个子函数声明如下:

void Merge( ElementType A[], int L, int R, int RightEnd )

void MSort( ElementType A[], int L, int RightEnd )

    这样也不是不行,但是这样的话,每一次在子函数里面用一次释放一次,增加了时间复杂度,还不如直接在最外层的代码里面定义好。

整体的源代码实现如下:

/* 归并排序 - 递归实现 */
 
/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
     int LeftEnd, NumElements, Tmp;
     int i;
     
     LeftEnd = R - 1; /* 左边终点位置 */
     Tmp = L;         /* 有序序列的起始位置 */
     NumElements = RightEnd - L + 1;
     
     while( L <= LeftEnd && R <= RightEnd ) {
         if ( A[L] <= A[R] )
             TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
         else
             TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
     }
 
     while( L <= LeftEnd )
         TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
     while( R <= RightEnd )
         TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
         
     for( i = 0; i < NumElements; i++, RightEnd -- )
         A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}
 
void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{ /* 核心递归排序函数 */
     int Center;
     
     if ( L < RightEnd ) {
          Center = (L+RightEnd) / 2;
          Msort( A, TmpA, L, Center );              /* 递归解决左边 */
          Msort( A, TmpA, Center+1, RightEnd );     /* 递归解决右边 */ 
          Merge( A, TmpA, L, Center+1, RightEnd );  /* 合并两段有序序列 */
     }
}
 
void MergeSort( ElementType A[], int N )
{ /* 归并排序 */
     ElementType *TmpA;
     TmpA = (ElementType *)malloc(N*sizeof(ElementType));
     
     if ( TmpA != NULL ) {
          Msort( A, TmpA, 0, N-1 );
          free( TmpA );
     }
     else printf( "空间不足" );
}

9.5.3 非递归算法

非递归算法的图示如图3所示。

1526113355712562.jpg 

图3

额外空间复杂度是O(N)。我们只需要开一个临时数组就可以了,没必要每次都开一个。

其伪码描述如下:

void Merge_pass( ElementType A[], ElementType TmpA[], int N,int length )
 /* length = 当前有序子列的长度*/
{
       for ( i=0; i <= N–2*length; i += 2*length )
              Merge1( A, TmpA, i, i+length, i+2*length–1 );
       if ( i+length < N ) /* 归并最后2个子列*/
              Merge1( A, TmpA, i, i+length, N–1);
       else /* 最后只剩1个子列*/
       for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}

统一接口如下:

void Merge_sort( ElementType A[], int N )
{
       int length = 1; /* 初始化子序列长度*/
       ElementType *TmpA;
       TmpA = malloc( N * sizeof( ElementType ) );
       if ( TmpA != NULL ) {
              while( length < N ) {
                     Merge_pass( A, TmpA, N, length );
                     length *= 2;
                     Merge_pass( TmpA, A, N, length );
                     length *= 2;
              }
              free( TmpA );
       }
       else Error( “空间不足" );
}

具有稳定性!

缺点是需要额外空间之类的~此方法主要用在外排序。

C语言实现源代码:

/* 归并排序 - 循环实现 */
/* 这里Merge函数在递归版本中给出 */
 
/* length = 当前有序子列的长度*/
void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length )
{ /* 两两归并相邻有序子列 */
     int i, j;
      
     for ( i=0; i <= N-2*length; i += 2*length )
         Merge( A, TmpA, i, i+length, i+2*length-1 );
     if ( i+length < N ) /* 归并最后2个子列*/
         Merge( A, TmpA, i, i+length, N-1);
     else /* 最后只剩1个子列*/
         for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}
 
void Merge_Sort( ElementType A[], int N )
{
     int length;
     ElementType *TmpA;
     
     length = 1; /* 初始化子序列长度*/
     TmpA = malloc( N * sizeof( ElementType ) );
     if ( TmpA != NULL ) {
          while( length < N ) {
              Merge_pass( A, TmpA, N, length );
              length *= 2;
              Merge_pass( TmpA, A, N, length );
              length *= 2;
          }
          free( TmpA );
     }
     else printf( "空间不足" );
}

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 数据结构
最后更新:2018年5月12日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
[leetcode]populating next right pointers in each node altium designer常用元件电气符号和封装形式(转) 吴恩达深度学习课程 DeepLearning.ai 编程作业(1-2)Part.2 C++面向对象程序设计课程笔记(第一周) Leetcode题目解析(191021) 南京青奥之行行程表
标签聚合
学习 算法 高中 鸟哥的linux私房菜 生活 linux leetcode Java Python python学习
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号