数据结构第03章-排序课件.ppt

1、数据结构（数据结构（C+版）版）n 第1章 绪论 第2章 线性表 第3章 排序 第4章 串 第5章 栈与队列 第6章 数组和广义表 第7章 树和二叉树 第8章 查找 第9章 图 第10章 综合应用设计第3章 排序 3.1 排序的基本概念 3.2 插入排序 3.3 交换排序 3.4 选择排序 3.5 归并排序数据结构（C+版）叶核亚3.1 排序的基本概念1数据序列数据序列（datalist）是待排序的数据元素的有限集合。2关键字通常数据元素由多个数据项组成，以其中某个数据项作为排序依据，则该数据项称为关键字（key）。3排序算法的性能评价排序算法的时间复杂度：指算法执行中的数据比较次数、数据移动

2、次数与待排序数据序列的元素个数n之间的关系。排序算法的空间复杂度：指算法执行中，除待排序数据序列本身所占用的内存空间外，需要的附加内存空间与待排序数据序列的元素个数n之间的关系。数据结构（C+版）叶核亚4排序算法的稳定性在数据序列中，如果有两个数据元素ri和rj，它们的关键字ki等于kj，且在未排序时，ri位于rj之前。如果排序后，元素ri仍在rj之前，则称这样的排序算法是稳定的（stable），否则是不稳定的排序算法。5内排序与外排序内排序：在待排序的数据序列中，数据元素个数较少，整个排序过程中所有的数据元素都可以保留在内存，则这样的排序称为内排序。外排序：待排序的数据元素非常多，以至于它们

3、必须存储在磁盘等外部存储介质上，则这样的排序称为外排序。显然，外排序过程中需要多次访问外存。数据结构（C+版）叶核亚3.2 插入排序插入排序（insertion sort）的基本思想是：每趟将一个待排序的数据元素，按其关键字大小，插入到已排序的数据序列中，使得插入后的数据序列仍是已排序的，直到全部元素插入完毕。3.2.1 顺序表的直接插入排序3.2.2 单链表的直接插入排序3.2.3 希尔排序数据结构（C+版）叶核亚3.2.1 顺序表的直接插入排序518765432table(a)k=5，i=1，插入535(b)k=3，在子序列5中查找，i=1，5向后移动,插入3253(c)k=2，在3，5中

4、查找，i=1，3,5向后移动,插入227543(e)k=7,在2，3，4，5中查找，i=5，插入7(f)k=1，在2，3，4，5，7中查找，i=1，2,3,4,5,7向后移动,插入11754322543(d)k=4，在2，3，5中查找，i=3，5向后移动,插入4序号iiiiii1234521数据结构（C+版）叶核亚例3-1 顺序表的直接插入排序的算法设计与实现。#include#include /其中定义随机数函数void output(int table,int n)/输出数组的n个元素 cout table:;for(int i=0;in;i+)couttablei ;coutendl;v

