神刀安全网

《数据结构》排序——基数排序(C++实现)


前言:《数据结构》作为计算机专业的一门重点学科,无论是将来考研、就业,对其的考察都是重中之重,之前的文章已经对此进行过论述。作为考察程序员“编程能力”的一种方式,考验的是我们如何将数据结构的思想用编程语言精确的编码出来。所有的《数据结构》课本都详细的讲解了每一种数据结构和算法的思想,然后给出具体的编程语言代码或者伪代码。算法思想只要认真看书,还是比较容易掌握的 ,真正考验我们的,是从算法思想到具体编码的这个思考过程,就是思考如何编码实现,这个过程是逃不掉的,除非参考别人的现有代码,但一段时间过后一定会忘记(百分之百的,我就忘记了无数次了)。所以,尽量在编程实现前,自己有个清晰的思路,尝试着自己去实现,然后调试,脑细胞不够用了再去参考别人写的。

0、代码:
这是《数据结构》排序系列的最后一文,本文全部代码放在 github:https://github.com/thinkChao/Data-Structure/blob/master/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F.cpp 中,需要的可以下载或者直接复制代码运行,只有一个cpp文件,已经通过测试。

1、关于技术排序的几点说明:
1)堆排序虽然在算法思想上不太容易想到,但是只要明白了其思想(其实挺简单的),编程实现还是非常容易的。所以还是跟以往一样,在这里就不讲解算法思想了,只讨论具体如何编程实现。

2)为了实现基数排序,这里使用二维数组int array[array_size][10]。其中array_size是行数,也就是待排序列的总个数。而10就是二维数组的列,依次分别代表0~9这10个数字。

3)假设最多位数是三,则算法流程是:从一维数组中依次取每个数的个位数的值——>加入到二维数组中相应的列——>收集到一个新的一维数组中——>取十位数的值并收集…………——>取百位数的值并收集…………——>最后收集的数组即为排序后的结果。

4)根据算法流程,我们需要依次取个、十、百位数的值,这个有统一的公式:

设数值为X,那么: 个位数=(X/1)%10; 十位数=(X/10)%10; 百位数=(X/100)%10;

5)在“加入到二维数组中相应的列 ”这一步中,有一个问题需要注意。这个问题不太好描述,所以我举例说明。比如:我在取第一个数的个位数的值的时候,如果是1,我就把它加入到array[0][1],这个没问题;接着取第二个数的个位数的值,结果如果还为1,就把它加入到array[1][1],这步也没问题;注意重点来了,然后我接着取第三个数的个位数的值,结果如果为2,那按照算法思想,我应该把它放入array[0][2]是吧,但是,在实际编程中可以不这样做,为什么?因为如果是这样的话,这也就意味着,每当我们在做“把数值加入到二维数组中相应的列中 ”这一步时,我们首先要先判断这一列已经有了几个数了,然后我们才能在该列的相应的行中加入这个数,这给我们编程又增加了点难度。所以回到那一步,当取第三个数的个位数的值,结果如果为2,应该把它放入array[3][2]。以后依次类推,依次加入array[4][x]、array[5][x]、array[6][x]……

6)上一步我们既然是那样处理的,那么在收集时,我们应该怎么办?首先,我们在建立这个二维数组之初,我们要对其进行初始化,初始化的值越大越好,只要比我们所要输入的数的最大值要大就好了。比方说如果我们最大只处理三位数,那我们可以初始化为一个四位数。这里,我们设这个值为X。在对二维数组进行收集时,只需从上到下,从左至右进行遍历(二维数组其实就是个二维矩阵,这点大家应该都懂),只要这个数比x小,我们就将其加入到一个一维数组中。

7)在我的这个程序中,有一个小bug,就是由于我将二维数组初始化为0,根据我们上一点所讲,那么我的这个程序就无法对0进行排序,所以大家在运行时不要输入0进行测试了。为什么不改过来呢?脑袋好累,不想改了,而且已经上传到github…………

2、附上代码:

#include <iostream> using namespace std; #define ArraySize 8   void radix(int data[],int size) {         int n;         for(int i=1;i<=100;i=i*10)     {         int tmp[20][10]={0};//建立一个20行,10列的数组,每一列分别代表0~9位数,20行代表能存放的总个数         for(int j=0;j<size;j++)         {             n=(data[j]/i)%10;             tmp[j][n]=data[j];         }         int k=0;         for(int p=0;p<10;p++)             for(int q=0;q<size;q++)             {                 if(tmp[q][p]!=0)                     data[k++]=tmp[q][p];             }     }   }   int main() {     int data[ArraySize];     /*输入数组数据*/     cout<<"请输入8个数:"<<endl;     for(int i=0;i<ArraySize;i++)         cin>>data[i];     /*执行排序*/     radix(data,8);     /*输出排序结果*/     cout<<""<<endl;     for(i=0;i<ArraySize;i++)         cout<<data[i]<<" ";     return 0; }

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 《数据结构》排序——基数排序(C++实现)

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址