跳转至

排序

我们假设 "<" ">" 运算符存在,这两种运算是仅有的允许对输入数据进行的操作,这称为基于比较的排序. 我们假定 N 为要排序的元素个数,数据从位置 0 开始。

插入排序

插入排序有 N-1 趟(pass), 对于 \(P=1\)\(P=N-1\) 趟我们保证位置 0 到位置 \(P-1\) 上的元素是已经排序好的,而第 \(P\) 趟要做的就是将位置 \(P\) 的元素向左移动到它在前 \(P+1\) 个元素中的正确位置上。

void InsertionSort ( ElementType A[ ], int N ) 
{ 
    int j, P; 
    ElementType  Tmp; 

    for ( P = 1; P < N; P++ ) { 
    Tmp = A[ P ];  /* the next coming card */
    for ( j = P; j > 0 && A[ j - 1 ] > Tmp; j-- ) 
          A[ j ] = A[ j - 1 ]; 
          /* shift sorted cards to provide a position 
                       for the new coming card */
    A[ j ] = Tmp;  /* place the new card at the proper position */
      }  /* end for-P-loop */
}
  • 最佳情况 - 输入数据是已经排好序的,那么运行时间为 \(O(N)\)
  • 最坏情况 - 输入数据是逆序的,那么运行时间为 \(O(N^2)\)

简单排序算法的下界

一个逆序是指数组中 \(i<j\)\(A[i]>A[j]\) 的序偶 \((A[i],A[j])\)

交换不按原序排列的相邻元素会恰好消除一个逆序,因此插入排序的运行时间为 \(O(I+N)\). 其中 \(I\) 为原始数组中的逆序数,当逆序数较少时插入排序以线性时间运行。

\(N\) 个互异数的数组的平均逆序数为 \(\dfrac{N(N-1)}{4}\)

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

希尔排序

希尔排序使用一个 \(h_1,h_2,\ldots,h_t\)增量序列(\(h_1=1\)).
\(h_k\)-sort 的一般做法是,对于 \(h_k,h_k+1,\ldots,N-1\) 中的每一个位置 \(i\), 将其元素放到 \(i,i-h_k,i-2h_k,\ldots\) 中间的正确位置上。相当于对 \(h_k\) 个独立的子数组各进行一次插入排序。\(h_k\)-sort 之后,对于每一个 \(i\) 我们都有 \(a_i\leq a_{i+h_k}\), 此时成称为 \(h_k\)-sorted.

希尔排序的一个重要性质: 一个 \(h_k\)-sorted 的文件(此后将是 \(h_{k-1}\)-sorted)保持他的 \(h_k\)-sorted 性质。

希尔增量序列

\(h_t=\lfloor N/2 \rfloor, h_k=\lfloor h_{k+1}/2 \rfloor\)(可以有更好的增量序列)

void Shellsort( ElementType A[ ], int N ) 
{ 
      int  i, j, Increment; 
      ElementType  Tmp; 
      for ( Increment = N / 2; Increment > 0; Increment /= 2 )  
    /*h sequence */
    for ( i = Increment; i < N; i++ ) { /* insertion sort */
          Tmp = A[ i ]; 
          for ( j = i; j >= Increment; j - = Increment ) 
        if( Tmp < A[ j - Increment ] ) 
              A[ j ] = A[ j - Increment ]; 
        else 
              break; 
        A[ j ] = Tmp; 
    } /* end for-I and for-Increment loops */
}
  • 最坏情形分析

    使用希尔增量时的希尔排序的最坏情形运行时间为 \(\Theta(N^2)\)

  • Hibbard 增量序列
    \(h_k= 2^k-1\), 且其最坏情形下运行时间为 \(O(N^{3/2})\)

堆排序

如果我们先 BuildHeap, 再 Delete N 次最小元素,这样需要多使用一个附加数组,使得存储需求增加一倍。

每次 DeleteMin 后,堆的大小缩小了 1, 因此我们可以用堆中最后的单元来存放刚刚删去的元素。

整体流程:

  • 以线性时间建一个 Max 堆
  • 将堆中最后元素与第一个元素交换,缩减堆的大小并进行下滤。执行 N-1 次 DeleteMax 操作
  • 算法终止时,数组按顺序即为从小到大的排序结果
void Heapsort( ElementType A[ ], int N ) 
{  int i; 
    for ( i = N / 2; 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 ); 
    } 
}

注:这里的堆我们是从 0 开始计数的,因此左儿子应该是 2*i+1

对 N 个互异项的随机排列进行堆排序,平均比较次数为 \(2N\log N-O(N\log\log N)\)

归并排序

基本操作:合并两个已排序的表,我们可以用双指针的方法在线性时间内完成两个表的合并,具体操作如下

  • 取两个输入数组 A 和 B, 一个输出数组 C, 以及三个计数器 Aptr, Bptr, Cptr, 分别对应数组的开端。
  • 每次 A[Aptr]B[Bptr] 中的较小者会被拷贝到 C 中的下一个位置,,相关的计数器向前推进一步。
  • 当两个输入表中有一个用完时,将另一个表的剩余部分拷贝到 C 中。
  • 我们最多进行 \(N-1\) 次比较,因此合并时间显然是线性的。

