希尔排序

希尔排序(by Donald Shell)：基于插入排序，利用插入排序的简单，同时每次交换相隔较远的元素，使得每次消去不止一个逆序对

定义增量序列元素 D(M)>D(M-1)>…>D(1)=1
对每个D(k)进行“D(k)-间隔”排序(k=M,M-1,…,1)
- “D(k)-间隔”有序的序列，在执行“D(k-1)-间隔”排序后，仍然是“D(k)-间隔”有序的

例： $[81,94,11,96,12,35,17,95,28,58,41,75,15]$

5-间隔–分为5组

$[81,35,41]$ , $[94,17,75]$ , $[11,95,15]$ , $[96,28]$ , $[12,58]$
$[35,41,81]$ , $[17,75,94]$ , $[11,15,95]$ , $[28,96]$ , $[12,58]$
$[35,17,11,28,12,41,75,15,96,58,81,94,95]$

3-间隔–分为3组

$[35,28,75,58,95]$ , $[17,12,15,81]$ , $[11,41,96,94]$
$[28,35,58,75,95]$ , $[12,15,17,81]$ , $[11,41,94,96]$
$[28,12,11,35,15,41,58,17,94,75,81,96,95]$

1-间隔– $[11,12,15,17,28,35,41,58,75,81,94,95,96]$

希尔增量序列

原始希尔排序(按待排序序列的长度)

$D(M)=⌊N/2⌋,D(k)=⌊D(k+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)//注意i至少要大于增量才能比较，因此实际上是从后往前比较的
                A[i]=A[i-D];
            A[i]=Tmp;
        }
    }
}

稳定性：不稳定(相等的元素可能由于其各自所处的位置不同而与之前或之后的元素交换，使其相对位置发生改变)
最坏情况： $T=Θ(N^2)$

较坏情况例子： $[1,9,2,10,3,11,4,12,5,13,6,14,7,15,8,16]$

8-间隔– $[1,5]$ , $[9,13]$ , $[2,6]$ , $[10,14]$ , $[3,7]$ , $[11,15]$ , $[4,8]$ , $[12,16]$

$[1,9,2,10,3,11,4,12,5,13,6,14,7,15,8,16]$

4-间隔– $[1,3,5,7]$ , $[9,11,13,15]$ , $[2,4,6,8]$ , $[10,12,14,16]$

$[1,9,2,10,3,11,4,12,5,13,6,14,7,15,8,16]$

2-间隔– $[1,2,3,4,5,6,7,8]$ , $[9,10,11,12,13,14,15,16]$

$[1,9,2,10,3,11,4,12,5,13,6,14,7,15,8,16]$

1-间隔– $[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]$

原因：增量元素D(k)之间不互质，则小增量可能不起作用

其他增量序列

Hibbard增量序列
- $D(k)=2^{k-1}$ ——保证了相邻元素互质
- 最坏情况： $T=Θ(N^{\frac{3}{2}})$ $T = Θ (N^{\frac{3}{2}})$
  - 猜想： $T(avg)=O(N^{\frac{5}{4}})$ (目前还未能得到证明)
Sedgewick增量序列
- $[1,5,19,41,109,...]$ $[1, 5, 19, 41, 109, . . .]$
  - $9\times 4^i-9\times 2^i+1$ $9 \times 4^{i} - 9 \times 2^{i} + 1$ 或 $4^i-3\times 2^i+1$ $4^{i} - 3 \times 2^{i} + 1$
    - $1=9\times 1-9\times 1+1,5=16-3\times 4+1,19=9\times 4-9\times 2+1,41=64-3\times 8+1,109=9\times 16-9\times 4+1,...$
  - 猜想： $T(avg)=O(N^{\frac{7}{6}})$ ，最坏情况 $T=O(N^{\frac{4}{3}})$ (目前未能得到证明)

例：希尔排序-用Sedgewick增量序列

