七大排序速查版

通用结构体:

View Code 
typedef struct
{
int r[MAXSIZE+1];  //下标从1开始用,0为哨兵或其他用
int length; 
}SqList;



一.选择排序

1.1简单选择排序:

(1)思路:

通过n-i次关键字比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录交换.

(2)代码:

View Code 
void SelectSort(Sqlist *L)
{
    int i, j, min;
    for(i=1; i<L->length; i++)
    {
        for(j=i+1; j<L->length; j++)
        {    
            min = i;
            if(L->r[j] < L->r[min])
                min = j;
        }
        if(i != min)
            swap(L,i,min);
    }

}

(3)时间复杂度:

由两个for循环知,时间复杂度为(n^2).

1.2堆排

(1)相关定义:

堆是一种完全二叉树,当结点值>=其左右孩子结点时,为大顶堆;反之,小顶堆.

(2)产生背景:

由简单排序改良而来.简单选择排序第1次从n个数中取最小需要n-1次比较,但第2次从n-1个中选又要n-1-1次比较,没利用好之前的比较.堆排则利用了,体现在建完大顶堆后,结点值大于孩子结点,所以重新调整时,比较的次数就大大缩减.

(3)使用步骤:

1.先建大顶堆 2.输出最大值并重调

(4)代码:

View Code 
//从上往下调整,使得L->r[s..m]满足大顶堆的定义
void HeapAdjust(SqList *L, int s, int m) 
{
    int temp, j;
    temp = L->r[s];
    for(j=2*s; j<m; j*=2)
    {
        if(j<m && L->r[j]<L->r[j+1])
            j++;
        if(temp > L->r[s])
            break;
        L->r[s] = L->r[j];
        s = j;
    }
    L->r[s] = temp;
}

void HeapSort(SqList *L)
{
    int i;
    for(i=L->length/2; i>0; i--)
    {
        HeapAdjust(L,i,L->length);    //从下往上,从右往左调,这样for循环结束后,堆已变成大顶堆;
    }
 
    for(i=L->length; i>0; i--)
    {
        swap(L,1,i);    //输出堆顶元素,然后将最后一个与其交换
        HeapAdjust(L,1,i-1);    //从新调整堆;
    }
}

(5)时间复杂度

由完全二叉树性质知,深度为log2n +1,即调用一次调整要logn时间,而堆排要调用n-1次,所以时间复杂度为(nlogn).

二.交换排序

2.1冒泡排序

(1)思路:

从下往上冒泡,每次都将最小的冒到最上,即第i次则将第i小的数冒泡到第i个位置上

(2)代码:

View Code

(3)事件复杂度:

由两个for循环可知,时间复杂度为(n^2).

2.2快排

(1)思路:

基于分治策略,将一个大的序列按某个值比较,按值大于或小于筛选分成两个小的序列,然后按之前的原则分别再继续细分,直到长度为1则排序完成.

(2)代码:

View Code 
int Partion(SqList *L, int low, int high)
{
    int pivot;
    pivot = L->r[low];  //为达到更高效率,比较好的是取头,尾,中三个数中第二大的数为'枢轴值'
    if(low < high)
    {
        while(low<high && L->r[high]>=pivot)
            high--;
        L->r[row] = L->r[high];
        
        while(low<high && L->r[low]<=pivot)
            low++;
        L->r[high] = L->r[low];
    }
    L->r[low] = pivot;    
    return low;        //返回'枢轴值'
}

void QuikSort(SqList *L, int low, int high)
{
    int pivot;
    if(low < high)
    {
        pivot = partion(L,low,high);    //将原序列一份为二
        QuikSort(L,low,pivot);    //递归调用左边区间
        QuikeSort(L,pivot+1,high);    //递归调用右区间
    }
}

(3)时间复杂度

最优情况为:枢轴值为序列中第n/2大的树,则有:

T(n) = 2T(n/2) + f(n)    //f(n)为将一个序列划分为更小的序列所需的时间,这里f(n)=n

