论坛 › 数据结构与算法 › 假设有 1000个关键字为小于10000的整数的记录序列

旭日东升 发表于 2011-4-29 14:42:37

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

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

旭日东升 发表于 2011-4-29 14:43:41

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

LNH_Sniper 发表于 2011-4-29 17:45:39

效率 明显不高 可以使用希尔排序 或者 快速排序的方法来进行排序
#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 > arrary)
                                {
                                        temp = arrary;
                                        arrary = arrary;
                                        arrary = 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 发表于 2011-4-30 13:40:02

//快排

#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 < middle && i < right) i++;
      while (parr > middle && j > left) j--;
      if (i <= j) {
            temp = parr;
            parr = parr;
            parr = temp;
            i++; j--;
      }
    }
    if (left < j) quick_sort(parr, left, j);
    if (right > i) quick_sort(parr, i, right);
}

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

LNH_Sniper 发表于 2011-4-30 16:11:20

回复 Kriginal 的帖子

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

Kriginal 发表于 2011-4-30 17:09:53

谢谢~ 共勉！

狸猫副园长 发表于 2011-5-1 08:34:47

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

devil5975 发表于 2011-5-22 11:21:17

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

LNH_Sniper 发表于 2011-5-22 13:34:59

回复 devil5975 的帖子

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

仰望天上的光 发表于 2011-5-22 16:48:43

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

dps521 发表于 2015-11-28 11:21:28

:smile:smile:smile:smile

查看完整版本: 假设有 1000个关键字为小于10000的整数的记录序列