数据结构课件.优秀PPT.ppt
数据结构课件内部排序内部排序第一讲2004年12月第十章第十章 内部排序内部排序插入排序:直插入排序,希尔排序交换排序:冒泡排序，霍尔快速排序选择排序:简洁选择排序，堆排序 归并排序 基数排序10-110-1排序的基本概念排序的基本概念一、排序：将若干数据元素构成的一个随意序列，重新排成按关键字有序序列的过程。二、关于排序的稳定性：若排序之前Ki=Kj,并且Ri领先Rj（ij），排序后仍Ri领先于Rj，则排序是稳定的，否则排序是不稳定的。三、排序方法分类：1 内排序:在内存进行;2 外排序:在内存进行，同时访问外存;10-110-1排序的基本概念排序的基本概念四、存储结构：依次存储结构,常称为表。#define MAXSIZE 30;/*表中记录的个数*/Typedef struct int key；/*或其他类型*/./*其他次关键字域*/ElemType;typedef ElemType listtpMAXSIZE；10-2 10-2 插入排序插入排序 一、干脆插入排序：思路:通过不断的将某记录插入到 一个已经有序的表中来实现。有一组关键字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*/-干脆插入排序算法 算法分析：算法分析：排序是稳定的排序是稳定的;原来：原来：（4949，3838，7676，2727，4949）排序后：排序后：(27,38,49,49,76)(27,38,49,49,76)排时间困难度为：排时间困难度为：T(n)=O(n2)T(n)=O(n2)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*/起泡排序实例图示：排序表长度 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 4949 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(n)=0(n2)当原始序列有序是：T(n)=0(n)起泡排序算法是稳定的。排序算法小结:干脆插入排序稳定，时间困难度为：0(n2)交换排序的起泡排序是稳定，一般，时间困难度为：0(n2)当原始序列有序，时间困难度为：0(n)上一讲内容回顾上一讲内容回顾 排序基本概念排序基本概念插入排序插入排序 干脆插入排序干脆插入排序 稳定稳定 T(n)=O(n2)希尔排序希尔排序 不稳定不稳定 T(n)=n 1.3交换排序交换排序起泡排序起泡排序 稳定稳定 T(n)=O(n2)原表有序时原表有序时 T(n)=O(n)本讲内容本讲内容交换排序交换排序起泡排序起泡排序 稳定稳定 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=j 为止。这就是枢轴元素的最终位置。（2）对各个子表重复第（1）步，直到各子表长度为1为止。
