问题描述

数据结构内部排序实验报告

一、实验目的
1、掌握排序的有关概念和特点。
2、熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。。
3、关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。
二、实验内容
设有关键字序列k={ 12 , 45 , 21 , 12 , 30 , 2 , 68 , 33 },试用各种排序算法进行排序。
三、实验环境
TC或VC++
四、实验步骤
1、从键盘输入上述8个整数，存放在数组quick[8]中，并输出值。
2、输出各种排序算法每一趟排序的结果，观察关键字次序的变化。
（1）直接插入排序算法如下：
void InsertionSort ( SqList &L ) {
// 对顺序表 L 作直接插入排序。
for ( i=2; i<=L.length; ++i )
if (L.r[i].key < L.r[i-1].key) {
L.r[0] = L.r[i]; // 复制为监视哨
for ( j=i-1; L.r[0].key < L.r[j].key; -- j )
L.r[j+1] = L.r[j]; // 记录后移
L.r[j+1] = L.r[0]; // 插入到正确位置
}
} // InsertSort
（2）希尔排序算法如下：
void ShellInsert ( SqList &L, int dk ) {
for ( i=dk+1; i<=n; ++i )
if ( L.r[i].key< L.r[i-dk].key) {
L.r[0] = L.r[i]; // 暂存在R[0]
for (j=i-dk; j>0&&(L.r[0].key
j-=dk)
L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置
L.r[j+dk] = L.r[0]; // 插入
} // if
} // ShellInsert
void ShellSort (SqList &L, int dlta[], int t)
{ // 增量为dlta[]的希尔排序
for (k=0; k
ShellInsert(L, dlta[k]);
//一趟增量为dlta[k]的插入排序
} // ShellSort
（3）冒泡排序算法如下：
void BubbleSort(Elem R[ ], int n) {
i = n;
while (i >1) {
lastExchangeIndex = 1;
for (j = 1; j < i; j++)
if (R[j+1].key < R[j].key) {
Swap(R[j], R[j+1]);
lastExchangeIndex = j; //记下进行交换的记录位置
} //if
i = lastExchangeIndex;
} // while
} // BubbleSort
（4）快速排序算法如下：
int Partition (RedType R[], int low, int high) {
R[0] = R[low]; pivotkey = R[low].key; // 枢轴

while (low
while(low=pivotkey)
-- high; // 从右向左搜索
R[low] = R[high];
while (low
++ low; // 从左向右搜索
R[high] = R[low];
}
R[low] = R[0]; return low;
}// Partition
void QSort (RedType & R[], int s, int t ) {
// 对记录序列R[s..t]进行快速排序
if (s
pivotloc = Partition(R, s, t); // 对 R[s..t] 进行一次划分
QSort(R, s, pivotloc-1);
QSort(R, pivotloc+1, t);
}
} // QSort
（5）简单选择排序的算法描述如下：
void SelectSort (Elem R[], int n ) {
// 对记录序列R[1..n]作简单选择排序。
for (i=1; i
j = SelectMinKey(R, i); // 在 R[i..n] 中选择关键字最小的记录
if (i!=j) R[i]←→R[j]; // 与第 i 个记录交换
}
} // SelectSort
（6）堆排序算法描述如下：
void HeapSort ( HeapType &H ) {
// 对顺序表 H 进行堆排序
for ( i=H.length/2; i>0; --i )
HeapAdjust ( H.r, i, H.length ); // 建大顶堆
for ( i=H.length; i>1; --i ) {
H.r[1]←→H.r[i];

HeapAdjust(H.r, 1, i-1); // 对 H.r[1] 进行筛选
}
} // HeapSort
void HeapAdjust (RcdType &R[], int s, int m)
{

rc = R[s]; // 暂存 R[s]
for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子
if ( j
if ( rc.key >= R[j].key ) break;
R[s] = R[j]; s = j;

}
R[s] = rc;

} // HeapAdjust
（7）归并排序算法描述如下：
void Msort ( RcdType SR[],

RcdType &TR1[], int s, int t ) {
// 将SR[s..t] 归并排序为 TR1[s..t]
if (s= =t) TR1[s]=SR[s];
else
{
m = (s+t)/2;
Msort (SR, TR2, s, m); // 递归地将SR[s..m]归并为有序的TR2[s..m]
Msort (SR, TR2, m+1, t);
Merge (TR2, TR1, s, m, t);
}
} // Msort
3、如果上述8个整数按照升序输入，即k1={ 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 }，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。
4、如果上述8个整数按照降序输入，即k2={ 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2}，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。
5、随机产生3万个数，对其进行排序，观察其结果，并测试各排序算法的执行时间，比较执行效率。
五、问题讨论
1、直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序中哪些是稳定的排序方法，哪些是不稳定的？
2、直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序中哪些排序方法比较次数与初始序列有关，那些无关？
3、在初始序列基本有序的前提条件下，哪种排序方法效率最高？
六、实验报告内容
1、实验目的
2、实验内容和具体要求
3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法
4、程序清单
5、所输入的数据及相应的运行结果
6、问题回答
7、实验心得

解决方案

网上有类似代码，对所有排序的算法写一遍然后每次运行都是有时间统计的，你去下载来改改应该就可以完成这个报告了。 = =我的数据机构期末作业就这么弄弄，糊弄过去了。。。