排序---快排-希尔排序-桶排

排序1：快速排序

PRoblem Description

Input

Output

Example Input

849 38 65 97 76 13 27 49
Example Output
13 27 38 49 49 65 76 97#include<stdio.h>int a[100000];void QQsort(int left,int right){    int i,j,mid;    i=left; j=right;    mid=a[i];  //将处于中间的比较的值赋值为a[i]    if(i>=j)        return ;    while(i<j)    {        while(i<j&&a[j]>=mid)            j--;        //如果比mid大，就继续比较前一个，直到找到        a[i]=a[j];   //直到找到一个数比mid小的数，放到mid位置的前面去        while(i<j&&a[i]<=mid)            i++;      //如果比mid小，就继续比较后一个，直到找到        a[j]=a[i];   //直到找到一个数比mid大的数，放到mid位置的后面去    }    a[i]=mid;    qqsort(left,i-1);  //调整左边    qqsort(j+1,right); //调整右边}int main(){    int i,n;    while(scanf("%d",&n)!=EOF)    {        for(i=0;i<n;i++)        {            scanf("%d",&a[i]);        }        qqsort(0,n-1);  //快速排序        for(i=0;i<n;i++)        {            if(i!=n-1)            {                printf("%d ",a[i]);            }            else            {                printf("%d/n",a[i]);            }        }    }    return 0;}
排序2：希尔排序
Problem Description
我们已经学习了各种排序方法，知道在不同的情况下要选择不同的排序算法，以期达到最好的排序效率；对于待排序数据来说，若数据基本有序且记录较少时， 直接插入排序的效率是非常好的，希尔排序就是针对一组基本有序的少量数据记录进行排序的高效算法。你的任务是对于给定的数据进行希尔排序，其中增量dk=n/(2^k)(k=1,2,3……)
Input
连续输入多组数据，每组输入数据的第一行给出一个正整数N(N <= 10000)，随后连续给出N个整数表示待排序关键字，数字间以空格分隔。
 
Output
输出dk=n/2和dk=1时的结果。
Example Input
1010 9 8 7 6 5 4 3 2 110-5 9 7 -11 37 -22 99 288 33 66
Example Output
5 4 3 2 1 10 9 8 7 61 2 3 4 5 6 7 8 9 10-22 9 7 -11 37 -5 99 288 33 66-22 -11 -5 7 9 33 37 66 99 288
#include<stdio.h>int a[10000],flag=1;void show(int n){    int i;    for(i=0;i<n;i++)    {        if(i!=n-1)        {            printf("%d ",a[i]);        }        else        {            printf("%d/n",a[i]);        }    }}void shell_sort(int n){    int i,j;    int gap,temp,k;    for(gap=n/2;gap>0;gap/=2)    {        for(i=0;i<gap;i++)        {            for(j=i;j<n;j+=gap)            {                if(a[j]<a[j-gap])                {                    temp=a[j];                    k=j-gap;                    while(k>=0&&temp<a[k])                    {                        a[j]=a[k];                        j-=gap;                        k-=gap;                    }                    k+=gap;                    a[k]=temp;                }            }        }        if(flag)        {            flag=0;            show(n);        }    }}int main(){    int i,n;    while(scanf("%d",&n)!=EOF)    {        flag=1;        for(i=0;i<n;i++)        {            scanf("%d",&a[i]);        }        shell_sort(n);        show(n);    }    return 0;}
排序3：bucket sort(桶排序）
Problem Description
根据人口普查结果，知道目前淄博市大约500万人口，你的任务是帮助人口普查办公室按年龄递增的顺序输出每个年龄有多少人，其中不满1周岁的按0岁计算，1到2周岁的按1岁计算，依次类推，大于等于100岁的老人全部按100岁计算。
Input
 输入第一行给出一个正整数N(<=5000000)，随后连续给出N个整数表示每个人的年龄，数字间以空格分隔。
Output
 按年龄递增的顺序输出每个年龄的人口数，人口数为0的不输出，每个年龄占一行，数字间以一个空格分隔，行末不得有多余空格或空行。
 
Example Input
1016 71 17 16 18 18 19 18 19 20
Example Output
16 217 118 319 220 171 1
#include<stdio.h>#include<string.h>int a[105]; //全局变量的初始值，系统自动设置为0。void bucket_sort(int n){    int i;    for(i=0;i<=100;i++)    {        if(a[i])        {            printf("%d %d/n",i,a[i]);        }    }}int main(){    int i,n;    int k;    scanf("%d",&n);    for(i=0;i<n;i++)    {        scanf("%d",&k);        if(k>100)        {            a[100]++;        }        else        {            a[k]++;        }    }    bucket_sort(n);    return 0;}