排序（C语言实现）

读数据结构与算法分析

插入排序

核心：利用的是从位置0到位置P都是已排序的

所以从位置1开始排序，如果当前位置不对，则和前面元素反复交换重新排序

实现

void InsertionSort(ElementType A[], int N)
{
    int i,P;
    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 ;
    }
}

希尔排序

使用hk增量序列进行一趟排序后，对每个i都有

A[i] \leq A[i+hk]   

重要性质：一个hk排序的文件在之后的排序中将保持hk排序性

实现

• ht = [N / 2]
• hk = [hk+1 / 2]

void ShellSort(ElmentType A[], int N)
{
    ElementType Tmp ;
    int i,j,Increment ;
    for(Increment = N/2;Increment > 0;Increment /= 2)
        for(i = Increment;i < N;i++)
        {
            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 ;
        }
}

堆排序

基于原有的二叉堆

建立二叉堆，执行DeleteMax操作，储存至数组（节省空间可以倒序储存在当前数组）

实现

#define LeftChild(i) (2 * i + 1) ;
void Percdown(ElementType A[],int i,int N)
{
    int Child ,i;
    ElementType Tmp ;
    for(Tmp = A[i]; LeftChild(i) < N-1;i = Child)
    {
        Child = LeftChild(i) ;
        if(Tmp < A[Child])
            A[i] = A[Chile] ;
        else
            break ;
    }
    A[i] = Tmp ;
}

void HeapSore(ElementType A[],int N)
{
    int i ;
    for(i = N/2 ;i >= 0;i--)
        Percdown(A,i,N) ; //建立二叉堆
    for(i = N-1; i > 0; i--)
    {
        Swap(&A[0],&A[i]) ;
        Percdown(A,0,i) ;
    }
    
}

归并排序

基本思想是合并两个已排序的表

实现

递归合并

void Msort(ElementType A[],ElementeType TmpArray[],int Left,int Right)
{
    int Center ;
    if(Left < Right)
    {
        Center = (Left + Right) /2 ;
        Msort(A,TmpArray,Left,Right) ;
        Msort(A,TmpArray,Center + 1,Right) ;
        Merge(A,TmpArray,Left,Center + 1,Right) ;
    }
}

驱动程序

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("内存不足") ；
}

合并函数

void Merge(ElementType A[],ElementType TmpArray[],int Lpos,int Rpos,int RightEnd)
{
    int i,LeftEnd,NumElements,TmpPos ;
    
    LeftEnd = Rpos - 1;
    TmpPos = Lpos ;
    NumElement = RightEnd - Lpos + 1 ;
    
    while(Lpos <= LeftEnd && Rpos <= RightEnd)
        if(A[Lpos] <= A[Rpos])
            TmpArray[TmpPos++] = A[Lpos++] ;
        else
            TmpArray[TmpPos++] = A[Rpos++] ;
            
    while(Lpos <= LeftEnd)
        TmpArray[TmpPos++] = A[Lpos++] ;
    while(Rpos <= RightEnd)
        TmpArray[TmpPos++] = A[Rpos++]
    
    for(i = 0;i < NumElement ;i++,RightEnd--)
        A[RightEnd] = TmpArray[RightEnd] ;
}

快速排序

和归并排序一样都是分治递归算法,在小数组上效率并没有插入排序好

1. 如果S中元素个数是0或1，则返回
2. 取S中任一元素v,称为枢纽元
3. 将S剩余的其它元素，分为两个不相交的集合
4. 返回quicksort(S1),继续选择v,继续quicksort(S2) ;

实现

选取枢纽元

三数中值分割方法

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]) ;
        
    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)
    {
        Pivot = Midian3(A,Left,Right)
        i = Left ; j = Right ;
        for(;;)
        {
            While(A[++i] < Privot){}
            While(A[--j] > Privot){}
            if(i < j)
                Swap(&A[i],&A[j]) ;
            else
                break ;
        }
        Swap(&A[i],&A[Right-1]) ;
        
        Qsort(A,Left,i-1) ;
        Qsort(A,i+1,Right) ;
        
    }
    else
       InsertionSort(A + Left,Right - Left + 1) ; 
}

驱动函数

void QuickSort(ElementType A[],int N)
{
    Qsort(A,0,N-1) ;
}

总结

• 对于一般的内部排序，选用的方法一般是插入排序、希尔排序和快速排序，根据输入来选择

• 高度优化的快速排序在对于很少的输入也可能和希尔排序一样快

  对于快速排序，选取枢纽元十分关键

• 堆排序比希尔排序要满
• 插入排序一般用于较小的或接近排好序的输入

• 归并排序在主存排序中不如快速排序那么好，但是合并时外部排序的中心思想