Scott's world.

第九讲-排序-上

数据结构 浙江大学
Word count: 1kReading time: 5 min
2019/08/14 Share

第九讲 排序（上）

简单排序

前提

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//伪代码
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(N^2)

稳定

插入排序

1
2
3
4
5
6
7
8
9
10
void Insertion_Sort (ElementType A[],int N)
{
    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(N^2)

稳定

时间复杂度下界

  • 定理:任意N个不同元素组成的序列平均具有N(N-1)/4个逆序对
  • 定理:任何仅以交换相邻两元素来排序的算法,其平均时间复杂度为Ω(N^2)

意味着:要提高算法效率,我们必须

  • 每次消去不止1个逆序对
  • 每次交换相隔较远的2个元素

希尔排序

希尔增量序列

  • 原始希尔排序 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void Sheel_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=Θ(N^2)

    增量元素不互质,则小增量可能根本不起作用

更多增量序列

  • Hibbard增量序列

  • Sedgewick增量序列

堆排序

选择排序

1
2
3
4
5
6
7
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=Θ(N^2)

堆排序

  • 算法1

    1
    2
    3
    4
    5
    6
    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++)A[i]=TmpA[i];//O(N)
    }

    T(N)=O(NlogN)

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

  • 算法2

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    void Heap_Sort(ElementType A[],int N)
    {
        for(i=N/2;i>=0;i--)
            PercDown(A,i,N); //BuildHeap
        for(i=N-1;i>0;i--){
            Swap(&A[0],&A[i]); //DeleteMax
            PercDown(A,0,i);
        }
    }

    void Swap(ElementType *a,ElementType *b)
    {
        ElementType t=*a;*a=*b;*b=t;
        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++;
            if(X>=A[Child]) break;
            
           else  A[Parent]=A[Child];
        }
        A[Parent]=X;
    }

    void PrecDown(ElementType A[],int p,int N)
    {
        
    }

归并排序

有序子列的归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Merge(ElementType A[],ElementType TmpA[],int L,int R,int RightEnd)
{
     LeftEnd=R-1;
    Tmp=L;
    NumElements=RightEnd-L+1;
    while(L<=Left&&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<NumElemnts;i++,RightEnd--)
        A[RightEnd]=TmpA[RightEnd];
}

递归算法

  • 分而治之

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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)=O(NlogN)

    稳定

  • 统一函数接口

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void Merge_sort(ElementType A[],itn N)
    {
        ElementType *TmpA;
        TmpA=malloc(N*sizeof(ElementType));
        if(TmpA!=NULL){
            MSort(A,TmpA,0,N-1);
            free(TmpA);
        }
        else Error("空间不足");
    }

    若用临时数组的话,会浪费很大部分空间

非递归算法

额外空间复杂度是O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/* 归并排序 - 循环实现 */
/* 这里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( "空间不足" );
}
CATALOG
  1. 1. 第九讲 排序（上）
    1. 1.1. 简单排序
      1. 1.1.1. 前提
      2. 1.1.2. 冒泡排序
      3. 1.1.3. 插入排序
      4. 1.1.4. 时间复杂度下界
    2. 1.2. 希尔排序
      1. 1.2.1. 希尔增量序列
      2. 1.2.2. 更多增量序列
    3. 1.3. 堆排序
      1. 1.3.1. 选择排序
      2. 1.3.2. 堆排序
    4. 1.4. 归并排序
      1. 1.4.1. 有序子列的归并
      2. 1.4.2. 递归算法
      3. 1.4.3. 非递归算法
Total : 117
2020
2019
数据结构 C 计算机网络 快捷键 算法 编程练习题 链表 MySQL redis NoSQL 线性结构 Linux machine learning 吴恩达教授 golang 书单 杂谈 浙江大学 深入理解计算机系统 读书笔记 设计模式 创造型模式 创建型模式 “golang" 项目反思 操作系统 排序 缓存策略 行为型模式 微服务 蓝桥杯 指针 matlab
编程练习题 C 计算机网络 杂记 算法 MySQL redis Linux machine-learning golang 书单 随记 数据结构 计算机系统 设计模式 项目反思 微服务 matlab