“C语言实现入门排序”

例子：乱序输入n个数，输出从小到大排序后的结果：

###1.冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
int main()
{
    int i, j, n, a[100], temp;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(i=0;i<n-1;i++) //总共需冒泡n-1次
        {
            for(j=0;j<n-i-1;j++) //第i趟冒泡
            {
                if(a[j]>a[j+1]) //比较a[j]与a[j+1],使a[j+1]大于a[j]
                {
                    temp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = temp;
                }
            }
        }
        for(i=0;i<n;i++) //打印
            printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}

###2.选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h>
int main()
{
    int i, j, n, a[100], t, temp;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(i=0;i<n-1;i++)           //总共排序n-1趟
        {
            t = i;
            for(j=i+1;j<n;j++)       //第i趟从a[i+1]~a[n-1]中选最小的数与a[i]交换
            {
                if(a[t]>a[j])	
                    t = j;
            }
            temp = a[i];
            a[i] = a[t];
            a[t] = temp;
        }
        for(i=0;i<n;i++)
            printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}

###3.快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
1.假设数组为a[n]；
2.第一次排序过程如下：
    取x = 0 ( a[0]为中轴 )；
    i=0 (第一个元素下标), j=n-1(最后一个元素下标)；
    重复下面过程：(直到i>=j)
        {
            从a[j]起，向前找小于a[x]的元素，同时j--，找到后，a[j]与a[x]交换，x=j;
            从a[i]起，向后找大于a[x]的元素，同时i++，找到后，a[i]与a[x]交换，x=i;
         }
3.注意快排函数是迭代函数，必须要有结束条件   (因为忽略结束条件,调试了很久......)
4.再对a[low]~a[x-1]、a[x+1]~a[high]分别调用快排函数
*/
#include<stdio.h>
void quicksort(int a[],int low,int high);
int main()
{
    int i, n, a[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        quicksort(a,0,n-1);
for(i=0;i<n;i++)
            printf("%d ",a[i]);
printf("\n");
    }
    return 0;
}
void quicksort(int a[],int low,int high)
{
    if(low>=high)  return;   //坑爹的结束条件，return后面不能跟数值
    int i=low, j= high, x=i, temp;
    while(i<j)
    {
        for(;a[j]>=a[x]&&i<j;j--);
        if(i<j)
        {
            temp = a[j];
            a[j] = a[i];
            a[i] = temp;
            x = j;
            i++;
        }
        else
            break;     //i>=j即可跳出本次while循环
        for(;a[i]<=a[x]&&i<j;i++);
        if(i<j)
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            x = i;
            j--;
        }
        else
            break;     //跳出本次while循环
    }
    quicksort(a,low,x-1);
    quicksort(a,x+1,high);
}

###4.插入排序法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>
void show(int a[],int n)    //输出数组
{
    int i;
    for(i=0;i<n;i++)
            printf("%d ",a[i]);
    printf("\n");
}
void insertsort(int a[],int n);
int main()
{
    int i, n, a[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        insertsort(a,n);
        show(a,n);
    }
    return 0;
}
void insertsort(int a[],int n)
{
    int i ,j ,k ,temp;
    for(i=1;i<n;i++)    //插入a[i]
    {
        j=i-1;
        for(;a[i]<a[j]&&j>=0;j--);  //寻找插入点
        j++;
        if(j==i)     //该数有序，不需要前插
            continue;
        else
        {
            temp=a[i];
            for(k=i-1;k>=j;k--) //将插入点后面的数依次后移一位
            {
                a[k+1]=a[k];
            }
            a[j]=temp;
        }
    }
}

###5.shell排序法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
void show(int a[],int n)    //输出数组
{
    int i;
    for(i=0;i<n;i++)
            printf("%d ",a[i]);
    printf("\n");
}
void shellsort(int a[],int n);
int main()
{
    int i, n, a[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        shellsort(a,n);
        show(a,n);
    }
    return 0;
}
void shellsort(int a[],int n)
{
    int k ,i ,j ,l ,temp;
    k = n/2;
    while(k>=1)
    {
        for(i=k;i<n;i++)
        {
            if(a[i]>=a[i-k])    //已经有序，不需要移动
                continue;
            else
            {
                for(j=i-k;a[j]>=a[i]&&j>=0;j=j-k); j+=k;    //寻找插入点a[j]
                temp = a[i];                //  保存a[i]
                for(l=i-k;l>=j;l-=k)        //依次向后移动k个位置
                {
                    a[l+k] = a[l];
                }
                a[j]=temp;      //插入
            }
        }
        k = k/2;
    }
}

###6.归并排序
归并排序是一种很容易进行并行化的算法，因为归并的各个数据区间都是独立的，没有依赖关系。并且归并排序是一种速度比较快的排序，且是一种稳定的排序算法，排序速度与关键词初始排列无关。
串行归并排序的算法大体的可以描述为：首先将要排序的表分成两个节点个数基本相等的子表，然后对每个子表进行排序，最后将排好序的两个子表合并成一个子表。在对子表进行排序时可以将子表再分解成两个节点数量基本相同的子表，当子表足够小时，也可以采用其他排序方法对子表进行排序，然后再对排好序的子表进行归并操作，最后将整个表排好序
算法流程图：

