假设有 1000个关键字为小于10000的整数的记录序列

旭日东升

求“假设有 1000个关键字为小于10000的整数的记录序列，请编写一种排序算法，要求以尽可能少的比较次数和移动次”的数据结构算法

旭日东升

基数排序：
void sort(int a[],int n)
{
       int i;
       int x[10001],s[10001]={0},rank[10001];
       for(i=0;i<n;i++)
            s[x[i]=a[i]]++;
       for(i=1;i<10001;i++)
            s[i]+=s[i-1];
       for(i=0;i<n;i++)
            rank[i]=s[a[i]]--;//rank数组可不求，这步可跳过
       for(i=0;i<n;i++)
            a[rank[i]-1]=x[i];
}
完整的测试程序：
#include<stdio.h>
void sort(int a[],int n)
{
       int i;
       int x[10001],s[10001]={0},rank[10001];
       for(i=0;i<n;i++)
            s[x[i]=a[i]]++;
       for(i=1;i<10001;i++)
            s[i]+=s[i-1];
       for(i=0;i<n;i++)
            rank[i]=s[a[i]]--;
       for(i=0;i<n;i++)
            a[rank[i]-1]=x[i];
}
int main()
{
int a[101],i,n;
while(~scanf("%d",&n))
{
  for(i=0;i<n;i++)
   scanf("%d",a+i);
  sort(a,n);
  for(i=0;i<n;i++)
   printf("%d ",a[i]);
  puts("");
}
}

LNH_Sniper

效率 明显不高 可以使用希尔排序 或者 快速排序的方法来进行排序
#include "stdio.h"
#include "malloc.h"

int *init_shell_sort(int size)
{
        return (int *)malloc(sizeof(int) * size);
}


void shell_sort(int *arrary, int length)
{
        int loop, loop_in, gap, temp;

        gap = length;

        while(gap >= 1)
        {
                gap = gap / 2;
                for( loop = 0; loop < length - gap; loop++)
                {
                        if( gap )
                                loop_in = loop + gap;
                        else
                                loop_in = loop +1;
                        if( loop_in != length)                    //&ETH;&acute;&micro;&Auml;&ordm;&Uuml;&sup2;&raquo;&ordm;&Atilde;
                        {
                                if(arrary[loop] > arrary[loop_in])
                                {
                                        temp = arrary[loop];
                                        arrary[loop] = arrary[loop_in];
                                        arrary[loop_in] = temp;
                                }
                        }
                }
        }
}

int main(void)
{
        int len, len_buf, len_print, *arrary, *arrary_buf, *arrary_print;
        printf("The Length of Arrary:");
        scanf("%d",&len);
        len_print = len_buf = len;
        arrary = arrary_buf = arrary_print =init_shell_sort( len );
        printf("The Elemments Of Arrary:");
        while( len-- )
        {
                scanf("%d",arrary++);
        }
        shell_sort(arrary_buf, len_buf);
        while( len_print --)
        {
                printf("%d ",*arrary_print++);
        }
        printf("\n");
        return 0;
}

有些不完善的地方，希望大家帮忙完善

Kriginal

//快排

#include <iostream>
#include <cstdlib>

using namespace std;

const int maxn = 1000 + 5;

void quick_sort(int *parr, int left, int right)
{
    int i(left), j(right), middle(0), temp(0);
    middle = parr[(rand() % (right - left + 1)) + left];
    while (i <= j) {
        while (parr[i] < middle && i < right) i++;
        while (parr[j] > middle && j > left) j--;
        if (i <= j) {
            temp = parr[j];
            parr[j] = parr[i];
            parr[i] = temp;
            i++; j--;
        }
    }
    if (left < j) quick_sort(parr, left, j);
    if (right > i) quick_sort(parr, i, right);
}

int main()
{
    int arr[maxn];
    int read, count(0);
    // 输入以任意非int型数据结束，如'#'或字母等 (空格、回车除外)
    while (cin >> read) arr[count++] = read;  
    if (count) {   
        quick_sort(arr, 0, count - 1);
        for (int i = 0; i != count; ++i) {
            cout << arr[i] << ' ' << flush;
        }
        cout << endl;
    } else {
        cout << "error: no data!" << endl;
    }
    system ("PAUSE");
    return 0;
}

LNH_Sniper

回复 Kriginal 的帖子

嗯嗯~不错不错~~很漂亮。

Kriginal

谢谢~ 共勉！

狸猫副园长

不会啊，要何年何月才能学会啊

devil5975

直接开数组存储，然后从小到大输出可以么？

LNH_Sniper

回复 devil5975 的帖子

可以，但效率就比较低，占用空间也许会比较大，
对于数据结构和算法来说，我们要做的是设计出优秀的存储结构和算法 以实现对实际问题的求解

仰望天上的光

“假设有 1000个关键字为小于10000的整数的记录”这个限制显然鸡排或者计数排序快。或者LZ应该把1000改为很大很大的数字，允许数字重复出现，那么就更显得基排和计数排序的优势了。

dps521

:smile:smile:smile:smile