void ShellSort(ElementType A[],int N)
{
    int Si,D,P,i;
    ElementType Tmp;                               //这里只列出一小部分增量 
    int Sedgewick[]={929,505,209,109,41,19,5,1,0};
    for(Si=0;Sedgewick[Si]>=N;Si++);               //初始的增量Sedgewick[Si]不能超过待排序列长度 
    for(D=Sedgewick[Si];D>0;D=Sedgewick[++Si])
        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;
        }
}

快速排序

快速排序：实际应用中在大规模的随机数据下通常表现最好的排序算法
算法概述：分而治之策略的典型应用
例： $[13,81,92,43,65,31,57,26,75,0]$

找到主元(枢纽、枢轴)65
将各元素依次与65进行比较，大的分为一组，小的分为一组——> $[13,43,31,57,26,0],[81,92,75]$
在两组中重复这一过程，最后排序为 $[0,13,26,31,43,57,65,75,81,92]$

快速排序基本思路：

void QuickSort(ElementType A[],int N){
    pivot=从A[]中选一个主元;
    将S={A[]\pivot}分成两个独立子集:
        A1={a∈S | a<=pivot}和
        A2={a∈S | a<=pivot};
    A[]=Quicksort(A1,N1) ∪ {pivot} ∪ Quicksort(A2,N2);
}

快速排序的最好情况：与主元的选取方法有关
如果选取的主元每次都处于序列的中间，并且正好将序列中分： $T(N)=O(NlogN)$

此时不需要交换，每次将序列等分，属于分治算法的标准复杂度)

选取主元

假设令pivot=A[0]

若序列完全有序，则序列每次被划分为0和n-1个元素的两个连续子列，实际相当于没有划分
- 相当于退化为没有提前判断结束的冒泡排序
- $T(N)=O(N)+T(N-1)=O(N)+O(N-1)+T(N-2)=O(N)+O(N-1)+...+O(1)=O(N^2)$

随机选取主元
- rand()函数也是有开销的，不可取
取头、中、尾的中位数
- 例：使用中位数取pivot

ElementType Median(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]);     //保证A[Left]<=A[Center]<=A[Right]
    Swap(&A[Center],&A[Right-1]);         //将pivot藏到右边，只需考虑A[Left+1]...A[Right-2]即可
    return A[Right-1];                                    //返回pivot
}

子集划分

例： $[8,1,4,9,0,3,5,2,7,6]$ 以6为主元进行一趟快速排序

快速排序快的核心原因：

每一轮快速排序中以主元为界做完子集划分之后，最后枢轴都会被换到正确的位置上且之后不会再移动
- 因为每一轮快速排序都是以上一个主元为界对两边的子序列做递归，
- 主元左右序列的元素在上一轮快速排序中已经按照与枢轴的大小关系排好序
如果有元素正好等于pivot
- 停下来交换而不是继续向下遍历
  - 假设一种极端情况，序列 $[1,1,1,1,1]$ $[1, 1, 1, 1, 1]$
    - 此时主元必然为1，则左右两侧开始扫描后最终都会遍历到最后，甚至可能发生越界
    - 即使对越界进行处理，最终子列分别为0和n-1个元素，出现快速排序的最坏情况(序列基本有序)
    - 反之，如果停下来交换的话，就会每轮确定一个元素位置，达到快速排序的最好情况( $O(N)$ )

小规模数据的处理

快速排序的问题
- 算法往往需要使用递归
  - 对小规模数据(例如N不到100)可能还不如插入排序快
解决方案
- 当递归的数据规模充分小，则停止递归，直接调用简单排序(如插入排序)
  - 在程序中定义一个Cutoff的阈值

快速排序最终算法实现伪代码描述