因此归并排序的流程就是,如果 N=1 那么只有一个元素需要排序,答案是显然的;否则递归地将前半部分数据和后半部分数据各自归并排序,得到排序后的两部分数据,然后使用刚刚描述的合并操作将这两个部分合并到一起。

需要注意的是,如果我们每次递归调用 Merge 都局部声明一个临时数组,那么任意时刻就会有 \(\log N\) 个临时数组处于活动期,这对于小内存的机器是致命的。注意到 Merge 只在每次递归调用的最后一行,因此任何时刻只需要一个临时数组活动,而且可以使用该临时数组的任意部分,这样节约了空间。

void MSort( ElementType A[ ], ElementType TmpArray[ ], 
        int Left, int Right ) 
{   int  Center; 
    if ( Left < Right ) {  /* if there are elements to be sorted */
    Center = ( Left + Right ) / 2; 
    MSort( A, TmpArray, Left, Center );     /* T( N / 2 ) */
    MSort( A, TmpArray, Center + 1, Right );    /* T( N / 2 ) */
    Merge( A, TmpArray, Left, Center + 1, Right );  /* O( N ) */
    } 
} 

void Mergesort( ElementType A[ ], int N ) 
{   ElementType  *TmpArray;  /* need O(N) extra space */
    TmpArray = malloc( N * sizeof( ElementType ) ); 
    if ( TmpArray != NULL ) { 
    MSort( A, TmpArray, 0, N - 1 ); 
    free( TmpArray ); 
    } 
    else  FatalError( "No space for tmp array!!!" ); 
}
/* Lpos = start of left half, Rpos = start of right half */ 
void Merge( ElementType A[ ], ElementType TmpArray[ ], 
           int Lpos, int Rpos, int RightEnd ) 
{   int  i, LeftEnd, NumElements, TmpPos; 
    LeftEnd = Rpos - 1; 
    TmpPos = Lpos; 
    NumElements = RightEnd - Lpos + 1; 
    while( Lpos <= LeftEnd && Rpos <= RightEnd ) /* main loop */ 
        if ( A[ Lpos ] <= A[ Rpos ] ) 
    TmpArray[ TmpPos++ ] = A[ Lpos++ ]; 
        else 
    TmpArray[ TmpPos++ ] = A[ Rpos++ ]; 
    while( Lpos <= LeftEnd ) /* Copy rest of first half */ 
        TmpArray[ TmpPos++ ] = A[ Lpos++ ]; 
    while( Rpos <= RightEnd ) /* Copy rest of second half */ 
        TmpArray[ TmpPos++ ] = A[ Rpos++ ]; 
    for( i = 0; i < NumElements; i++, RightEnd - - ) 
         /* Copy TmpArray back */ 
        A[ RightEnd ] = TmpArray[ RightEnd ]; 
}
  • 运行时间分析
\[ \begin{align*} T(1) & = 1\\ T(N) & = 2T(N/2)+O(N) \\ & = 2^kT(N/2^k) + k*O(N)\\ & = N *T(1) +\log N *O(N)\\ & = O(N+N\log N) \end{align*} \]

注:Mergesort 需要线性外部内存,复制数组缓慢,因此不适合用于内部排序,但对于外部排序是有用的。

快速排序

快速排序是在实践中已知的最快的排序算法,平均运行时间是 \(O(N\log N)\)
快速排序的算法流程:(将数组 S 排序)

  • 如果 S 中的元素个数是 0 或者 1 则返回
  • 从 S 中取任意元素为主元
  • \(S-\{v\}\) 分为两个不相交的集合 \(S_1=\{x\in S-\{v\}|x\leq v\}, S_2=\{x\in S-\{v\}|x\geq v\}\)
  • 返回 \(quicksort(S_1), v, quicksort(S_2)\)

对于不同主元的选取,分割的描述不是唯一的。

选取主元

  • 错误的方法 Pivot=A[0]
    这样如果输入是顺序或者反序的,那么每次划分所有元素全部落入 \(S_1\) 或者 \(S_2\), 选取主元并没有带来任何帮助,完成排序需要 \(O(N^2)\) 的时间。
  • 安全做法 Pivot = random select from A[]
    但随机数的产生是昂贵的
  • 三数中值分割法 Pivot = median(left, center, right)
    一组 N 个数的中值是第 \(\lceil N/2 \rceil\) 大的数,主元最好是选择中值,但这很难算出,而且会明显减慢排序的速度。因此我们可以使用左端、右端和中心位置上的三个元素的中值作为主元。
    这样消除了错误方法中的最坏情形,减少了快速排序大概 5% 的运行时间。

划分策略

