资源描述
学 院
电子信息学院
班 级
08031302班
学 号
姓 名
张昌武
摘要
此次大作业包含一个标准型大作业，一个界面型大作业，两个数学型大作业和一个算法型大作业。
此次联络我选择题目是：
A.数学型
a.歌星大奖赛
b.求最大数
B.标准型
a.打印指定年份公历表和农历表
C.算法型
a.七种排序算法
D.界面型
a.OpenGL图形库程序
目录
1 摘要 3
1.1 设计题目 3
1.2 设计内容 3
1.3 开发工具 4
1.4 应用平台 4
2 具体设计 4
2.1 程序结构 4
2.2 关键功效 18
2.3 函数实现 18
2.4 开发日志 25
3 程序调试及运行 31
3.1 程序运行结果 31
3.2 程序使用说明 36
3.3 程序开发总结 36
4 附件（源程序） 36
1 摘要
1.1 设计题目
A.数学型
a.歌星大奖赛
b.求最大数
B.标准型
a.打印指定年份公历表和农历表
C.算法型
a.七种排序算法
D.界面型
a.OpenGL图形库程序
1.2 设计内容
A. 数学型
a.十个评委打分，分数在1~100之间，选手最终得分为：去掉一个最高分和一个最低分后其它8个分数平均值。
b.求555555约数中最大三位数
B.标准型
a.打印指定年份公历表和农历表
C.算法型
a.七种排序算法：
快速排序
插入排序
选择排序
冒泡排序
堆排序
归并排序
基数排序
D.界面型
a. OpenGL图形库程序:
绘制黑白框
绘制螺旋曲线
绘制彩色立方体
1.3 开发工具
codeblock
1.4 应用平台
Windows /XP/Vista 32位/win 7、8
2 具体设计
2.1 程序结构
A. 数学型
a.十个评委打分，分数在1~100之间，选手最终得分为：去掉一个最高分和一个最低分后其它8个分数平均值。
该题包含到数组存放
b.求555555约数中最大三位数：
该题只用到循环和判定语句，从999向下搜索即可
B.标准型
a.打印指定年份公历表和农历表
年历设计和计算，应首先判定“某年某月某日是星期几”，即能被4且不能被100整除或能被400整除数。这么，接下来事情就简单了，输入年份，打印出对应日历。
C.算法型
a.七种排序算法：
快速排序(QuickSort)
划分关键是要求出基准统计所在位置pivotpos,编程时候关键点
快速排序：
既然能把冒泡KO掉，立即就激起我们爱好，tnd快排咋这么快，一定要好好研究一下。
首先上图：
从图中我们能够看到：
left指针，right指针，base参考数。
其实思想是蛮简单，就是经过第一遍遍历（让left和right指针重合）来找到数组切割点。
第一步：首先我们从数组left位置取出该数（20）作为基准（base）参考物。
第二步：从数组right位置向前找，一直找到比（base）小数，
假如找到，将此数赋给left位置（也就是将10赋给20），
此时数组为：10，40，50，10，60，
left和right指针分别为前后10。
第三步：从数组left位置向后找，一直找到比（base）大数，
假如找到，将此数赋给right位置（也就是40赋给10），
此时数组为：10，40，50，40，60，
left和right指针分别为前后40。
第四步：反复“第二,第三“步骤，直到left和right指针重合，
最终将（base）插入到40位置，
此时数组值为： 10，20，50，40，60，至此完成一次排序。
第五步：此时20已经潜入到数组内部，20左侧一组数全部比20小，20右侧作为一组数全部比20大， 以20为切入点对左右两边数根据"第一，第二，第三，第四"步骤进行，最终快排大功告成。
快速排序含有最好平均性能（average behavior），但最坏性能（worst case behavior）和插入排序
相同，也是O(n^2)。比如一个序列5,4,3,2,1，要排为1,2,3,4,5。根据快速排序方法，每次只会有一个数据进入正确次序，不能把数据分成大小相当两份，很显著，排序过程就成了一个歪脖子树，树深度为n，那时间复杂度就成了O(n^2)。尽管如此，需要排序情况几乎全部是乱序，自然性能就确保了。据书上测试图来看，在数据量小于20时候，插入排序含有最好性能。当大于20时，快速排序含有最好性能，归并(merge sort)和堆排序(heap sort)也望尘莫及，尽管复杂度全部为nlog2(n)。
1、算法思想
快速排序是C.R.A.Hoare于1962年提出一个划分交换排序。它采取了一个分治策略，通常称其为分治法(Divide-and-ConquerMethod)。
（1） 分治法基础思想
分治法基础思想是：将原问题分解为若干个规模更小但结构和原问题相同子问题。递归地解这些子问题，然后将这些子问题解组合为原问题解。
（2）快速排序基础思想
设目前待排序无序区为R[low..high]，利用分治法可将快速排序基础思想描述为：
①分解：
在R[low..high]中任选一个统计作为基准(Pivot)，以此基准将目前无序区划分为左、右两个较小子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中全部统计关键字均小于等于基准统计(不妨记为pivot)关键字pivot.key，右边子区间中全部统计关键字均大于等于pivot.key，而基准统计pivot则在正确位置(pivotpos)上，它无须参与后续排序。
注意：
划分关键是要求出基准统计所在位置pivotpos。划分结果能够简单地表示为(注意pivot=R[pivotpos])：
R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high。
②求解：
经过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
③组合：
因为当"求解"步骤中两个递归调用结束时，其左、右两个子区间已经有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。
2、快速排序算法QuickSort
void QuickSort(SeqList R，int low，int high)
{ //对R[low..high]快速排序
int pivotpos； //划分后基准统计位置
if(low<high){//仅当区间长度大于1时才须排序
pivotpos=Partition(R，low，high)； //对R[low..high]做划分
QuickSort(R，low，pivotpos-1)； //对左区间递归排序
QuickSort(R，pivotpos+1，high)； //对右区间递归排序
}
} //QuickSort
注意：
为排序整个文件，只须调用QuickSort(R，1，n)即可完成对R[l..n]排序。
插入排序
算法描述
插入排序：插入即表示将一个新数据插入到一个有序数组中，并继续保持有序。比如有一个长度为N无序数组，进行N-1次插入即能完成排序；第一次，数组第1个数认为是有序数组，将数组第二个元素插入仅有1个有序数组中；第二次，数组前两个元素组成有序数组，将数组第三个元素插入由两个元素组成有序数组中......第N-1次，数组前N-1个元素组成有序数组，将数组第N个元素插入由N-1个元素组成有序数组中，则完成了整个插入排序。
以下面5个无序数据为例：
65 27 59 64 58 （文中仅细化了第四次插入过程）
第1次插入: 27 65 59 64 58
第2次插入: 27 59 65 64 58
第3次插入: 27 59 64 65 58
第4次插入: 27 58 59 64 65
二. 算法分析
平均时间复杂度：O(n2)
空间复杂度：O(1) (用于统计需要插入数据)
稳定性：稳定
选择排序
算法描述
选择排序：比如在一个长度为N无序数组中，在第一趟遍历N个数据，找出其中最小数值和第一个元素交换，第二趟遍历剩下N-1个数据，找出其中最小数值和第二个元素交换......第N-1趟遍历剩下2个数据，找出其中最小数值和第N-1个元素交换，至此选择排序完成。
以下面5个无序数据为例：
56 12 80 91 20（文中仅细化了第一趟选择过程）
第1趟：12 56 80 91 20
第2趟：12 20 80 91 56
第3趟：12 20 56 91 80
第4趟：12 20 56 80 91
算法分析
平均时间复杂度：O(n2)
空间复杂度：O(1) (用于交换和统计索引)
稳定性：不稳定 （比如序列【5， 5， 3】第一趟就将第一个[5]和[3]交换，造成第一个5挪动到第二个5后面）
冒泡排序
冒泡排序法基础思想：（以升序为例）含有n个元素数组标准上要进行n-1次排序。对于每一躺排序，从第一个数开始，依次比较前一个数和后一个数大小。假如前一个数比后一个数大，则进行交换。这么一轮过后，最大数将会出现称为最末位数组元素。第二轮则去掉最终一个数，对前n-1个数再根据上面步骤找出最大数，该数将称为倒数第二数组元素......n-1轮过后，就完成了排序。
若要以降序次序排列，则只需将 if(array[j]>array[j+1])语句中大于号改为小于号即可。
堆排序
堆排序是利用堆性质进行一个选择排序。下面先讨论一下堆。
1.堆
堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或Key[i]>=Key[2i+1]&&key>=key[2i+2]
即任何一非叶节点关键字小于或大于其左右孩子节点关键字。
堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆堆顶关键字肯定是全部关键字中最大，小顶堆堆顶关键字是全部关键字中最小。
2.堆排序思想
利用大顶堆(小顶堆)堆顶统计是最大关键字(最小关键字)这一特征，使得每次从无序中选择最大统计(最小统计)变得简单。
其基础思想为(大顶堆)：
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始无序区；
2)将堆顶元素R[1]和最终一个元素R[n]交换，此时得到新无序区(R1,R2,......Rn-1)和新有序区(Rn),且满足R[1,2...n-1]<=R[n];
3)因为交换后新堆顶R[1]可能违反堆性质，所以需要对目前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]和无序区最终一个元素交换，得到新无序区(R1,R2....Rn-2)和新有序区(Rn-1,Rn)。不停反复此过程直到有序区元素个数为n-1，则整个排序过程完成。
操作过程以下：
1)初始化堆：将R[1..n]结构为堆；
2)将目前无序区堆顶元素R[1]同该区间最终一个统计交换，然后将新无序区调整为新堆。
所以对于堆排序，最关键两个操作就是结构初始堆和调整堆，其实结构初始堆实际上也是调整堆过程，只不过结构初始堆是对全部非叶节点全部进行调整。
下面举例说明：
给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序。
首先依据该数组元素构建一个完全二叉树，得到
然后需要结构初始堆，则从最终一个非叶节点开始调整，调整过程以下：
20和16交换后造成16不满足堆性质，所以需重新调整
这么就得到了初始堆。
即每次调整全部是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换以后可能造成被交换孩子节点不满足堆性质，所以每次交换以后要重新对被交换孩子节点进行调整)。有了初始堆以后就能够进行排序了。
此时3在堆顶不满堆性质，则需调整继续调整
这么整个区间便已经有序了。
从上述过程可知，堆排序其实也是一个选择排序，是一个树形选择排序。只不过直接选择排序中，为了从R[1...n]中选择最大统计，需比较n-1次，然后从R[1...n-2]中选择最大统计需比较n-2次。实际上这n-2次比较中有很多已经在前面n-1次比较中已经做过，而树形选择排序恰好利用树形特点保留了部分前面比较结果，所以能够降低比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，所以其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序，不适合统计较少排序。
归并排序
归并排序基础操作是 将两个或两个以上统计有序序列归并为一个有序序列。最简单情况是，只含一个统计序列显然是个有序序列，经过"逐趟归并"使整个序列中有序子序列长度逐趟增大，
直至整个统计序列为有序序列止。 它基础操作是将两个相邻有序子序列"归并"为一个有序序列，
如右侧所表示。这个操作对次序表而言是极其轻易实现，只要依关键字从小到大进行"复制"即可
基数排序
简略概述：基数排序是经过“分配”和“搜集”过程来实现排序。而这个思想该怎样了解呢？请看以下例子。
（1）假设有欲排数据序列以下所表示：
73 22 93 43 55 14 28 65 39 81
首先依据个位数数值，在遍历数据时将它们各自分配到编号0至9桶（个位数值和桶号一一对应）中。
分配结果（逻辑想象）以下图所表示：
分配结束后。接下来将全部桶中所盛数据根据桶号由小到大（桶中由顶至底）依次重新搜集串起来，得到以下仍然无序数据序列：
81 22 73 93 43 14 55 65 28 39
接着，再进行一次分配，这次依据十位数值来分配（原理同上），分配结果（逻辑想象）以下图所表示：
分配结束后。接下来再将全部桶中所盛数据（原理同上）依次重新搜集串接起来，得到以下数据序列：
14 22 28 39 43 55 65 73 81 93
观察能够看到，此时原无序数据序列已经排序完成。假如排序数据序列有三位数以上数据，则反复进行以上动作直至最高位数为止。
那么，到这里为止，你认为你是不是一个细心人？不要不假思索回复我。不管回复什么样问题，全部要做到心比头快，头比嘴快。
仔细看看你对整个排序过程中还有哪些迷惑？真看不到？认为我做得很好？抑或前面没看懂？
假如你看到这里真心没有意识到或发觉这个问题，那我告诉你：悄悄去找个墙角蹲下用小拇指画圈圈（好好反省反省）。
追问：观察原无序数据序列中73 93 43 三个数据次序，在经过第一次（根据个位数值，它们三者应该是在同一个桶中）分配以后，
在桶中次序由底至顶应该为73 93 43（即就是装迟在最上面，对应我们上面逻辑想象应该是43 93 73），对吧？这个应该能够想明白吧？理论上应该是这么。
不过，不过，不过分配后很显著在3号桶中三者次序刚好相反。这点莫非你没有发觉吗？或是发觉了认为不屑谈及（算我贻笑大方）？
其实这个也正是基数排序稳定性原因（分配时由末位向首位进行），请看下文具体分析。
再思索一个问题：既然我们能够从最低位到最高位进行如此分配搜集，那么是否能够由最高位到最低位依次操作呢？ 答案是完全能够。
基于两种不一样排序次序，我们将基数排序分为LSD（Least significant digital）或MSD（Most significant digital），
LSD排序方法由数值最右边（低位）开始，而MSD则相反，由数值最左边（高位）开始。
注意一点：LSD基数排序适适用于位数少数列，假如位数多话，使用MSD效率会比很好。
MSD方法和LSD相反，是由高位数为基底开始进行分配，但在分配以后并不立即合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中数值根据下一数位值分配到“子桶”中。
在进行完最低位数分配后再合并回单一数组中。
（2）我们把扑克牌排序看成由花色和面值两个数据项组成主关键字排序。
要求以下：
花色次序：梅花<方块<红心<黑桃
面值次序：2<3<4<...<10<J<Q<K<A
那么，若要将一副扑克牌排成下列次序：
梅花2，...，梅花A，方块2，...，方块A，红心2，...，红心A，黑桃2，...，黑桃A。
有两种排序方法：
<1>先按花色分成四堆，把各堆搜集起来；然后对每堆按面值由小到大排列，再按花色从小到大按堆收叠起来。----称为"最高位优先"(MSD)法。
<2>先按面值由小到大排列成13堆，然后从小到大搜集起来；再按花色不一样分成四堆，最终次序搜集起来。----称为"最低位优先"(LSD)法。
【2】代码实现
（1）MSD法实现
最高位优先法通常是一个递归过程：
<1>先依据最高位关键码K1排序，得到若干对象组，对象组中每个对象全部有相同关键码K1。
<2>再分别对每组中对象依据关键码K2进行排序，按K2值不一样，再分成若干个更小子组，每个子组中对象含有相同K1和K2值。
<3>依此反复，直到对关键码Kd完成排序为止。
<4> 最终，把全部子组中对象依次连接起来，就得到一个有序对象序列。
（2）LSD法实现
最低位优先法首先依据最低位关键码Kd对全部对象进行一趟排序，
再依据次低位关键码Kd-1对上一趟排序结果再排序，
依次反复，直到依据关键码K1最终一趟排序完成，就能够得到一个有序序列。
使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组。
【3】基数排序稳定性分析
基数排序是稳定性排序算法，那么，到底怎样了解它所谓稳定特征呢？
比如：我们有以下欲排数据序列：
下面选择LSD逻辑演示
第一次按个位数值分配，结果以下图所表示：
然后搜集数据结果以下：
第二次按十位数值分配，结果以下图所表示：
然后搜集数据结果以下：
注意：分配时是从欲排数据序列末位开始进行，逐次分配至首位。
D.界面型
a. OpenGL图形库程序
openGL（Open Graphics Library）从本质上说，它是一个3D图形和模型库，含有高度移植性。我们能够将openGL看做是一个C运行时函数库，这个函数库能够帮助我们绘制二维或三维图像。
静态链接库和动态链接库
静态库：lib文件。编译时代码编译进exe中，会使得程序体积很庞大。不利于模块共享。优点：不会有dll hell问题。仿佛“企业间吞并”。
动态库：dll文件。代码在dll中，其它程序调用dll中代码，多个程序能够共享。缺点：dll hell(dll地狱)，版本问题。
另外，关键用到就是“glut.h”这个头文件，它包含了我们所需大多数函数，直接调用很方便！
我们利用OpenGl函数库编写了三个简单程序，分别是：绘制黑白框、绘制螺旋曲线、绘制彩色立方体。
2.2 关键功效
A. 数学型
a.十个评委打分，分数在1~100之间，选手最终得分为：去掉一个最高分和一个最低分后其它8个分数平均值。
该题关键实现赛场积分统计
b.求555555约数中最大三位数
该题关键实现一个数约数求解
B.标准型
a.打印指定年份公历表和农历表
该题关键实现制订年月日期输出
C.算法型
a.七种排序算法：
快速排序
插入排序
选择排序
冒泡排序
堆排序
归并排序
基数排序
该题关键实现一组数据排序
D.界面型
a. OpenGL图形库程序
该题关键实现OpenGl图形库在Windows系统下图形设计
/*请在这里说明你大作业程序功效，并具体描述它们实现原理和方法（包含算法、数据结构）。*/
2.3 函数实现
B.标准型
a.打印指定年份公历表和农历表
void DateTrans(char *chDate,int *nYear,int *nMonth,int *nDay) // 1
{
*nYear=(chDate[0]-'0')*1000+(chDate[1]-'0')*100+(chDate[2]-'0')*10+chDate[3]-'0';
*nMonth=(chDate[5]-'0')*10+chDate[6]-'0';
*nDay=(chDate[8]-'0')*10+chDate[9]-'0';
}
int IsLeapYear(int nYear) // 2
{
if(nYear%4==0)
return 1;
else
return 0;
}
int GetWeekOfFirstday(int nYear) // 3
{
if(nYear>)
return ((nYear-)*365+(nYear-)/4+1)%7;
else if(nYear<)
return 6-((-nYear)*365+(-nYear)/4)%7;
else
return 6;
}
int GetWeek(int nYear,int nMonth,int nDay,int nWeekOfFirstday) // 4
{
int nDaysYear[]={31,28,31,30,31,30,31,31,30,31,30,31};
int nDaysLeapYear[]={31,29,31,30,31,30,31,31,30,31,30,31};
int i,sum=0;
if(nYear%4==0)
{
for(i=0;i<(nMonth-1);i++)
{
sum+=nDaysLeapYear[i];
}
return (sum+nDay+nWeekOfFirstday-1)%7;
}
else
{
for(i=0;i<(nMonth-1);i++)
{
sum+=nDaysYear[i];
}
return (sum+nDay+nWeekOfFirstday-1)%7;
}
}
void PrintCalendar(int nWeek,int nDay,int nMonthDays,char *chDate) // 5
{
int i,j;
printf("the calender of this month as following:\n");
printf("*********************************\n");
printf(" SUN MON TUE WEN THU FRI STA\n");
for(i=1,j=1;j<=nMonthDays;i++)
{
if(i<=nWeek+1)
printf(" ");
else
{
printf("%4d",j);
j++;
}
if(i%7==0)
printf("\n");
}
printf("\n********************************\n");
printf("OK!\n");
}
C.算法型
a.七种排序算法：
快速排序
void quickSort(int a[],int left,int right)
{
int i=left;
int j=right;
int temp=a[left];
if(left>=right)
return;
while(i!=j)
{
while(i<j&&a[j]>=temp)
j--;
if(j>i)
a[i]=a[j];//a[i]已经赋值给temp,所以直接将a[j]赋值给a[i],赋值完以后a[j],有空位
while(i<j&&a[i]<=temp)
i++;
if(i<j)
a[j]=a[i];
}
a[i]=temp;//把基准插入,此时i和j已经相等R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
quickSort(a,left,i-1);/*递归左边*/
quickSort(a,i+1,right);/*递归右边*/
}
插入排序
选择排序
void SelectionSort(int *a, int n)
{
int i, j, index, value;
for (i = 0; i < n - 1; i ++) {
index = i;
value = a[i];
for (j = i + 1; j < n; j ++)
if (value > a[j]) {
index = j;
value = a[j];
}
a[index] = a[i];
a[i] = value;
Display(a, n);
}
}
冒泡排序
void BubbleSort(int array[],int n)
{
int i,j,temp;
//外循环控制循环趟数
for(i=0; i<n-1; i++)
{
//内循环选择要进行比较数
for(j=0; j<n-1-i; j++)
{
if(array[j]>array[j+1])
{
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
printf("\nThe sorted numbers are:");
for(i=0; i<n; i++)
{
printf("}",array[i]);
}
printf("\n\n");
}
堆排序
void HeapAdjust(int *a,int i,int size) //调整堆
{
int lchild=2*i; //i左孩子节点序号
int rchild=2*i+1; //i右孩子节点序号
int max=i; //临时变量
if(i<=size/2) //假如i是叶节点就不用进行调整
{
if(lchild<=size&&a[lchild]>a[max])
{
max=lchild;
}
if(rchild<=size&&a[rchild]>a[max])
{
max=rchild;
}
if(max!=i)
{
swap(a[i],a[max]);
HeapAdjust(a,max,size); //避免调整以后以max为父节点子树不是堆
}
}
}
void BuildHeap(int *a,int size) //建立堆
{
int i;
for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2
{
HeapAdjust(a,i,size);
}
}
void HeapSort(int *a,int size) //堆排序
{
int i;
BuildHeap(a,size);
for(i=size;i>=1;i--)
{
//cout<<a[1]<<" ";
swap(a[1],a[i]); //交换堆顶和最终一个元素，即每次将剩下元素中最大者放到最终面
//BuildHeap(a,i-1); //将余下元素重新建立为大顶堆
HeapAdjust(a,1,i-1); //重新调整堆顶节点成为大顶堆
}
}
归并排序
void Merge(int *SR, int *TR, int i, int m, int n){
// 将有序SR[i..m]和SR[m+1..n]归并为有序TR[i..n]
int j = m+1;
int k = i;
for(; i<=m && j<=n; ++k){// 将SR中统计按关键字从小到大地复制到TR中
if (SR[i]<=SR[j]){
TR[k] = SR[i++];
}else{
TR[k] = SR[j++];
}
}
while (i<=m) TR[k++] = SR[i++]; // 将剩下 SR[i..m] 复制到TR
while (j<=n) TR[k++] = SR[j++]; // 将剩下 SR[j..n] 复制到TR
}//Merge
void Msort( int *SR, int *TR1, int s, int t ){
// 对SR[s..t]进行归并排序，排序后统计存入TR1[s..t]
if (s==t){
TR1[s] = SR[s];
}else {
int TR2[10] ;
int m = (s+t)/2; // 将 SR[s..t] 平分为 SR[s..m] 和 SR[m+1..t]
Msort(SR,TR2,s,m); // 递归地将 SR[s..m] 归并为有序 TR2[s..m]
Msort(SR,TR2,m+1, t); // 递归地将SR[m+1..t]归并为有序TR2[m+1..t]
Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t] 归并到 TR1[s..t]
}// else
} // Msort
基数排序
int getdigit(int x,int d)
{
int a[] = {1, 1, 10}; //因为待排数据最大数据也只是两位数，所以在此只需要到十位就满足
return ((x / a[d]) % 10); //确定桶号
}
void PrintArr(int ar[],int n)
{
for(int i = 0; i < n; ++i)
cout<<ar[i]<<" ";
cout<<endl;
}
void msdradix_sort(int arr[],int begin,int end,int d)
{
const int radix = 10;
int count[radix], i, j;
//置空
for(i = 0; i < radix; ++i)
{
count[i] = 0;
}
//分配桶存放空间
int *bucket = (int *) malloc((end-begin+1) * sizeof(int));
//统计各桶需要装元素个数
for(i = begin;i <= end; ++i)
{
count[getdigit(arr[i], d)]++;
}
//求出桶边界索引，count[i]值为第i个桶右边界索引+1
for(i = 1; i < radix; ++i)
{
count[i] = count[i] + count[i-1];
}
//这里要从右向左扫描，确保排序稳定性
for(i = end;i >= begin; --i)
{
j = getdigit(arr[i], d); //求出关键码
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
