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)，一般应用时先采用直接插入排序得到几个有序序列，然后再进行归并，这样仍然是稳定的。

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

#include <stdio.h>

#include <stdlib.h>

#define n 8

typedef struct

{

    int key;

}rectype;

rectype R[n+];

void insertsort(rectype R[])

{

    int i,j;

    for(i=;i<=n;i++)

    {

        if(R[i].key<R[i-].key)

        {

            R[]=R[i];

            j=i-;

            while(R[].key<R[j].key)

            {

                R[j+]=R[j--];//jiang guanjianzi dayu R[i].key de jilu houyi

            }

            R[j+]=R[];

        }

    }

}

void shellsort(rectype R[],int d[],int t)

{

    int i,j,k;

    for(k=;k<t;k++)

        for(i=d[k]+;i<=n;i++)

            if(R[i].key<R[i-d[k]].key)

            {

                R[]=R[i];

                j=i-d[k];

                while(j>&&R[].key<R[j].key)

                {

                    R[j+d[k]]=R[i];

                    j=j-d[k];

                    R[j-d[k]]=R[];

                }

            }

}

void bubblesort(rectype R[])

{

    int i,j,swap;

    for(i=;i<n;i++)

    {

        swap=;

        for(j=n;j>i;j--)

        if(R[j-].key>R[j].key)

        {

            R[]=R[j-];

            R[j-]=R[j];

            R[j]=R[];

            swap=;

        }

        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-);

        quicksort(R,i+,t);

    }

}

void selectsort(rectype R[],int m)

{

    int i,j,k;

    rectype temp;

    for(i=;i<m;i++)

    {

        k=i;

        for(j=i+;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+;k=;

    rectype *R1=(rectype*)malloc((high-low+)*sizeof(rectype));

    if(!R1){printf("failed");exit();}

    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=,i=low;i<high;k++,i++)

        R[i]=R1[k];

}

void mergepass(rectype R[],int length)

{

    int i=;

    while(i+*length-<=n)

    {

        merge(R,i,i+length-,i+*length-);

        i=i+*length;

    }

    if((i+length-)<n)

    {

        merge(R,i,i+length-,n-);

    }

}

void mergesort(rectype R[])

{

    int length;

    for(length=;length<n;length*=)

        mergepass(R,length);

}

int main()

{

    int i;

    int d[]={,,};

    rectype R[]={{},{},{},{},{},{},{},{},{}};

    insertsort(R);

    for(i=;i<=n;i++)

        printf("%d ",R[i].key);

    printf("\n");

    shellsort(R,d,);

    for(i=;i<=n;i++)

        printf("%d ",R[i].key);

    printf("\n");

    bubblesort(R);

    for(i=;i<=n;i++)

        printf("%d ",R[i].key);

    printf("\n");

    quicksort(R,,);

    for(i=;i<=n;i++)

        printf("%d ",R[i].key);

    printf("\n");

    selectsort(R,);

    for(i=;i<=n;i++)

        printf("%d ",R[i].key);

    printf("\n");

    mergesort(R);

    for(i=;i<=n;i++)

        printf("%d ",R[i].key);

    printf("\n");

}

巴特西

C语言排序算法复习

最新文章

热门文章