【精品数据结构】排序算法.ppt

《【精品数据结构】排序算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章排序算法1§10.1概述排序的主要目的是便于以后在已排序的集合中查找检索某一成员若干概念关键字排序排序的稳定性内排序外排序多键排序2§10.1概述排序方法进行分类插入排序交换排序选择排序归并排序分配排序3§10.1概述算法的时间复杂性通常只考虑键值的比较次数和记录的移动次数评价排序的另一个主要标准是执行算法所需的附加空间4§10.2插入排序插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。5§10.2.1直接插入排序初始键值序列[46]58154590181062i=2[4

2、658]154590181062i=3[154658]4590181062i=4[15454658]90181062i=5[1545465890]181062i=6[151845465890]1062i=7[10151845465890]62i=8[1015184546586290]图10‑1直接插入排序过程示例6§10.2.1直接插入排序可以将插入排序粗略地描述为：SortInsertion(inta[],longn){for(i=1;i

3、tion(inta[],longn){intx,i,,j;for(i=1;i=0&&x

4、记录集的一端移动，键值较小的记录向另一端移动。10§10.3.1冒泡排序设初始记录集为2030104533225550则第一趟冒泡的过程为：2030104533225550//20与30比较，未交换2010304533225550//30与10比较，交换2010304533225550//30与45比较，未交换2010303345225550//45与33比较，交换2010303322455550//45与22比较，交换10303322455550//45与55比较，未交换2010303322455055//55与50比较，交换11§10.3.1冒泡排

5、序每趟的结果1020302233455055//第2趟1020223033455055//第3趟1020223033455055//第4趟1020223033455055//第5趟1020223033455055//第6趟1020223033455055//第7趟1020223033455055//第8趟12§10.3.3快速排序(一)基本思想基本思想是：在待排序的n个记录中任取一个记录（例如就取第一个记录），以该记录的键值为标准，将所有记录分为两组（一般都是无序的），使得第一组中各记录的键值均小于或等于该键值，第二组中各记录的键值均大于该键值。然后把

6、该记录就排在这两组的中间（这也是该记录最终的位置）。此称为一趟分割，对所分成的两组再分别重复上述方法，直到所有记录都排在适当位置为止。13§10.3.3快速排序(二)分割算法一趟快速排序的具体做法是：设两个指针i和j，它们的初值分别为0、n-1，且把a[0]送入工作单元x中保存（选第一个记录为标准），然后比较a[j]和x，若a[j]>x，则j减1后继续与x比较，直至r[j]＜=x，然后，将a[j]移至a[i]的位置，令i加1，接着进行a[i]和x的比较，若a[i]

7、，令j减1，之后，重复上述过程，直至i==j。此时i便是记录x所应在的位置。14§10.3.3快速排序(二)分割算法longSortPartition(ina[],longp1,longp2);{//对a[p1]—a[p2]进行分割，返回分割点longi,j;intx;i=p1;j=p2;x=a[i];15§10.3.3快速排序(二)分割算法while(ix&&i

8、x;returni;}16§10.3.3快速排序(二)分割算法初始关键字70736923931