数据结构课件..ppt

《数据结构课件..ppt》由会员分享，可在线阅读，更多相关《数据结构课件..ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课件内部排序内部排序第一讲2004年12月第十章第十章 内部排序内部排序插入排序:直插入排序直插入排序,希尔排序希尔排序交换排序:冒泡排序，霍尔快速排序冒泡排序，霍尔快速排序选择排序:简单选择排序简单选择排序，堆排序堆排序 归并排序归并排序 基数排序基数排序10-110-1排序的基本概念排序的基本概念一、排序：将若干数据元素构成的一个任意序列，重新排成按关键字有序序列的过程。二、关于排序的二、关于排序的稳定性稳定性：若排序之前若排序之前KiKi=KjKj,并且并且RiRi领先领先RjRj （ijij），），排序后仍排序后仍RiRi领先于领先于RjRj，则排序是稳定的，则排序是稳定的，否

2、则排序是不稳定的。否则排序是不稳定的。三、排序方法分类：1 内排序:在内存进行;2 外排序:在内存进行，同时访问外存;10-110-1排序的基本概念排序的基本概念四、存储结构：顺序存储结构,常称为表。#define MAXSIZE 30;/*表中记录的个数*/Typedef struct int key；/*或其他类型*/./*其他次关键字域*/ElemType;typedef ElemType listtpMAXSIZE；10-2 10-2 插入排序插入排序 一、直接插入排序：一、直接插入排序：思路思路:通过不断的将某记录插入到通过不断的将某记录插入到 一个已经有序的表一个已经有序的表中来实

3、现。中来实现。有一组关键字49，38，76，27，49;i=2 (49)3838,76,27,49 i=3 (38,49),7676,27,49 i=4 (38,49,76),2727,49 i=5 (27,38,49,76),4949 end.(27,38,49,49,76)-直接插入排序算法 nvoid straisort(listtp r);n for(i=2;ik)/*大值的记录后移*/n rj+1=rj;j-;n rj+1=r0;/*插入位置*/n n /*straisort*/-直接插入排序算法 算法分析：算法分析：排序是稳定的排序是稳定的;原来：（49，38，76，27，49）排

4、序后：排序后：(27,38,49,49,76)排时间复杂度为：排时间复杂度为：T(n)=O(nT(n)=O(n2 2)10-3 交换排序一、起泡排序(由小到大）思路:第1趟aj与aj+1比,较大数=aj+1(j=1,.n-1）第2趟aj与aj+1比,较大数=aj+1(j=1,.n-2)第n-1趟a1与a2比,较大数=a2(j=1,n-(n-1)一、起泡排序(由小到大）算法描述：（1）void buble_sort(listtp r)for(i=1;i=n-1;i+)/*共计n-1趟*/for(j=1;jrj+1.key)x=rj;rj=rj+1 rj+1=x;/*bubble_sort*/起泡

5、排序实例图示：排序表长度 n=8初始状态初始状态 第第1 1趟后趟后 第第2 2趟后趟后 第第3 3趟后趟后 第第4 4趟后趟后 第第5 5趟后趟后 第第6 6趟后趟后 49 38 38 38 38 13 49 38 38 38 38 13 1313 38 49 49 49 13 27 38 49 49 49 13 27 2727 65 65 65 13 27 38 65 65 65 13 27 38 3838 97 76 13 27 49 97 76 13 27 49 49 4949 49 76 13 27 76 13 27 4949 4949 4949 4949 13 27 13 27 4

6、949 65 65 65 6565 65 65 65 27 27 4949 76 76 76 76 7676 76 76 76 76 4949 9797 97 97 97 97 9797 97 97 97 97起泡排序改进方法（2）Void bubble_sort2(listtp r)i=1;do bool=1;for(j=1;jrj+1.key)x=rj;rj=rj+1;rj+1=x;bool=0;i+;while(bool=0&i=n-1);/*bubble_sort2*/当某一趟仅有比较比较而无数据交换交换，表明序列已经有序。可以结束排序过程。起泡排序算法分析 时间复杂度：一般情况下：T

7、(n)=0(nT(n)=0(n2 2)当原始序列有序是：T(n)=0(n)T(n)=0(n)起泡排序算法是稳定的。排序算法小结:直接插入排序稳定稳定，时间复杂度为：0(0(n n2 2)交换排序的起泡排序是稳定稳定，一般，时间复杂度为：0(0(n n2 2)当原始序列有序，时间复杂度为：0(n)上一讲内容回顾上一讲内容回顾 排序基本概念排序基本概念插入插入排序排序 直接插入排序直接插入排序 稳定 T(n)=O(n2)希尔排序希尔排序 不稳定 T(n)=n 1.3交换排序交换排序起泡排序起泡排序 稳定 T(n)=O(n2)原表有序时 T(n)=O(n)本讲内容本讲内容交换排序交换排序起泡排序 稳

8、定 T(n)=O(n2)快速排序快速排序 不稳定 T(n)=O(n.log2n)选择选择排序排序 简单选择排序简单选择排序 稳定 T(n)=O(n2)堆排序堆排序 不稳定 T(n)=O(n.log2n)10.3 10.3 交换排序交换排序 二、霍尔快速排序霍尔快速排序 n存储结构：顺序存储结构,常称为表。n#define MAXSIZE 30;/*表中记录的个数*/nTypedef struct n int key；/*或其他类型*/n ./*其他次关键字域*/n ElemType;ntypedef ElemType listtpMAXSIZE；1.霍尔快速排序思路霍尔快速排序思路（1）以以r1.keyr1.key为枢轴，经过比较将:r1r1，r2,rnr2,rn 分成两个子表：.k ki i.k k1 1.k kj j.,左子表关键字=k11.霍尔快速排序思路思路每一趟具体做法：先以第一个关键字为枢轴。设置左右两个 指针分别指向表的两端，i=1 ,j=n。从表的右端开始比较比较(j=n),发生元素移动后，再换到左端比较比较（i），直到 i=ji=j 为止。这就是枢轴元素的最后位置。（2）对各个子表重复第（1）步，直到各子表长度为1为止。