5、oid insertsort(int table,int n)/n个随机数直接插入排序 /已排序数据存放在table数组 for(int i=0;in;i+)/n-1趟排序，依次插入n-1个数 int k=rand()%20;/产生一个020之间的随机数 coutk=kt ;数据结构（C+版）叶核亚直接插入排序算法分析1.直接插入排序的平均比较次数为 2.平均移动次数为3.直接插入排序的时间复杂度为O(n2)。4.直接插入排序算法是稳定的。ninnniC12241434121ninnniM1244)1(2数据结构（C+版）叶核亚3.2.2 单链表的直接插入排序 1 4 3 (d)中间插入qph

6、ead(a)空表插入 1 head(b)头插入 2head 1 q 2(c)尾插入 2head 1 3 pqhead数据结构（C+版）叶核亚单链表直接插入排序#include /包含rand函数#include Onelink.h /单链表类void insert_sorted(Onelink&h1,int k)/k值插入已排序的单链表h1 /引用类型参数 OnelinkNode*t=new OnelinkNode(k);/创建k值结点t if(h1.head=NULL)/空表插入 h1.head=t;/改变单链表的头指针 else if(kdata)/表头插入 t-next=h1.head;

7、h1.head=t;/改变单链表的头指针 else /表中、表尾插入数据结构（C+版）叶核亚3.2.3 希尔排序图3-3 希尔排序算法描述8561972318765432table87639521jj+jumpi(a)jump=4(b)jump=2,j=1,交换jj+jump27639581jj+jumpi(d)jump=2,j=4,交换123416543227639581jj+jumpi(c)jump=2,j=2,不交换,j=3,不交换27659381jj+jump18765432i(e)jump=2,j=5,交换27956381jj+jumpi(f)jump=2,j=3,交换2795836

8、1ji(g)jump=2,j=6,不交换j+jump19876532(h)jump=11654327序号数据结构（C+版）叶核亚希尔排序算法描述希尔排序算法共有三重循环最外层循环while语句控制增量jump，初值为数组长度n的一半，以后逐次减半（jump=jump/2），直至为1。中间循环for语句进行一轮相隔jump的元素进行比较、交换。最内层循环while语句，设j是数组元素的下标，将元素tablej与相隔jump的元素tablejjump进行比较，如果两者是反序的，则执行swap(table,j,j+jump)交换两个元素。重复往前与相隔jump的元素再比较、交换，j=jjump，当t

9、ablejtablej+jump时，表示该元素tablej已在这趟排序后的位置，不需交换，则退出最内层循环。数据结构（C+版）叶核亚希尔排序算法 void swap(int table,int i,int j)/交换tablei、tablej的值 int temp=tablei;tablei=tablej;tablej=temp;void shellsort(int table,int n)/对table数组元素进行希尔排序 int jump=n/2;while(jump0)/控制增量，一趟排序 for(int i=jump;i=0)数据结构（C+版）叶核亚3.3 交换排序3.3.1 冒泡排序

10、3.3.2 改进的冒泡排序3.3.3 快速排序数据结构（C+版）叶核亚3.3.1 冒泡排序void bubblesort1(int table,int n)/对table数组元素进行冒泡排序 for(int i=0;in-1;i+)/n-1趟排序 for(int j=0;jtablej+1)swap(table,j,j+1);/反序时，交换 cout第i趟;output(table,n);时间复杂度为O(n2)，空间复杂度为O(1)。数据结构（C+版）叶核亚3.3.2 改进的冒泡排序1567843218765432table(a)第1趟，i=1,从index到n-i+1的相邻位置元素比较、交换

11、交换index交换交换18567432(b)第2趟，i=2,从index到n-i+1的相邻位置元素比较、交换交换index交换n-i+1n-i+118756432(c)第3趟，i=3，比较、交换交换indexn-i+118765432(d)第3趟，i=4，比较,没有交换，已排序indexn-i+1序号数据结构（C+版）叶核亚改进的冒泡排序算法void bubblesort2(int table,int n)/改进的冒泡排序算法 int i=0,j=0,index=0;bool exchange=true;/是否交换的标记 while(in-1&exchange)/最多n-1趟排序 exchan

12、ge=false;/假定元素未交换 j=index;/起始比较位置 while(jtablej+1)swap(table,j,j+1);/反序时，交换 exchange=true;/更改交换标记 数据结构（C+版）叶核亚3.3.3 快速排序5713842618765432table(a)vot=5，tablejvot，不移动，j-i j17685423(i)i+，j-，分成两个子序列（left,j）与(i,right)ijrightleft57138426(b)vot=5，tablejvot，将tablei值赋给tablej，j-ijrightleft17638426(d)vot=5，tabl

13、ejvot，将tablej值赋给tablei，i+ij17638423(e)vot=5，tableivot，i+ij17638423(f)vot=5，tableivot，将tablei值赋给tablej，j-17688423(h)i=j，将vot值赋给tableiij序号数据结构（C+版）叶核亚快速排序算法设计const int N=8;void quicksort(int table,int left,int right)/实现一趟快速排序 int i,j,vot;if(leftright)/左边界小于右边界，序列有效 i=left;j=right;vot=tablei;/第一个值作为基准值

14、 while(i!=j)/进行一轮比较 while(vottablej&ij)j-;/从右向左寻找较小值 if(ij)数据结构（C+版）叶核亚快速排序算法分析1.快速排序的平均比较次数为O(nlog2n)，时间复杂度为O(nlog2n)。2.由于快速排序是递归算法，系统调用时需要设立一个栈（stack）存放参数，最大递归调用层次数为。因此，算法的空间复杂度为O(nlog2n)。数据结构（C+版）叶核亚3.4 选择排序3.4.1 顺序表的直接选择排序3.4.2 单链表的直接选择排序数据结构（C+版）叶核亚3.4.1 顺序表的直接选择排序void selectsort(int table,int

15、n)/对table数组元素进行选择排序 for(int i=0;in-1;i+)/n-1趟排序 int min=i;for(int j=i;jn;j+)/在从tablei开始的部分数组元素中 if(tablejtablemin)/寻找最小值 min=j;/min记下本趟最小值的下标 if(i!=min)swap(table,i,min);/本趟最小值交换到左边 coutin-1:minmin=tableminnext;q=h1.head;while(p!=NULL)if(p-data data)/比较,min记住最小值位置 minprior=q;/minprior是min的前驱结点数据结构（C

16、+版）叶核亚3.5 归并排序所谓归并，就是将两个已排序的数据序列合并，形成一个已排序的数据序列，又称两路归并。3.5.1 顺序表的归并排序 3.5.2 单链表的归并排序数据结构（C+版）叶核亚3.5.1 顺序表的归并排序 数据结构（C+版）叶核亚顺序表的归并排序算法const int N=10;void output(int table,int n);void onemerge(int x,int y,int m,int r,int n1)/一次归并 /将x中相邻的两个子序列归并到y中 int i=m,j=r,k=m;while(ir&jr+n1&jN)coutxixj?;if(xidata q-data)/比较两个单链表第1个结点的值数据结构（C+版）叶核亚实习31实习目的：学习多种排序算法，灵活运用排序算法解实际问题。2题意（1）九宫排序问题在一个方框盘中放上8个方块，分别写上1，2，8，另有一个位置空着，如图3.12（a）所示。做此游戏时，只能将与空格相邻的方块移入空格内。要求对任意给定的初始状态，判断是否能够移成如图3.12（b）的目标状态，若能则给出移动步伐，否则输出不能移动信息。图3.12 九宫排序图数据结构（C+版）叶核亚