《数据结构》实验报告——排序.docx

《数据结构》实验报告 排序

实验题目：

输入十个数，从插入排序， 快速排序， 选择排序三类算法中各选一种编程实 现。 实验所使用的数据结构内容及编程思路：

1. 插入排序：直接插入排序的基本操作是， 将一个记录到已排好序的有序表 中，从而得

到一个新的，记录增一得有序表。

一般情况下，第 i 趟直接插入排序的操作为： 在含有 i-1 个记录的有序子序 列 r[1..i-1 ]中插入一个记录 r[i ]后，变成含有 i 个记录的有序子序列 r[1..i ]； 并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在 r [0]处设置哨兵。在自 i-1 起往前搜索的过程中，可以同时后移记录。整个排 序过程为进行 n-1 趟插入，即：先将序列中的第一个记录看成是一个有序的子序 列，然后从第 2 个记录起逐个进行插入， 直至整个序列变成按关键字非递减有序 序列为止。

2. 快速排序：基本思想是，通过一趟排序将待排记录分割成独立的两部分， 其中一部分记

录的关键字均比另一部分记录的关键字小， 则可分别对这两部分记 录继续进行排序，以达到整个序列有序。

假设待排序的序列为{L.r[s]

,L.r[s+1],…L.r[t]},

首先任意选取一个记录

（通常可选第一个记录L.r[s]）作为枢轴（或支点）（PiVOt ）,然后按下述原则重 新排列其余

记录： 将所有关键字较它小的记录都安置在它的位置之前， 将所有关 键字较大的记录都安置在它的位置之后。 由此可以该 “枢轴”记录最后所罗的位 置 i 作 为 界 线 ， 将 序 列 {L.r[s]

{L.r[i+1],L.[i+2],

， … ， L.r[t]} 分 割 成 两 个 子 序 列

…,L.r[t]}。这个过程称为一趟快速排序，或一次划分。

一趟快速排序的具体做法是：附设两个指针 lOw 和 high ，他们的初值分别 为 lOw 和

high ，设枢轴记录的关键字为 PiVOtkey ，则首先从 high 所指位置起向 前搜索找到第一个关

键字小于 PiVOtkey 的记录和枢轴记录互相交换， 然后从 lOw 所指位置起向后搜索，找到第一个关键字大于 PiVOtkey 的记录和枢轴记录互相 交换，重复这两不直至 low=high 为止。

具体实现上述算法是，每交换一对记录需进行 3 次记录移动(赋值)的操作。 而实际上，

1

在排列过程中对枢轴记录的赋值是多余的， 因为只有在一趟排序结束 时，即 low=high 的位置才是枢轴记录的最后位置。由此可以先将枢轴记录暂存 在 r[0] 的位置上，排序过程中只作

r[low] 或 r[high] 的单向移动，直至一趟排 序结束后再将枢轴记录移至正确位置上。

整个快速排序的过程可递归进行。 若待排序列中只有一个记录， 显然已有序， 否则进行一趟快速排序后再分别对分割所得的两个子序列进行快速排序。

3. 简单选择排序： 其操作为， 通过 n-i 次关键字间的比较， 从 n-i+1 个记录 中选出关

键字最小的记录，并和第i (1≤i ≤n)个记录交换之。

显然，对L.r[1 ???n]中的记录进行简单选择排序的算法为：令i从1至n-1 , 进行 n-1 趟选择操作。 可以看出， 简单选择排序过程中， 所需进行记录移动的操 作次数较少，其最小值为“ 0”最大值为3 (n-1)。然后，无论记录的初始排列 如何，所需进行的关键字之间的比较次数相同，均为 n(n-1)/2 。

程序清单：

1 ．插入排序： #include struct sqlist {int key[11]; int length;

}

insertsort(struct sqlist *l)

{

int i,j;

for(i=2;i<=l->length;i++) if(l->key[i]key[i-1]) {l->key[0]=l->key[i]; l->key[i]=l->key[i-1];

for(j=i-2;l->key[0]key[j];j--) l->key[j+1]=l->key[j]; l->key[j+1]=l->key[0]; }

}

main()

{

int i,j,k;

struct sqlist num; num.length=10;

2

for(i=1;i<=num.length;i++)scanf(\insertsort(&num); printf (“charu ：”)；

for(i=1;i<=num.length;i++)printf(\

}

测试用例：

输入：23 34 12 98 56 45 67 8 9 37

输出： charu ：8 9 12 23 34 37 45 56 67 98

2 快速排序： #include struct sqlist

{

int key[11]; int length; };

int partition(struct sqlist *l,int low,int high)

{

int pivotkey;

l->key[0]=l->key[low]; pivotkey=l->key[low]; while(low

{while(lowkey[high]>=pivotkey)high--; l->key[low]=l->key[high]; while(lowkey[low]<=pivotkey)low++; l->key[high]=l->key[low];

}

l->key[low]=l->key[0]; return low;

}

void qsort(struct sqlist *l,int low,int high) {int pivotloc; if(low

{pivotloc=partition(l,low,high); qsort(l,low,pivotloc-1); qsort(l,pivotloc+1,high); }

}

void quicksort(struct sqlist *l)

3

{

qsort(l,1,l->length);

}

main()

{

int i,j;

struct sqlist num; num.length=10;

for(i=1;i<=num.length;i++)scanf(\printf (“kuaisu ：”)；

for(i=1;i<=num.length;i++)printf(\

}

测试用例：

输入：23 34 12 98 56 45 67 8 9 37

输出： charu ：8 9 12 23 34 37 45 56 67 98

3 选择排序： #include struct sqlist {int key[11]; int length; };

int selectminkey(struct sqlist *l,int a)

{

int i,j=a;

for(i=a;i<=l->length;i++) if(l->key[i]key[j])j=i; return j;

}

void selectsort (struct sqlist *l) {int i,j,k;

for(i=1;ilength;i++) {j=selectminkey(l,i); if(i!=j){k=l->key[i];

l->key[i]=l->key[j]; l->key[j]=k;}

}

}

main()

{

4

int i,j; struct sqlist num; num.length=10;

for(i=1;i<=num.length;i++)scanf(\printf (“xuanze：”)；

for(i=1;i<=num.length;i++)printf(\

}

测试用例：

输入：23 34 12 98 56 45 67 8 9 37

输出： charu ：8 9 12 23 34 37 45 56 67 98

编程感想：

本次编程总共使用了三种排序方法，而这三种编程方法放在一起进行编写时， 很容易就让我们对齐难易程度有了更深刻的了解。

首先，三种排序中，我们都像查表那样，设置了哨兵，而哨兵的使用可以减少 对整个表的验空操作，使程序更加节省空间。

其次，对于插入排序，每次都要对一段序列进行检索，每排一次所要检索的序 列长度减一，其时间发杂度为 0(n ^2)0

接着，对于快速排序，这个程序是比较复杂的，总共是 3 个函数，并且使用了 递归的方法，这是但是，这种算法却是最优越的，平均性能也是最好的，我在编 这个程序时， 对其排序的思想有了进一步的了解， 并努力拿他与冒泡排序进行比 较，看出了些许其优越性。

还有，就是选择排序，简单选择排序思路简单，易于进行，但其时间发杂度与 简单插入排序方法一样，都是 0 (n^2) ，性能不如快速排序。

最后，本次试验是数据结构课的最后一次实验，经过数据结构试验课的锻炼， 使我对数据结构有了更深刻的理解， 对我对其知识起到了重要的影响， 增加了我 编程的实践活动，为我将来进一步学习打下了基础。

5