【数据结构电子课件】排序.ppt

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

1、概述插入排序快速排序选择排序归并排序基数排序各种内排方法比较第十章内部排序概述排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据表(datalist):它是待排序数据对象的有限集合。主关键字(key):数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据，称为关键字。也称为排序码。排序方法的稳定性:如果在对象序列中有两个对象r[i]和r[j],它们的排序码k[i]==k[j],且在排序之前,对象r[i]排在r[j]前面。如果在排序之后,对象r[i]仍在对象r[j]的前

2、面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。内排序与外排序:内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。内排序分类依不同原则插入排序、交换排序、选择排序、归并排序、和计数排序等。依所须工作量简单排序---时间复杂度o(n2)先进排序方法---时间复杂度o(nlogn)

3、基数排序---时间复杂度o(d.n)插入排序(InsertSorting)基本思想当插入第i(i1)个对象时,前面的V[0],V[1],…,V[i-1]已经排好序。这时,用V[i]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的对象向后顺移。基本思想每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。直接插入排序(InsertSort)直接插入排序过程012345tempi=1i=2012345temp2108

4、254925*162125084925*16252125084925*162125084925*16492125084925*16i=32125084925*1625*2125084925*16i=4i=52125084925*1616162125084925*162125084925*162125084925*1608直接插入排序的算法typedefintSortData;voidInsertSort(SortDataV[],intn){//按非递减顺序对表进行排序SortDatatemp;inti,j;for(i=1

5、;i0;j--)//从后向前顺序比较if(temp

6、序码比较,并且每做1次比较就要做1次数据移动。则总排序码比较次数KCN和对象移动次数RMN分别为在平均情况下的排序码比较次数和对象移动次数约为n2/4。因此，直接插入排序的时间复杂度为o(n2)。直接插入排序是一种稳定的排序方法。折半插入排序(BinaryInsertsort)基本思想设在顺序表中有一个对象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已经排好序的对象。在插入V[i]时,利用折半搜索法寻找V[i]的插入位置。折半插入排序的算法typedefintSortData;v

7、oidBinInsSort(SortDataV[],intn){SortDatatemp;intLeft,Right;for(inti=1;i=Left;k--)V[k+1]=V[k];//记录后移V[Left]=temp;//插入}}折半插入排序01234

8、5tempi=1i=2012345temp52133i=35521532144i=4215388i=52153161684421384516折半搜索比顺序搜索查找快,所以折半插入排序就平均性能来说比直接插入排序要快。它所需的排序码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。在插入第i个对象时,需要经过