C语言排序

C语言数组排序小结（for beginner)
很多朋友是以谭浩强老师编的《c语言教程》作为学习C语言的入门教程的。书中涉及排序问题一般都以“冒泡法”和“选择法”实现。
为了扩大视野，增加学习编程的兴趣，我参阅了有关书籍，整理了几种排序法，写出来同大家共勉。
（高手们不要笑，这篇文章是写给出学者的，而且我自己也是只菜鸟，虽然内容陈旧，但值得初学者一看）。
让我们先定义一个整型数组a[n],下面用五种方法对其从小到大排序。
（1）“冒泡法”
冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a[i]，则交换它们，一直比较到a[n]。
同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代码：

void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/
{
    int i,j,temp;
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++) /*注意循环的上下限*/
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
}

冒泡法原理简单，但其缺点是交换次数多，效率低。
下面介绍一种源自冒泡法但更有效率的方法“选择法”。

（2）“选择法”
选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把a[k]同后面元素比较，若a[k]>a[j],则使k=j.最后看看k=i是否还成立，不成立则交换a[k],a[i],
这样就比冒泡法省下许多无用的交换，提高了效率。
void choise(int *a,int n)
{
    int i,j,k,temp;
    for(i=0;i<n-1;i++)
    {
        k=i; /*给记号赋值*/
        for(j=i+1;j<n;j++)
        {
            if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/
        }
        if(i!=k) /*当k!=i是才交换，否则a[i]即为最小*/
        {
            temp=a[i];
            a[i]=a[k];
            a[k]=temp;
        }
    }
}

选择法比冒泡法效率更高，但说到高效率，非“快速法”莫属，现在就让我们来了解它。


（4）“插入法”
插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序，再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。
void insert(int *a,int n)
{
    int i,j,temp;
    for(i=1;i<n;i++)/*外循环控制趟数，n个数从第2个数开始到最后共进行n-1次插入*/
    {
        temp=a[i]; /*将待插入数暂存于变量t中*/
        j=i-1;
        while(j>=0&&temp<a[j]) /*在有序序列（下标0?~?i-1）中寻找插入位置*/
        {
            a[j+1]=a[j]; /*若未找到插入位置，则当前元素后移一个位置*
            j--;
        }
        a[j+1]=temp; /*找到插入位置，完成插入*/
    }
}