void Ouick_Sort(ElementType A[],int Left,int Right){
    if(Cutoff<=Right-Left){
        Pivot=Median(A,Left,Right);
        i=Left,j=Right-1;
        while(true){
            while(A[++i]<Pivot);  
            //注意先自增很重要，因为i和j初值分别是Left和Right-1，通过Median()已经确定了和主元的关系，因此直接跳过即可
            //这样的话i和j终止时都是刚好停在使循环结束的那个元素上面
            //A[i]和pivot不取等，即遇到与pivot相等的元素也停下来做交换
            while(A[--j]>Pivot);
            if(i<j)Swap(&A[i],&A[j]);   //比主元小的放在左边，大的放在右边
            else break;                 //此时i==j，整个子列已经扫描完，i的位置就是主元所在的位置
        }
        Swap(&A[i],&A[Right-1]);        //把主元交换到第i的位置
        Quicksort(A,Left,i-1);
        Quicksort(A,i+1,Right);
    }else Insertion_Sort(A+Left,Right-Left+1);
}
void Quick_Sort(ElementType A[],int N){
    Quicksort(A,0,N-1);
}

时间复杂度

平均： $O(NlogN)$
最坏： $O(N^2)$
额外空间复杂度： $O(logN)$ $O (l o g N)$
- 需要递归调用，最好情况是 $O(logN)$ ，最坏是 $O(N)$
稳定性：不稳定

快速排序演示

/* 快速排序 - 直接调用库函数 */

#include <cstdlib>
#define MAXN 100
using namespace std;
typedef int ElementType;

void qsort (void *base, size_t nitems, size_t size, int (*compar) (const void *, const void*)) ;
/*---------------简单整数排序--------------------*/
int N,A[MAXN];

int compare(const void *a, const void *b)
{ /* 比较两整数。非降序排列 */
    return (*(int*)a - *(int*)b);
}
/*---------------------------------------------*/


/*--------------- 一般情况下，对结构体Node中的某键值key排序 ---------------*/
struct Node {
    int key1, key2;
} S[MAXN];
 
int compare2keys(const void *a, const void *b)
{ /* 比较两种键值：按key1非升序排列；如果key1相等，则按key2非降序排列 */
    int k;
    if ( ((const struct Node*)a)->key1 < ((const struct Node*)b)->key1 )
        k = 1;
    else if ( ((const struct Node*)a)->key1 > ((const struct Node*)b)->key1 )
        k = -1;
    else { /* 如果key1相等 */
        if ( ((const struct Node*)a)->key2 < ((const struct Node*)b)->key2 )
            k = -1;
        else
            k = 1;
    }
    return k;
}
/*-------------------------------------------------------------------*/

/* 调用接口 */ 
int main(){
    qsort(A,N,sizeof(int),compare);
    qsort(S, N, sizeof(struct Node), compare2keys);
}
/*--------*/

/* 快速排序 */
void InsertionSort( ElementType A[], int N );
void Swap(ElementType*,ElementType*);

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] );
    /* 此时A[Left] <= A[Center] <= A[Right] */
    Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
    /* 只需要考虑A[Left+1] … A[Right-2] */
    return  A[Right-1];  /* 返回基准Pivot */
}

void Qsort( ElementType A[], int Left, int Right )//有问题，这个函数应该是没写递归出口
{ /* 核心递归函数 */ 
     int Pivot, Cutoff, Low, High;
    
     if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，进入快排 */
          Pivot = Median3( A, Left, Right ); /* 选基准 */ 
          Low = Left; High = Right-1;
          while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
               while ( A[++Low] < Pivot ) ;
               while ( A[--High] > Pivot ) ;
               if ( Low < High ) Swap( &A[Low], &A[High] );
               else break;
          }
          Swap( &A[Low], &A[Right-1] );   /* 将基准换到正确的位置 */ 
          Qsort( A, Left, Low-1 );    /* 递归解决左边 */ 
          Qsort( A, Low+1, Right );   /* 递归解决右边 */  
     }
     else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少，用简单排序 */ 
}

void QuickSort( ElementType A[], int N )
{ /* 统一接口 */
     Qsort( A, 0, N-1 );
}