实验题【实验四题目1】
数据结构实验报告实验名称： 实验四——题目一
学生姓名： 唐文旭
班 级：2013211118
班内序号： 09
学 号： 2013210524
日 期： 2015年1月5日
1．实验要求
使用简单数组实现下面各种排序算法，并进行比较。
排序算法：
1、插入排序
2、希尔排序
3、冒泡排序
4、快速排序
5、简单选择排序
6、堆排序（选作）
7、归并排序（选作）
8、基数排序（选作）
9、其他
要求：
1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性。
2. 程序分析
2.1 存储结构
2.2 关键算法分析
北京邮电大学信息与通信工程学院
第2页
希尔排序又称“缩小增量排序”，是对直接插入排序的一种改进，它利用了直接插入的两个特点：1. 基本有序的序列，直接插入最快；2. 记录个数很少的无序序列，直接插入也很快。希尔排序的基本思想为：将待排序的元素集分成多个子集，分别对这些子集进行直接插入排序，待整个序列基本有序时，再对元素进行一次直接插入排序。
冒泡排序的基本思想是：两两比较相邻的元素，如果反序，则交换位置，直到没有反序的元素为止。具体的排序过程是：将整个待排序元素划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的元素；对无序区从前向后依次将相邻元素的关键码进行比较，若反序则交换，从而使得关键码小的元素向前移，关键码大的元素向后移；重复执行前一个步骤，直到无序区中没有反序的元素。
快速排序元素的比较和移动是从两端向中间进行的。快速排序的基本思想是：在分区中选择一个元素作为轴值，将待排序元素划分成两个分区，使得左侧元素的关键码均小于或等于轴值，右侧元素的关键码均大于或等于轴值，然后分别对这两个分区重复上述过程，直到整个序列有序。
简单选择排序的基本思想是：第1趟，在待排序记录r[1„n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2„n]中选出最小的记录，将它与r[2]交换；以此类推，第i 趟，在待排序记录r[i„n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
r[0]留空，初始时赋为0
2.2 关键算法分析
1、直接插入排序
自然语言描述：
（1） 将整个待排序的记录划分成有序区和无序区。有序区为待排序记录的第一个记录， 无序区为所有剩余带待排序记录。
（2） 从第二个数据开始依次插入到有序区中，直到所有记录插入完毕。 （3） 在r[0]处设置“哨兵”，记为要插入的记录r[i]，在自i-1起往前查找的过程中，同时
后移记录。
（4） 找到插入位置后，将待插入记录插入到有序表中。
（5） 重复执行（3）、（4），直到无序区中没有记录。
伪代码描述：
初始化比较次数compare =0，移动次数move =0 2. for(int i=2;i
for(j=i-1;r[0]
r[j+1]=r[j] 比较次数++；移动次数++；
r[j+1]=r[0]，移动次数++
时间复杂度：最好情况下，待排序序列为正序，每趟秩序与有序序列的最后一个纪录的关键码比较一次，移动两次记录。总的比较次数为n-1，记录移动的次数为2（n-1）。因此，时间复杂度为O （n ）。
最坏情况下，待排序序列为逆序，比较次数为(n+2)(n+1)/2，移动次数为(n+4)(n-1)/2因此，时间复杂度为O （n2）.
平均情况下，总的比较次数为n （n-1）/4，移动次数为（n+4）（n-1）/4，因此，时间复杂度
为O （n2）
2、希尔排序
自然语言描述：
（1） 假设待排序记录为n 个，先取整数d
中的前一个记录比较，在插入记录r[i]时，自r[i-d]往前查找待插入位置，在查找过程中，记录后移也是移动d 个位置。
（3） 当搜索位置j=r[j]，表示插入位置已经找到。在整个序列中，前d 个记 录分别是d 个子序列的第一个记录，所以从第d+1个记录开始插入。 （4） 再缩小d ，重复以上步骤，再对每个子序列进行直接插入排序，直到d=1，即将所有
记录放在一组进行一次直接插入排序，最终将所有记录重新排序得到有序序列。
伪代码描述：
1. 初始化比较次数compare =0，移动次数move =0
for(int d=n/2;d>=1;d=d/2)
for(int i=d+1;i
if(r[i]
r[0]=r[i]，移动次数++
for(j=i-d;i>0&&r[0]
r[j+d]=r[j] 比较次数++，移动次数++
r[j+d]=r[0]，移动次数++
时间复杂度：
希尔排序的时间性能分析是一个复杂的问题，因为它是所取增量的函数。有人在大量实验的基础上指出，希尔排序的时间性能在O （n2）和O （nlog2n ）之间
3、冒泡排序
自然语言描述：
（1） 将整个待排序的记录划分成有序区和无序区，初始有序区为空，无序区包括所有待排序记录。设置变量pos ，此位置之后的所有记录均已经有序。
（2） 对无序区从前向后一次将相邻记录的关键码进行比较，若反序则交换，从而使得关 键码小的记录前移，关键码大的记录后移。
（3） 每趟冒泡排序开始之前，设pos 初值为0，在该趟排序过程中，只要有记录的交换，pos 就大于0。通过pos 是否为0判断是否有记录的交换，从而判断冒泡排序是否结束。 伪代码描述：
初始化比较次数compare =0，移动次数move =0
int pos=0 2. while(pos!=0)
int bound=pos，pos=n
for(int j=1;j
if(r[j]>r[j+1])
r[0]=r[j]，r[j]=r[j+1],r[j+1]=r[0]
pos=j，move+=3
时间复杂度：
最好情况下，待排序记录序列为正序，算法只执行了一趟，进行了n-1次关键妈的比较，不需要移动记录，时间复杂度为O （n ） 最坏情况下，待排序记录序列为反序，每趟排序在无序序列中只有一个最大的纪录被交换到最终位置，故算法执行n-1趟，第i 趟排序执行了n-1
次关键码的比较和n-i 次记录的交换，这样，关键码的比较次数为n （n-1）/2，记录的移动次数为3n （n-1）/2平均情况下，起泡排序的时间复杂度与最坏情况同数量级。
4、快速排序
自然语言描述：
（1） 取第一个记录作为基准，设置两个参数i ，j 分别用来指示将要与基准记录进行比较 的左侧记录位置和右侧记录位置，也就是本次划分的区间。 （2） 右侧扫描过程：将基准记录与j 指向的记录进行比较，如果j 指向记录的关键码大，
则j--，重复右侧扫描过程，直到右侧的记录小，即反序，执行r[i]=r[j] （3） 左侧扫描过程：将基准记录与i 指向的记录进行比较，如果i 指向记录的关键码大，
则i--，重复右侧扫描过程，直到右侧的记录小，即反序，执行r[j]=r[i]
（4） 重复执行（2）、（3），直到i 、j 指向同一位置。 （5） r[i]=pivot （6） 返回i 的位置 伪代码描述：
int i=first; int j=end; int pivot=r[i] 2. while(i
while((i=pivot))
j--; 比较次数++
r[i]=r[j] 2.3 if(i
while((i
r[j]=r[i] 2.6 if(i
r[i]=pivot; return i ;
时间复杂度：
最好情况下，每次划分对一个记录定位后，该记录的左侧子序列和右侧子序列的长度相同。在具有n 个记录的序列中，对一个记录定位要对整个待划分序列扫描一遍，则所需时间为O
（n ）。时间复杂度为O （nlog2n ）。 最坏情况下，待排序记录序列正序或逆序，每次划分只得到一个比上一次划分少一个纪录的子序列（另一个子序列为空）。此时，必须经过n-1次递归调用才能把所有记录定位，而且第i 趟划分需要经过n-i 次关键码的比较才能找到第i 个记录的基准记录，因此总的比较次数为n （n-1）/2，记录的移动次数小于等于比较次数。因此时间复杂度为O （n2）. 平均情况下，可以用归纳法证明，其数量级也为O （nlog2n ）。
5、简单选择排序
自然语言描述：
（1） 将整个记录划分为有序区和无序区，初始有序区为空，无序区包括所有待排序记录。设置变量index ，记录一次比较中关键码最小的位置。
（2） 第i 趟简单选择排序的待排序区间是r[i]-r[n]，首先将index 设定为当前无序区的第一个位置，然后用r[index]与无序区中其他记录进行比较，若有比r[index]小的记录，就将index 改为这个新的最小的记录的位置。
（3） 如果index 不等于i ，则将它与无序区中第一个记录交换，有序区增加一个记录，无 序区减少一个记录。 （4） 重复（2）（3），直到无序区只剩下一个记录为止。此时所有记录已经按照从小到大
的顺序排好。 伪代码描述：
初始化比较次数compare=0，移动次数move=0
for(int i=1;i
int index=i
for(int j=i+1;j
if(r[j]
if(index!=i)
r[0]=r[i];r[i]=r[index];r[index]=r[0]
move+=3
时间复杂度：待排序序列为正序时，记录的移动次数最少，为0次。在待排序序列为逆序时，记录的移动次数最多为3（n-1）次。
无论记录的初始排列如何，关键码的比较次数相同，第i 趟排序需进行n-1次关键码的比较，而简单选择排序需进行n-1趟排序，则总的比较次数为n （n-1）/2=O（n2）。所以， 总的时间复杂度为O(n2)，这是简单选择排序最好、最坏、和平均的时间性能。
3. 程序运行结果
测试条件：
问题规模的数量级是4，正序逆序由键盘输入，随机数由随机数生成函数生成。
测试结论：
程序对不同序列的数组运用各种不同方法进行排序时均能得到正确的排序结果，同时能够给出正确的比较次数和移动次数。
4. 总结
插入排序：n*n的时间复杂度，稳定排序，原地排序。在数据大部分都排好了，用插入排序会给你带来很大的方便。数据的移动和交换都很少。
希尔排序：n*log(n)的时间复杂度， 非稳定排序，原地排序。主要思想是分治，不过他的分治和合并排序的分治不一样，他是按步长来分组的，而不是想合并那样左一半右一半。 开始
输出测试数组
进行简单插入排序 进行希尔排序
进行起泡排序 进行快速排序
进行简单选择排序 结束
开始步长为整个的长度的一半，然后每组排序。接个步长减为原来的一半在分组排序，直到步长为1，排序之后希尔排序就完成了。这个思路很好，是插入排序的升级版，我觉得他是一个特别好的排序方法了。他的缺点就是两个数可能比较多次，但效率也是很高的。
冒泡排序，n*n的时间复杂度，稳定排序，原地排序。冒泡排序的思想很不错，一个一个比较，把小的上移，依次确定当前最小元素。因为他简单，稳定排序，而且好实现，所以用处也是比较多的。
选择排序，n*n的时间复杂度， 稳定排序，原地排序。选择排序就是冒泡的基本思想，从小的定位，一个一个选择，直到选择结束。和插入排序是一个相反的过程，插入是确定一个元素的位置，而选择是确定这个位置的元素。它的好处就是每次只选择确定的元素，不会对很多数据进行交换。所以在数据交换量上应该比冒泡小。
绛旓細娆″叧閿爜鐨勬瘮杈冨拰n-i 娆¤褰曠殑浜ゆ崲,杩欐牱,鍏抽敭鐮佺殑姣旇緝娆℃暟涓簄 (n-1)/2,璁板綍鐨勭Щ鍔ㄦ鏁颁负3n (n-1)/2骞冲潎鎯呭喌涓,璧锋场鎺掑簭鐨勬椂闂村鏉傚害涓庢渶鍧忔儏鍐靛悓鏁伴噺绾с 4銆佸揩閫熸帓搴 鑷劧璇█鎻忚堪: (1) 鍙栫涓涓褰曚綔涓哄熀鍑,璁剧疆涓や釜鍙傛暟i ,j 鍒嗗埆鐢ㄦ潵鎸囩ず灏嗚涓庡熀鍑嗚褰曡繘琛屾瘮杈 鐨勫乏渚ц褰曚綅缃拰鍙充晶璁板綍浣嶇疆,涔...
绛旓細銆愬疄楠鍐呭銆1.瑙傚療涓庢弿杩颁笅鍒椾箣涓鏍囨湰鍜岃杽鐗囷細鈥斺旂硿妫卞博锛圡423.1锛屽洓宸濆悍瀹氾級鈥斺旂硿妫卞博锛圡423.2锛屽洓宸濆悍瀹氾級2.瑙傚療涓庢弿杩颁笅鍒楁爣鏈細鈥斺斿崈绯滃博锛圡416.1锛屽洓宸濇掣瀹氾級銆愭暀瀛︽彁绀恒戞暀瀛﹁繃绋嬩腑鍙粨鍚堝够鐏墖銆佸綍鍍忕墖鏀炬槧锛屽博鐭宠杽鐗囧濯掍綋鍥惧儚绯荤粺瑙傚療锛岃瑙ｇ熆鐗╃矑鍐呭彉褰紙鏄惧井鏋勯犮佺粍鏋勶級鐗瑰緛銆傘愬涔犱笌鎬...
绛旓細绗竴棰橈細include <iostream.h> include <stdlib.h> void main(){ int a[10],i,s = 0,m = 0,n = 0,j =0,k = 0,p = 0;cout<<"璇疯緭鍏10涓鐢熺殑C++鎴愮哗:"<<endl;for( i = 0;i<=9;i++){ cin>>a[i];s = s+a[i];if(a[i]>100||a[i]<0){ cout<<"杈撳叆闈炴硶!
绛旓細1銆佸湪_鍏堟潵鍏堟湇鍔＄畻娉昣__璋冨害绠楁硶涓紝鎸夌収杩涚▼杩涘叆灏辩华闃熷垪鐨勫厛鍚庢搴忔潵鍒嗛厤澶勭悊鏈恒2銆佽繘绋嬭皟搴︾畻娉曢噰鐢ㄧ瓑鏃堕棿鐗囪疆杞硶鏃讹紝鏃堕棿鐗囪繃澶э紝灏变細浣胯疆杞硶杞寲涓篲鍏堟潵鍏堟湇鍔¤皟搴︾畻娉昣__璋冨害绠楁硶銆3銆佽繘绋嬬殑璋冨害鏂瑰紡鏈変袱绉嶏紝涓绉嶆槸_鍓ュず寮廮__锛屽彟涓绉嶆槸__闈炲墺澶哄紡__銆4銆佽嫢浣垮綋鍓嶈繍琛岃繘绋嬫绘槸浼樺厛绾...
绛旓細(鍏堝皬缁勮璁瀹為獙姝ラ)绛:姝ラ:1銆佺敤姘存Ы鐩涙按;2銆佹妸娌夋诞鎮潗鏂欐斁鍏ユ按涓;3銆佽瀵熺幇璞°傚笀:寮濮嬫寜姝ラ瀹為獙,鍋氬ソ璁板綍,寰楀嚭缁撹?绛:缁撹:钃濇矇銆佺孩鎮侀粍娴傚洓銆佹嫇灞:闂:鍥轰綋浼氭矇娴,娑蹭綋銆佹皵浣撲細涓嶄細娌夋诞?璇蜂妇渚嬭鏄?绛:浼氥1銆侀鐢ㄦ补鍊掑叆鏈夋按鐨勬澂瀛,娌瑰厛娌夊悗娴2銆佺┖姘斾腑澶х殑棰楃矑浼氭矇鍦ㄤ笅闈傞棶:鏄笉鏄...
绛旓細1锛 鍒跺彇姘㈡哀鍖栦簹閾佺殑杩囩▼瑕侀伩鍏嶅皢绌烘皵甯﹀叆婧舵恫涓2锛 娆蹭娇Ni(OH)2 銆丆o( OH)2鍦ㄦ祿姘ㄦ按涓畬鍏ㄦ憾瑙ｏ紝鏈濂藉姞鍏ュ皯閲忓浐浣揘H4Cl 鍥涖佹濊冮璁ㄨ 1锛庤娉曞疄鐜颁笅鍒楃墿璐ㄧ殑杞寲 姘寲浜氶搧鍜屾隘鍖栭搧銆佺～閰镐簹閾佸拰纭吀閾 2FeCl2锛婥l2 锛 2FeCl3 2FeCl3锛婩e 锛 3FeCl2 2Fe2+ +H2O2 + 2H+ =...
绛旓細楂樹腑鐗╃悊鍚堥泦鐧惧害缃戠洏涓嬭浇 閾炬帴锛歨ttps://pan.baidu.com/s/1znmI8mJTas01m1m03zCRfQ ?pwd=1234 鎻愬彇鐮侊細1234 绠浠嬶細楂樹腑鐗╃悊浼樿川璧勬枡涓嬭浇锛屽寘鎷細璇曢璇曞嵎銆佽浠躲佹暀鏉愩佽棰戙佸悇澶у悕甯堢綉鏍″悎闆嗐
绛旓細鍚屾椂鐢熸垚姘寲閽犲拰姘达紝鍙嶅簲鏂圭▼寮忔槸锛歂a2CO3+2HCl鈺2NaCl+H2O+CO2鈫戯紱銆愬疄楠鎷撳睍銆戜緷鎹吀鐨勫寲瀛︽ц川锛岄吀鍙笌杈冩椿娉奸噾灞炪佺⒈銆佺洂銆侀噾灞炴哀鍖栫墿鍙嶅簲锛岃兘浣跨煶钑婂彉鑹诧紝锛1锛変腑浣跨敤浜嗙洂锛岋紙2锛変腑浣跨敤浜嗘寚绀哄墏锛岋紙3锛変腑浣跨敤浜嗙洂锛涘洜姝よ璇佹槑鐩愰吀瀛樺湪锛屽彲鍙栨牱鍝佸姞鍏ヨ緝娲绘臣閲戝睘锛屽锛氶晛銆侀攲绛夛紝...
绛旓細鍐鏁欑増鍥涘勾绾х瀛﹀疄楠岋細璁板繂娓告垙 涓銆瀹為獙棰樼洰锛氳蹇嗘父鎴 浜屻佸疄楠岃姹傦細璁板繂娓告垙01 涓夈佸疄楠屽櫒鏉愶細鎵嬬數绛掋佹鐨佺瑪銆佹枃鍏风洅銆侀杞︺佸鏂欑洊绛夈傚洓銆佹搷浣滄楠わ細1銆佸湪妗屼笂鎽嗘斁鎵鏈夌墿鍝併2銆佸湪10绉掗挓鍐呭敖鍙兘鍦拌浣忔涓婂悇涓墿浣撶殑浣嶇疆銆3銆佽浆杩囪韩锛岀敱鍙︿竴涓悓瀛﹁繀閫熸敼鍙樻涓婄墿浣撳師鏉ョ殑浣嶇疆銆4銆佸啀...
绛旓細杩涜鏈夊叧閾濈殑鎬ц川瀹為獙闇瑕佸皢鍏堕櫎鎺夛紝鎵浠ユ湰棰樼瓟妗堜负锛氶櫎鍘婚摑鐗囪〃闈㈢殑姘у寲鑶滐紱銆愭帰绌惰璁°戯紙1锛夐椈璇ユ皵浣撶殑姘斿懗锛屽彂鐜版病鏈夋皵鍛筹紝鑰屼簩姘у寲纭叿鏈夊埡婵鎬ф皵鍛筹紝鏁呬笉浼氭槸浜屾哀鍖栫～锛涳紙2锛夋哀姘旇兘浣垮甫鐏槦鐨勬湪鏉″鐕冿紝鑰岃瀹為獙涓甫鐏槦鐨勬湪鏉′笉澶嶇噧锛屼娇鐢ㄤ笉鏄哀姘旓紱 妫楠屾阿姘斾娇鐢ㄧ殑鏄敹闆嗘皵浣撶偣鐕冪殑鏂规硶锛...
