文档介绍：1．实验要求
【实验目的】
　学****实现、对比各种排序算法,掌握各种排序算法的优劣，以及各种算法使用的情况。
【实验内容】
使用简单数组实现下面各种排序算法,并进行比较。
排序算法：
　　 ﻩﻩ1、插入排序
ﻩﻩ２、希尔排序
3、冒泡排序
4、快速排序
５、简单选择排序
6、堆排序(选作）
7、归并排序(选作）
８、基数排序（选作)
9、其他
要求：
ﻩﻩ1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为３次移动)。
３、对于这三类数据，比较上述排序算法中不同算法的执行时间,精确到微秒（选作)
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度
编写测试maiｎ（)函数测试线性表的正确性。
2。程序分析
２。1 存储结构
　存储结构：数组
r1≤r2≤ … … ≤ri-1 ri ri+1 … … rn
有序区无序区
图8-1 直接插入排序的基本思想图解
插入到合适位置
关键算法分析
//插入排序
ｖoｉｄ InseｒtSｏｒt(inｔｒ[］， iｎt　n)
｛ﻩ
ﻩinｔ cｏunt１＝0,coｕnt2＝0；
ﻩfor （int　ｉ=２；　i〈n; i++）
ﻩ{
ﻩﻩr[0］=r［i］;　　　　　　　　　 /／设置哨兵
ﻩﻩfor （ｉnt j=i—1；ｒ［０］＜r［j]; j——）　 //寻找插入位置
ﻩﻩﻩｒ［ｊ+1］=r［j］; 　　　　　／/记录后移
ﻩﻩr[ｊ+1]=r［０]；
ﻩ cｏunt1++；
ﻩﻩｃounｔ2＋+；
ﻩ｝
ﻩｆｏr（ｉnt　ｋ=1；ｋ〈n；k＋+）
ﻩﻩcｏｕｔ〈〈ｒ[k]<〈” ＂；
ﻩcｏuｔ<〈endｌ；
ﻩcout<〈＂比较次数为 "〈<count１＜<＂移动次数为 "＜＜ｃｏunt２<〈endl；
}
/／希尔排序
voｉd ShelｌSort(int r［］，　iｎt n）
{
ﻩｉｎｔｉ;
ﻩｉnt d；
ﻩiｎt　j；
ﻩiｎt cｏunｔ1=0，ｃｏunｔ２＝0;
　　 fｏｒ (d＝ｎ/2；ｄ＞＝1; ｄ=d/２）　　　 //以增量为d进行直接插入排序
ﻩ｛
ﻩﻩfｏr （i=ｄ＋１; i＜n；　ｉ++）
ﻩﻩ｛
ﻩﻩﻩｒ［０]=r［i］；　　　　　　　／／暂存被插入记录
ﻩﻩﻩfor　（ｊ=i－ｄ；　j〉0　＆& ｒ[0］＜ｒ［j]； j＝j—d）
ﻩﻩﻩﻩr［ｊ＋ｄ]=r[j]; 　　　//记录后移d个位置
ﻩﻩﻩr[j+ｄ］=r［0];
ﻩﻩﻩcouｎt１＋+;
ﻩﻩcｏunt2=couｎｔ２+d;
ﻩﻩ｝
ﻩﻩcouｎt１++;
ﻩ｝
ﻩfoｒ(i=１；i＜n；i+＋）
ﻩcouｔ〈〈r[ｉ］〈〈”　"；
ﻩｃout<〈endl;
ﻩcｏut<<＂比较次数为＂＜<coｕnｔ１<〈” 移动次数为　”〈<counｔ２<〈endl;
｝
r1≤r2≤ … … ≤ri-1 ri ri+1 … … rn
有序区无序区
图8-1 直接插入排序的基本思想图解
插入到合适位置
//起泡排序
voｉd ＢｕbbｌeSoｒt（ｉnt r［],　inｔ n)
｛
ﻩint temp；
ﻩinｔ excｈａnge；
ﻩｉnt boｕnd；
ﻩｉｎｔｃount1=0,couｎt2=0;
　 exｃｈanｇｅ=ｎ—1;　　　　　　　　　／／第一趟起泡排序的范围是r[1］到ｒ[n］ﻩ
ﻩwｈilｅ（exchange）　　　　 /／仅当上一趟排序有记录交换才进行本趟排序
ﻩ{
ﻩﻩｂound=excｈａngｅ；
ﻩﻩexchange=0；　
ﻩ　ｆoｒ（int　j=0；j＜ｂounｄ;ｊ++) ﻩﻩﻩ ／／一趟起泡排序
ﻩﻩ｛
ﻩﻩﻩcount１＋+;ﻩ ﻩﻩ ﻩﻩﻩ//接下来有一次比较
ﻩﻩﻩｉf（r［ｊ］>r［j＋１］）
ﻩﻩﻩ{
ﻩﻩ ﻩteｍp＝r[j]；ﻩﻩﻩﻩﻩﻩﻩ//交换r［ｊ]和r[j＋1]
ﻩ ﻩr［j]=ｒ[j+1］；
ﻩﻩﻩﻩr［j＋1］=ｔｅmp；
ﻩﻩﻩeｘｃhange＝j;ﻩﻩﻩﻩﻩﻩﻩ//记录每一次发生记录交换的位置