用主方法可知,时间复杂度为(nlogn).

最差情况为:序列为从小到大排好的,而且枢轴值为第一个,则退化为冒泡排序,时间复杂度为(n^2).

三.插入排序

3.1直接插入排序

(1)思路:

将一个记录插入到已经排好序的有序序列中,从而得到一个新的记录数加1的有序序列.

(2)代码:

View Code 
void InsertSort(SqList *L)
{
    int i,j;
    for(i=2; i<L->length; i++)
    {
        if(L->r[i] < L->r[i-1])    //将L->r[i]插入到有序序列中
        {
            L->r[0] = L->r[i];    //哨兵,暂存值
            for(j=i-1; L->r[j]>L->r[0]; j--)
            {
                L->r[j+1] = L->r[j];    //比L->r[i]大的,向后挪,腾出位子来            
            }
            L->r[j+1] = L->r[0];    //j+1是由于for循环最后多减了1
        }
        
    }
}

(3)时间复杂度:(n^2).

3.2希尔排序

(1)思路:

直接插入排序的改良版.先用比较大的间隔的数去使用插入排序,然后逐步缩减间隔大小,直到为1.即让序列每次排序后越来越接近有序序列.

(2)代码:

View Code 
void ShellSort(SqList *L)
{
    int i, j;
    int increment = L->length;
    while(increment>1)
    {
        increment = increment/3 +1;    //相对来说比较好的一个间隔数
        for(i=increment+1; i<=L->length; i++)
        {
            if(L->r[i] < L->r[i-increment])
            {
                L->r[0] = L->r[i];
                for(j=i-increment; L->r[j]>L->r[0]; j=j-increment)
                {
                    L->r[j+increment] = L->r[j];
                }
                L->r[j+increment] = L->r[0];
            }
        }
    }
}

(3)时间复杂度:

大量的研究表明，当增量序列为dlta[k]=2t-k+1-1（0≤k≤t≤⌊log2(n+1)⌋）时，可以获得不错的效率，其时间复杂度为O(n3/2)，要好于直接排序的O(n2)。

四.归并排序

归并排序

(1)思路:

典型的分治策略,分而治之,分到1个1个,再两两合并成有序序列.

(2)步骤:

需要一个临时数组来装分出来的两个序列.

(2)代码:

View Code 
void MergeSort(SqList *L)
{
    MSort(L->r, L->r, 1, L->length);
}

void MSort(int SR[],int TR1[], int s, int t)    //将SR[s..t]归并排序为TR1[s..t]
{
    int m;
    int TR2[MAXSIZE+1];    //临时数组,用来在相邻递归函数之间传递数据
    
    if(s==t)    //3递归结束条件,即每个数组只有一个元素
        TR1[s] = SR[s];
    else
    {
        m = (s+t)/2;    //1平分SR,然后从两个序列中继续递归调用
        MSort(SR,TR2,s,m);
        MSort(SR,TR2,m+1,t);
        Merge(TR2,TR1,s,m,t);    //2将TR2[s..m]和TR2[m+1..t]合并到TR1[s..t]中
    
    }
}

void Merge(int SR[], int TR[], int i, int m, int n)
{
    int j, k, l;
    for(k=i,j=m+1; (i<=m)&&(j<=n); k++)
    {
        if(SR[i]<SR[j])
            TR[K] = SR[i++];
        else
            TR[K] = SR[j++];
    }
    
    //跳出for循环则说明有一组已经全部插入TR[]中,所以将剩下的全部复制到TR[]后面即可
    if(i<=m)    //i<=m,则说明j>n即j已经插完
        for(l=1; l<=m; l++)
            TR[k+1] = SR[i+1];
            
    if(j<=n)
        for(l=1; l<=n; l++)
            TR[k+1] = SR[j+1];
}

(3)时间复杂度:

T(n) = 2T(n/2) + n-1    //n-1为将n个数分成一个一个以及两两合并的时间,由于n个要比较n-1次

由主方法可知,时间复杂度为(nlogn).

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Quains/p/2430607.html