插入排序

核心：利用的是从位置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] ;}

快速排序

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

如果S中元素个数是0或1，则返回

取S中任一元素v,称为枢纽元

将S剩余的其它元素，分为两个不相交的集合

返回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) ;}

总结

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

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

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

堆排序比希尔排序要满

插入排序一般用于较小的或接近排好序的输入

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

转载于:https://www.cnblogs.com/secoding/p/9609382.html

你可能感兴趣的文章