三种排序法的练习题（桶排序，冒泡排序，快速排序）

小哼买书的三种解法

题目：要登记买书的同学，人数小于100，每个人报一个ISBN码，范围在1~1000;去掉重复的，
并将ISBN码从小大排列

1、桶排序，时间复杂的都为O（n+m），占空间大

#include <stdio.h>

int main()
{
    int arr[1001] = {0};
    int n = 0;
    int i = 0;
    int t = 0;
    int count = 0;

    printf("请输入要登记买书的人数\n");
    scanf("%d", &n);
    for(i=1; i<=n; i++) //接受数据，并去重
    {
        scanf("%d", &t);
        arr[t] = 1;
    }

    for(i=1; i<=1000; i++)
    {
        if(arr[i] == 1)
        {
            count++;
            printf("%d ", i);
        }
    }
    printf("\n共要买%d本书\n", count);

    return 0;
}

2、冒泡法,时间复杂度为o(n+n2)

#include <stdio.h>

int main()
{
    int arr[101] = {0};
    int i = 0;
    int n = 0;
    int j = 0;
    int count = 1;   
    int tmp = 0;

    printf("请输入要登记买书的人的个数\n");
    scanf("%d", &n);  //总共等级的人数
    for(i=1; i<=n; i++)
    {
        scanf("%d", &arr[i]);
    }

    for(i=1; i<=n-1; i++)
    {
        for(j=1; j<=n-1; j++)
        {
            if(arr[j] > arr[j+1])
            {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
    printf("%d ", arr[1]);    //因为这里先输出一个ISBN码，故count的初始值为 1
    for(i=2; i<=n; i++)
    {
        if(arr[i]!=arr[i-1])
        {
            printf("%d ",arr[i]);
            count++;

        }
    }
    printf("共需要%d本书\n", count);

    return 0;
}

3、快速排序，时间复杂度o(logN),和冒泡排序类似

#include <stdio.h>

int arr[101] = {0};

void quick_sort(int left, int right)
{
    int i = 0;
    int j = 0;
    int t = 0;
    int tmp = 0;

    if(left > right)
        return;

    tmp = arr[left];  //tmp保存基准数
    i =  left;
    j = right;
    while(i!=j)
    {
        while(arr[j] >= tmp && j>i)
            j--;
        while(arr[i] <= tmp && j>i)
            i++;
        if(i<j)
        {
            t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    //如果i和j相遇，则和基准数交换
    arr[left] = arr[i];
    arr[i] = tmp;

    quick_sort(left, i-1);
    quick_sort(i+1, right);
}

int main()
{
    int n = 0;
    int i = 0;

    printf("请输入要登记买书的人的个数\n");
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%d", &arr[i]);
    }
    quick_sort(1, n);

    printf("%d ", arr[1]);
    for(i=2; i<=n; i++)
    {
        if(arr[i]!= arr[i-1])
        {
            printf("%d ", arr[i]);
        }
    }

    return 0;
}