/*伪代码：
mergesort(int a[],int low,int high)；

if(high-low+1>2)执行如下几步：(3个及以上)
mid = (0+n)/2;
mergesort(a,low,mid-1);
mergesort(a,mid,high);进行本轮二路归并；bsort(int low,int mid,int high);
i=low,j=mid;
while(i=a[high]) 交换a[low],a[high];
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<stdio.h>
int other[100];
void exchange(int *a,int *b)
{
    int t=*a;
    *a=*b;
    *b=t;
}
void show(int a[],int n)    //输出数组
{
    int i;
    for(i=0;i<n;i++)
            printf("%d ",a[i]);
    printf("\n");
}
void mergesort(int a[],int low,int high);
int main()
{
    int i, n, a[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        mergesort(a,0,n-1);
        show(a,n);
    }
    return 0;
}
void mergesort(int a[],int low,int high)
{
    if((high-low+1)>2)		//含3个以上
    {
        int mid = (high+low)/2;
        mergesort(a,low,mid);
        mergesort(a,mid+1,high);
        int i=low, j=mid+1, k=low;
        while(i<=mid&&j<=high)
        {
            if(a[i]<=a[j])
            {
                other[k++]=a[i++];
            }
            if(a[i]>a[j])
            {
                other[k++]=a[j++];
            }
        }
        while(i<=mid)
        {
            other[k++]=a[i++];
        }
        while(j<=high)
        {
            other[k++]=a[j++];
        }
        for(i=low;i<=high;i++)
            a[i]=other[i];
    }
    else		//含2及个以下
    {
        if(a[low]>a[high])
        {
            exchange(a+low,a+high);
        }
    }
}

###7.堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//堆排序
/*(堆是一个完全二叉树，根结点值最大(小))
1.heapadjust(int a[],int i,int sizea)  功能:以a[i]为根，形成一个堆
  buildheap(int a[],int sizea)         功能:调用heapadjust()，使a[]形成一个堆
  heapsort(int a[],int sizea)          功能:do{建堆，输出堆顶}while(堆不空)
*/
#include<stdio.h>
void show(int a[],int n)    //输出数组
{
    int i;
    for(i=0;i<n;i++)
            printf("%d ",a[i]);
    printf("\n");
}
void exchange(int *a,int *b)
{
    int t=*a;
    *a=*b;
    *b=t;
}
void heapadjust(int a[],int i,int sizea)
{
    int maxi=i;
    int l=2*i+1;
    int r=2*i+2;
    if(i<(sizea/2))     //a[i]为叶结点，则不需要调整
    {
        if(l<=(sizea-1)&&a[l]>a[i])    //左孩子比a[i]大的，取左孩子下标
        {
            maxi=l;
        }
        if(r<=(sizea-1)&&a[r]>a[maxi])  //右孩子最大，取右孩子下标
        {
            maxi=r;
        }
        if(maxi!=i)     //取比根大的孩子，与根调换
        {
            exchange(&a[maxi],&a[i]);
            heapadjust(a,maxi,sizea);   //跌倒，以a[maxi]为根，向下调整为大根堆。
        }
    }
}
//函数功能：从最后一个非叶结点起，向上直到根结点，逐步调整，建立大根对堆
void buildheap(int a[],int sizea)
{
    int i;
    for(i=(sizea/2-1);i>=0;i--)     //a[i]为最后一个非叶结点
    {
        heapadjust(a,i,sizea);
    }
}
void heapsort(int a[],int sizea)
{
    int i;
    int j=sizea;
    for(i=0;i<sizea;i++)    //每次循环，都会形成一个大根堆，堆顶元素a[0]最大
    {
        buildheap(a,j);
        exchange(&a[0],&a[--j]);    //将根(最大)结点交换到后面去
                                //堆中元素个数减一
    }
}
int main()
{
    int i, n, a[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        heapsort(a,n);
        show(a,n);
    }
    return 0;
}

###8.带哨兵的直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*从小到大排序
a[0]用作哨兵，当某个数a[i]，找插入位置时，先令a[0]=a[i]，再向前比较，当比较到a[0]时，说明插入位置为a[1],这样可以防止数组越界.
*/
#include<stdio.h>
void show(int a[],int n)    //输出数组
{
    int i;
    for(i=1;i<=n;i++)
            printf("%d ",a[i]);
    printf("\n");
}
void dir_insert(int a[],int n)
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        a[0]=a[i];
        for(j=i-1;a[j]>a[0];j--)  //插入位置：j
            a[j+1]=a[j];
        a[++j]=a[0];
    }
}
int main()
{
    int i, n, a[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        dir_insert(a,n);
        show(a,n);
    }
    return 0;
}

###9.基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//基数排序
/*假设输入数列最多为4位，且都是十进制数
  要做4次划分、收集
*/
#include<stdio.h>
#include<math.h>
#define N 4             //每个数最多4位
void show(int a[],int n)    //输出数组
{
    int i;
    for(i=1;i<=n;i++)
            printf("%d ",a[i]);
    printf("\n");
}
void radixsort(int c[],int i,int n)   //以第i位为依据进行划分和收集
{
    int a[10][30]={{0},{0},{0},{0},{0},{0},{0},{0},{0},{0}};    //a[i][]中收集本次划分基数为i的数
    int b[10]={0};      //b[i]表示本次本次划分后，基数为i的数的个数
    int j,k,l,m;
    k=pow(10,i);
    l=k/10;
    for(j=1;j<=n;j++)   //一次分配的过程
    {
        m=(c[j]%k)/l;       //判断c[j]在本次划分中被分到哪个部分
        a[m][b[m]++]=c[j];  //分配完毕后，基数为m的数为b[m]个
    }
    l=1;
    for(m=0;m<10;m++)   //收集
    {
        for(j=0;j<b[m];j++)
        {
            c[l++]=a[m][j];
        }
    }
}
void basesort(int c[],int n)
{
    int i;
    for(i=1;i<=N;i++)
    {
        radixsort(c,i,n);
    }
}
int main()
{
    int i, n, c[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&c[i]);
        basesort(c,n);
        show(c,n);
    }
    return 0;
}

准IT工作者<br><br>CS专业学生