C++习题-基数排序

C++习题-基数排序

时间: 1ms        内存:128M

描述:

基数排序是一种分配排序,其基本思想是:排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性O(n)。基数排序所做的事情,是对N位分别进行排序。从直觉上来看,人们可能会觉得应该首先按最高有效位进行排序,不过这点与我们的直觉相反,基数排序首先对最低有效位数字进行排序。如果我们每次比较r bits,则需要进行b/r趟,每趟进行计数排序需要O(n+2^r),则总的时间复杂度为O(b/r(n+2^r))。
理论上来说,基数排序的速度是几种排序方法中最快的,可以达到O(N),而其它的排序算法最快也只有O(N*logN)。但是,基数排序需要占用额外的空间,而且只支持整数进行排序。
#include <iostream>
#include <string.h>
using namespace std;
/* 获取输入数字的索引值,order指定需要获取哪一位的索引,1代表个位,2代表十位,3代表百位 */
int get_index(int num, int order)
{
    while(--order)
        num/=10;
    return num%10;
}
/* 进行基数排序 */
void radix_sort(int arr[], int len, int dec, int order)
{
    int i, j;
    int index;                      /* 排序索引 */
    int tmp[1001];                  /* 临时数组,用来保存待排序的中间结果 */
    int num[10];                    /* 保存索引值的数组 */
    memset(num, 0, 10*sizeof(int)); /* 数组初始清零 */
    memset(tmp, 0, len*sizeof(int));/* 数组初始清零 */
    if (dec < order)                /* 最高位排序完成后返回 */
        return;
    for (i=0; i<len; i++)
    {
        index = get_index(arr[i],order);    /* 获取索引值 */
        num[index]++;                       /* 对应位加一 */
    }
    for (i=1; i<10; i++)
        num[i] += num[i-1];                 /* 调整索引数组 */
    for (i=len-1; i>=0; i--)
    {
        index = get_index(arr[i], order);/* 从数组尾开始依次获得各个数字的索引 */
        j = --num[index];                   /* 根据索引计算该数字在按位排序之后在数组中的位置 */
        tmp[j] = arr[i];                    /* 数字放入临时数组 */
    }
    for (i=0; i<len; i++)
        arr[i] = tmp[i];                                     /* 从临时数组复制到原数组 */
/////////////////////////////////////////////////////////
       /*    这里补充代码   */
       /* 继续按高一位的数字大小进行排序 */
/////////////////////////////////////////////////////////
    return;
}
int main()
{
    int i,n;
    int arr[1001];
    cin>>n;
    for(i=0; i<n; i++)
        cin>>arr[i];
    int dec=3;      /* 最多处理位数 */
    int order= 1;   /* 排序的位数,1代表个位、2代表十位、3代表百位 */
    /* 排序函数,从个位开始 */
    radix_sort(arr, n, dec, order);
    for (i=0; i<n; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

输入:

 输入n和n个整数

输出:

从小到大排序

示例输入:

10
2 1 3 4 6 5 7 9 8 10

示例输出:

1 2 3 4 5 6 7 8 9 10 

提示:

参考答案(内存最优[1096]):

#include <stdio.h>
int main()
{
    int i=0,d;
    int a[1001],b,c;
    scanf("%d",&c);
    for(i=0; i<c; i++)scanf("%d",&a[i]);
    for(i=0; i<c-1; i++)
        for(d=0; d<c-i-1; d++)
            if(a[d]>a[d+1])
            {
                b=a[d+1];
                a[d+1]=a[d];
                a[d]=b;
            }
    for(i=0; i<c; i++)printf("%d ",a[i]);
    return 0;
}

参考答案(时间最优[0]):


#include <iostream>
#include <string.h>
using namespace std;
/* 获取输入数字的索引值,order指定需要获取哪一位的索引,1代表个位,2代表十位,3代表百位 */
int get_index(int num, int order)
{
    while(--order)
        num/=10;
    return num%10;
}
/* 进行基数排序 */
void radix_sort(int arr[], int len, int dec, int order)
{
    int i, j;
    int index;                      /* 排序索引 */
    int tmp[1001];                  /* 临时数组,用来保存待排序的中间结果 */
    int num[10];                    /* 保存索引值的数组 */
    memset(num, 0, 10*sizeof(int)); /* 数组初始清零 */
    memset(tmp, 0, len*sizeof(int));/* 数组初始清零 */
    if (dec < order)                /* 最高位排序完成后返回 */
        return;
    for (i=0; i<len; i++)
    {
        index = get_index(arr[i],order);    /* 获取索引值 */
        num[index]++;                       /* 对应位加一 */
    }
    for (i=1; i<10; i++)
        num[i] += num[i-1];                 /* 调整索引数组 */
    for (i=len-1; i>=0; i--)
    {
        index = get_index(arr[i], order);/* 从数组尾开始依次获得各个数字的索引 */
        j = --num[index];                   /* 根据索引计算该数字在按位排序之后在数组中的位置 */
        tmp[j] = arr[i];                    /* 数字放入临时数组 */
    }
    for (i=0; i<len; i++)
        arr[i] = tmp[i]; 
    if(order<dec)    /* 继续按高一位的数字大小进行排序 */
        radix_sort(arr,  len,  dec,  order+1);
    return;
}
int main()
{
    int i,n;
    int arr[1001];
    cin>>n;
    for(i=0; i<n; i++)
        cin>>arr[i];
    int dec=3;      /* 最多处理位数 */
    int order= 1;   /* 排序的位数,1代表个位、2代表十位、3代表百位 */
    /* 排序函数,从个位开始 */
    radix_sort(arr, n, dec, order);
    for (i=0; i<n; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注