C语言排序算法复习

排序算法有很多种,这里在复习和分析的基础上,做一个自己的总结;

首先要知道有哪些排序算法,google一下,有云C语言7大经典排序算法(也有8大)。主要包括冒泡排序,快速排序,选择排序,插入排序,希尔排序,归并排序,堆排序,8大的还有基数排序。各有各的版本,代码写法也各不相同。所以这里以整理思路为先,代码只是作为自己的一个备份。

搞清楚的概念稳定排序和不稳定排序,就看序列中两个值相等的数,排完序之后的相对位置是否改变,如果改变了就不稳定。

内部排序和外部排序,只用到内存即可完成排序的就叫内部排序,外部排序因为序列比较长,用到了外部存储。

算法好坏标准:时间复杂度和空间复杂度。分析T(n)=O(f(n))为主,这个还是比较简单的理解一下就行,因为这种方法本身也是一种统计估计。

针对3中存储结构,1、以一组连续的地址单元作为存储结构;2、以链表作为存储结构;3、和1一样存储,但是通过建立辅助表来进行排序。

 插入类排序:直接插入排序,希尔排序;

第一个算法,直接插入算法,很简单,假如我们的数组是R[n+1],第一个作为交换时用的中间变量;那么R[1]作为最初的有序区,从i=2开始不断插入R[i],插入时跟有序区中的R[j]进行比较;R[0]在while循环中可以作为监视哨,以防下标变量j越界,避免了while循环检测j是否越界,测试循环条件的时间可以减少一半。

算法的时间复杂度为O(n2);排序中最坏情况就是全逆序,最好情况,全正序;根据这样的两种情况来判断。

希尔排序,多了一个增量数组,有选择规则(使得增量值没有除1之外的公因子)如5.3.1;按照增量的值进行多轮排序,使得序列趋于正序列和交换次数较少的序列;希尔排序其实就是插入排序的改进版本。

算法复杂度O(nlgn)

交换类排序:冒泡排序和快速排序

冒泡排序,想法很简单,相邻两个元素比较,大的放后面,一趟一趟比,最后完成排序。快速排序就是对这一过程进行了优化;还有双向冒泡法,改进算法,这里不深入了。冒泡排序算法复杂度O(n2)

快速排序,这里首先要选取一个基准,一般都是一上来就吧R[0]作为基准,大的放在右边,小的放在左边,形成两个子序列,然后R[0]在中间,对两个子序列继续重复上一过程,直到序列里面的个数为1;从而可以看出,这个算法可以用递归。 算法复杂度O(n2);但是他是目前基于比较的内部排序方法中平均性能最好的。但是快读排序不稳定。

选择类排序:直接选择排序,和直接插入排序作比较,其实差不多,不过这里是选择最小的一个作为有序列的R[1],进行n-1趟排序。也是不稳定的,算法复杂度O(n2)

归并排序:顾名思义,是合并,将一些较小的有序的序列进行合并从而成为整个有序序列。他是稳定的排序,复杂度为O(nlgn),一般应用时先采用直接插入排序得到几个有序序列,然后再进行归并,这样仍然是稳定的。

完了之后就是要把思路转化为程序。毕竟写出程序的能力才是最终要有的。

C语言排序算法复习
#include <stdio.h>
#include <stdlib.h>

#define n 8

typedef struct
{
    int key;
}rectype;
rectype R[n+1];

void insertsort(rectype R[])
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        if(R[i].key<R[i-1].key)
        {
            R[0]=R[i];
            j=i-1;
            while(R[0].key<R[j].key)
            {
                R[j+1]=R[j--];//jiang guanjianzi dayu R[i].key de jilu houyi
            }
            R[j+1]=R[0];
        }
    }
}
void shellsort(rectype R[],int d[],int t)
{
    int i,j,k;
    for(k=0;k<t;k++)
        for(i=d[k]+1;i<=n;i++)
            if(R[i].key<R[i-d[k]].key)
            {
                R[0]=R[i];
                j=i-d[k];
                while(j>0&&R[0].key<R[j].key)
                {
                    R[j+d[k]]=R[i];
                    j=j-d[k];
                    R[j-d[k]]=R[0];
                }
            }
}

void bubblesort(rectype R[])
{
    int i,j,swap;
    for(i=1;i<n;i++)
    {
        swap=0;
        for(j=n;j>i;j--)
        if(R[j-1].key>R[j].key)
        {
            R[0]=R[j-1];
            R[j-1]=R[j];
            R[j]=R[0];
            swap=1;
        }
        if(!swap) break;
    }
}

int partition(rectype R[],int low,int high)
{
    rectype pivot=R[low];
    while(low<high)
    {
        while(low<high&&R[high].key>=pivot.key)
            high--;
        if(low<high)
            R[low++]=R[high];
        while(low<high&&R[low].key<=pivot.key)
            low++;
        if(low<high)
            R[high--]=R[low];
    }
    R[low]=pivot;
    return low;
}

void quicksort(rectype R[],int s,int t)
{
    int i;
    if(s<t)
    {
        i=partition(R,s,t);
        quicksort(R,s,i-1);
        quicksort(R,i+1,t);
    }
}

void selectsort(rectype R[],int m)
{
    int i,j,k;
    rectype temp;
    for(i=1;i<m;i++)
    {
        k=i;
        for(j=i+1;j<=m;j++)
            if(R[j].key<R[k].key)
                k=j;
        if(k!=i)
        {
            temp=R[i];
            R[i]=R[k];
            R[k]=temp;
        }
    }
}

void merge(rectype R[],int low,int mid,int high)
{
    int i,j,k;
    i=low;j=mid+1;k=0;
    rectype *R1=(rectype*)malloc((high-low+1)*sizeof(rectype));
    if(!R1){printf("failed");exit(0);}
    while((i<=mid)&&(j<=high))
    {
        if(R[i].key<=R[j].key)
            R1[k++]=R[i++];
        else
            R1[k++]=R[j++];
    }
    while(i<=mid)    R1[k++]=R[i++];
    while(j<=high)    R1[k++]=R[j++];
    for(k=0,i=low;i<high;k++,i++)
        R[i]=R1[k];
}

void mergepass(rectype R[],int length)
{
    int i=1;
    while(i+2*length-1<=n)
    {
        merge(R,i,i+length-1,i+2*length-1);
        i=i+2*length;
    }
    if((i+length-1)<n)
    {
        merge(R,i,i+length-1,n-1);
    }
}

void mergesort(rectype R[])
{
    int length;
    for(length=1;length<n;length*=2)
        mergepass(R,length);
}

int main()
{
    int i;
    int d[]={5,3,1};
    rectype R[]={{0},{12},{16},{23},{58},{68},{2},{7},{9}};
    insertsort(R);
    for(i=1;i<=n;i++)
        printf("%d ",R[i].key);
    printf("\n");
    shellsort(R,d,2);
    for(i=1;i<=n;i++)
        printf("%d ",R[i].key);
    printf("\n");
    bubblesort(R);    
    for(i=1;i<=n;i++)
        printf("%d ",R[i].key);
    printf("\n");
    quicksort(R,1,8);    
    for(i=1;i<=n;i++)
        printf("%d ",R[i].key);
    printf("\n");    
    selectsort(R,8);
    for(i=1;i<=n;i++)
        printf("%d ",R[i].key);
    printf("\n");
    mergesort(R);    
    for(i=1;i<=n;i++)
        printf("%d ",R[i].key);
    printf("\n");    
}
View Code

 

 

C语言排序算法复习,布布扣,bubuko.com

C语言排序算法复习

上一篇:python 之易经启卦


下一篇:javascript flash 弹框