数据结构之排序算法操作论文Word格式文档下载.doc
《数据结构之排序算法操作论文Word格式文档下载.doc》由会员分享，可在线阅读，更多相关《数据结构之排序算法操作论文Word格式文档下载.doc（7页珍藏版）》请在冰点文库上搜索。
如：
学生成绩往往需要按照成绩高低或按学号从前到后排序；
在图书馆众多的图书中，需要按照各个学科将书籍归类；
排队时从高到低的顺序排队等问题。
同样，排序也是计算机程序设计中的一个非常重要的操作，在计算机软件设计中占有极其重要的地位。
本文将对排序算法中直接插入排序、快速排序和简单选择排序三种算法的实现做一些研究。
2.算法的实现
直接插入排序算法中，第i趟进行的操作为：
在含有i-1个记录的有序子序列r[1…i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r[1….i]；
并且为了在查找插入位置的过程中避免数组下标出界，在r[0]处设置监视哨，在自i-1起往前搜索的过程中，可以同时后移记录。
算法1直接插入排序算法
Step1:
从第二个记录起逐个进行关键字与前面关键字的比较并判断是否把该记录作为哨兵
for（i=2;
i<
=L.length;
++i）
if（LT（L.r[i].key,L.r[i-1].key））
L.r[0]=L.r[i];
//若“<
”，将L.r[i]复制为哨兵
Step2:
在进行关键字比较的同时后移记录
for（j=i-1;
LT（L.r[0].key,L.r[j].key）;
--j）
L.r[j+1]=L.r[j];
//记录后移
Step3:
把记录插入到正确的位置
L.r[j+1]=L.r[0];
//插入到正确位置
快速排序算法中，一趟快速排序的具体作法为：
附设两个指针low和high，他们的初值分别为low和high，设枢轴的关键字为pivokey，则首先从high所指位置起向前搜索找到第一个关键字小于pivokey的记录和枢轴记录相互交换，然后从low所指位置起向后搜索，找到第一个关键字大于的pivokey记录和枢轴记录相互交换，重复这两步直至low=high为止。
算法2.1一趟快速排序算法
选取一个记录作为枢轴，并把关键字附给pivokey
L.r[0]=L.r[low];
//用子表的第一个记录作枢轴记录
pivotkey=L.r[low].key;
//枢轴记录的关键字
从high所指位置起向前搜索找到第一个关键字小于pivokey的记录和枢轴记录相互交换,同时把比枢轴小的记录移到低端
while（low<
high&
&
L.r[high].key>
=pivotkey）--high;
L.r[low]=L.r[high]；
//将比枢轴记录小的记录移到低端
从low所指位置起向前搜索找到第一个关键字大于pivokey的记录和枢轴记录相互交换,同时把比枢轴小的记录移到高端
L.r[low].key<
=pivotkey）++low;
L.r[high]=L.r[low]//将比枢轴记录大的记录移到高端
Step4:
当low=high时，把枢轴记录移到位，并且返回枢轴位置
L.r[low]=L.r[0]//枢轴记录到位
returnlow//返回枢轴位置
算法2.2递归快速排序算法
通过调用QSort函数把整个顺序表一分为二
QSort（L,1,L.length）;
把子表再一分为二，然后分别对低子表和高子表进行划分
pivotloc=Partition（L,low,high）;
//将L.r[low...high]一分为二
QSort（L,low,pivotloc-1）;
//对低子表递归排序
QSort（L,pivotloc+1,high）;
//对高子表递归排序
简单选择排序中，第i趟进行的操作为：
从第i+1个记录到第n个记录中选一个关键字最小的记录，然后与第i个记录进行交换。
算法3简单选择排序算法
从个i+1记录开始从中选一个关键字最小的记录
for（i=1;
L.length;
++i）{//i为选择区间下界
j=i;
//j指向当前的初始记录
for（k=i+1;
k<
++k）
if（L.r[k].key<
L.r[j].key）
j=k;
//让j指向当前最小的记录
将找到的最小的记录与第i个记录交换
if（i!
=j）
L.r[i]«
L.r[j];
//与第个i记录交换
3.算法分析
3.1直接插入排序
从时间复杂度方面来看：
当初始记录的关键字序列按非递减有序时，所需进行的关键字间的比较次数达到最小值n-1，记录不需移动；
反之当初始记录的关键字序列按非递增有序时，总的比较次数达到最大值（n+2）（n-1）/2,记录移动的次数也达到最大值（n+4）（n-1）/2。
而初始记录是随机的，则取上述最大值和最小值的平均值作为直接插入排序的时所需进行关键字间的比较次数和移动记录的次数，约为n2/4。
3.2快速排序
从时间复杂度方面来看：
最好的情况是每次划分得到的两个子序列的长度大致相等，在这种情况下排序过程所需要的比较次数为O（n·
log2n），最坏的情况是，每次划分得到的子序列有一个为空，而另一个长度为n-1,此时需要进行n-1趟快速排序，整个过程的比较次数为：
n（n-1）/2。
3.3简单选择排序
在一趟排序中关键字的比较次数为n-1次，在第二趟排序中关键字的比较次数为n-2次，………第i趟排序中关键字的比较次数为n-i次，总的比较次数为n（n-1）/2。
而在各次排序中，记录的移动次数最好的情况是该记录正好处于合适的位置上，不需要移动，此时移动次数为0次，最坏的情况需要交换记录的位置，此时的移动次数为3次，所以总的移动次数最好为0次，最坏为3（n-1）次，由此可知，简单选择排序的时间复杂度为O（n2）。
从空间复杂度方面来看：
简单选择排序在交换记录时需要一个记录大小的缓存空间，所以其空间复杂度为O
（1）。
4.应用举例
假设待排序的记录的关键字序列为：
49,38,65,97,76,13,27,49’，排序以后的记录按关键字非递减有序
4.1直接插入排序的基本思想：
每次将待排序的一个记录按其关键字大小插入到已经排好序的子序列中，直到所有的记录都插入完为止。
直接插入排序的过程如图2.1所示：
[初始关键字]（49）38659776132749’
i=2:
（38）（3849）659776132749’
i=3:
（38）（384965）9776132749’
i=4:
（38）（38496597）76132749’
i=5:
（76）（3849657697）132749’
i=6:
（13）（133849657697）2749’
i=7:
（27）（13273849657697）49’
i=8:
（49’）（1327384949’657697）
监视哨L.r[0]
图2.1
4.2快速排序的基本思想：
通过一趟排序将待排序记录分割成独立的两部分，其中一部分的记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序以达到整个序列有序。
整个排序过程采用递归方式，一趟快速排序过程如图2.2（a）图所示：
pivotkey
初始关键字4938659776132749’
ijj
进行1次移动后27386597761349’
iij
进行2次移动后 27389776136549’
ijj
进行3次移动后27381397766549’
iij
进行4次移动后27381376976549’
ijj
完成一趟排序 2738134976976549’
图2.2（a）
排序的全过程如图2.2（b）所示：
初始状态{4938659776132749’}
一次划分之后{273813}49{76976549’}
分别进行快速排序{13}27{38}
结束结束{49’65}76{97}
49’{65}结束
结束
有序序列{1327384949’657697}
图2.2（b）
4.3简单选择排序的基本思想：
每一趟在n-i+1（i=1,2,……,n-1）个记录中选取关键字最小的记录作为有序序列中的第i个记录，并和第i（0<
i<
n+1）个记录交换。
简单选择排序的过程如图2.3所示：
49 38 65 97 76 13 27 49’
第1趟13 38 65 97 76 49 27 49’
第2趟 13 27 65 97 76 49 38 49’
第3趟 13 27 38 97 76 49 65 49’
第4趟 13 27 38 49 76 97 65 49’
第5趟 13 27 38 49 49’ 97 65 76
第6趟 13 27 38 49 49’ 65 97 76
第7趟 13 27 38 49 49’ 65 76 97
图2.3
5.结束语
本文中讨论的排序的初始序列都是建立在静态顺序存储结构基础上的，所以排序过程中产生了大量的记录移动，从而导致系统空间开销很大，时间耗费也很大。
因此，可以采用静态链表或动态链表作存储结构，以提高整个排序算法的效率。
可以把本文中快速排序中用到的递归算法改为非递归形式，降低排序算法的空间复杂度。
参考文献：
[1]严蔚敏,吴伟明.数据结构（C语言版）,清华大学出版社，1997.
[2]谭浩强.C程序设计，清华大学出版社，2000.
升级会员 