首先我们将主元和最后的元素交换,使得主元离开将要分割的数据段,随后 i 从第一个元素开始,j 从倒数第二个元素开始。(假设所有元素互异)

  • 当 i 在 j 的左边时,我们将 i 右移,移过那些小于主元的元素,并将 j 左移,移过那些大于主元的元素。
  • 当 i 和 j 停止时,i 指向一个大元素而 j 指向一个小元素,如果 i 在 j 的左边那么将这两个元素互换。
  • 直到 i 和 j 彼此交错时,停止交换
  • 将 i 和主元交换

对于那些等于主元的关键字,我们采用停止 i j 并交换的策略。因为若 i j 不停止,对于数组中所有关键字都相同的情况,我们需要有程序防止 i j 超出数组的界限。最后我们会把主元交换到 i 的最后位置上,也就是倒数第二个位置,这样我们又陷入了最坏情况。

小数组

对于很小的数组(\(N\leq 20\))快速排序不如插入排序,因此我们可以设置一个截止范围 Cutoff(e.g. 10). 当 N 小于阈值的时候采用插入排序.

实现

void  Quicksort( ElementType A[ ], int N ) 
{ 
    Qsort( A, 0, N - 1 ); 
    /* A:   the array   */
    /* 0:   Left index  */
    /* N – 1: Right index   */
}
/* Return median of Left, Center, and Right */ 
/* Order these and hide the pivot */ 

ElementType Median3( ElementType A[ ], int Left, int Right ) 
{ 
    int  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 ] ); 
    /* Invariant: A[ Left ] <= A[ Center ] <= A[ Right ] */ 
    Swap( &A[ Center ], &A[ Right - 1 ] ); /* Hide pivot */ 
    /* only need to sort A[ Left + 1 ] … A[ Right – 2 ] */
    return  A[ Right - 1 ];  /* Return pivot */ 
}
void  Qsort( ElementType A[ ], int Left, int Right ) 
{   int  i,  j; 
    ElementType  Pivot; 
    if ( Left + Cutoff <= Right ) {  /* if the sequence is not too short */
        Pivot = Median3( A, Left, Right );  /* select pivot */
        i = Left;     j = Right  1;  /* why not set Left+1 and Right-2? */
        for( ; ; ) { 
     while ( A[ + +i ] < Pivot ) { }  /* scan from left */
     while ( A[  j ] > Pivot ) { }  /* scan from right */
     if ( i < j ) 
        Swap( &A[ i ], &A[ j ] );  /* adjust partition */
     else     break;  /* partition done */
        } 
        Swap( &A[ i ], &A[ Right - 1 ] ); /* restore pivot */ 
        Qsort( A, Left, i - 1 );      /* recursively sort left part */
        Qsort( A, i + 1, Right );   /* recursively sort right part */
    }  /* end if - the sequence is long */
    else /* do an insertion sort on the short subarray */ 
        InsertionSort( A + Left, Right - Left + 1 );
}
  • 在最开始选取主元时,我们将 A[left],A[mid],A[Right] 进行排序。这样的话我们将较小值放在了最左边,较大值放在了最右边,这符合分割的要求。此外由于 A[left] 比主元小,我们不用担心 j 越界。

复杂度分析

\(T(N)=T(i)+T(N-i-1+)+cN\) 其中 \(i=|S_1|\)

  • 最坏情形:主元始终是最小元素,此时 \(i=0\) 则递推关系为 \(T(N)=T(N-1)+cN,N>1\) 那么 \(T(N)=T(1)+d\sum\limits_{i=2}^N i=O(N^2)\)
  • 最好情形:主元正好位于中间 \(T(N)=2T(N/2)+cN\Rightarrow T(N)=O(N\log N)\)
  • 平均情形:\(T(N)=\dfrac{2}{N}\sum\limits_{j=0}^{N-1}T(j)+cN\Rightarrow T(N)=O(N\log N)\)

大型结构的排序

交换两个大型的结构可能是非常昂贵的,因此我们让输入数组包含指向结构的指针,通过比较指针指向的关键字,必要时交换指针来进行排序。

排序的一般下界

只使用比较的任意排序算法最坏情形下都需要 \(\Omega(N\log N)\)

使用决策树证明:共 \(N!\) 种排序可能,因此决策二叉树有 \(N!\) 片叶子,则树的深度至少为 \(\log(N!)=\Omega(N\log N)\)

桶排序

若输入数据 \(A_1,A_2,\ldots,A_N\) 都小于 \(M\), 那么我们可以用一个大小为 \(M\)Count 数组,初始化为全 0. 于是 Count\(M\) 个桶,读入到 \(A_i\)Count[Ai] 自增一。所有数据读完后扫描数组 Count 打印排序后的表。

{
    initialize count[ ];
    while (read in a students record)
        insert to list count[stdnt.grade];
    for (i=0; i<M; i++) {
        if (count[i])
            output list count[i];
    }
}

\(O(M+N)\)

LSB MSB


最后更新: 2022年12月31日 10:07:19
创建日期: 2022年12月25日 15:14:42

评论