《数据结构》课件-模块四 数据运算-排序

模块四数据运算--排序数据结构排序基本概念SOLVETHEPROBLEM本章我们要解决的问题熟练掌握各种排序方法的基本思想及实现方法。掌握各种排序方法时间复杂度和稳定性的分析方法。掌握各种排序方法在何种情况下使用的分析方法。排序介绍9.1排序基本概念排序（Sorting）是数据处理中一种很重要的运算，同时也是很常用的运算，一般数据处理工作25%的时间都在进行排序。简单地说，排序就是把一组记录（元素）按照某个域的值的递增（即由小到大）或递减（即由大到小）的次序重新排列的过程。将一个包含若干数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列的过程。排序定义B9.1排序基本概念排序按待排序记录所在的位置，可分为：内部排序：待排序记录存放在内存。（本章讲的为内部排序）外部排序：当待排序记录数量很大时，一部分记录需放在外存，在排序过程中就需要对外存进行访问。按照排序过程中依据的原则，把内部排序分为：插入排序

交换排序

选择排序

归并排序

基数排序9.1排序基本概念排序基本操作：将记录从一个位置移动到另一个位置按内部排序过程中所需的工作量，分为:比较两个关键字大小—简单的排序方法，时间复杂度为O(n2)—先进的排序方法，时间复杂度为O(nlog2n)—基数排序，时间复杂度为O(d·n)9.1排序基本概念

稳定排序和不稳定排序:假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，若在排序前的序列中Ri领先于Rj(即i<j)，经过排序后得到的序列中Ri仍领先于Rj，则排序方法是稳定的；反之，是不稳定的。按某种稳定方法对年龄关键字进行排序例：姓名年龄体重1李由57622王天54763七明24754张强24725陈华2453姓名年龄体重3七明24754张强24725陈华24532王天54761李由57629.1排序基本概念按某种不稳定方法对年龄关键字进行排序待排序记录的存储方式：本章所讨论的待排序记录，假定是存放在一组地址连续的存储单元中，即顺序存储方式，可以用一维数组来表示，数组的第0个单元空闲或者作为哨兵单元。姓名年龄体重1李由57622王天54763七明24754张强24725陈华2453姓名年龄体重4张强24723七明24755陈华24532王天54761李由57629.2插入排序插入排序算法：直接插入排序折半插入排序、2-路插入排序希尔排序。9.2插入排序一、直接插入排序1、排序基本操作将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。2、排序基本思想当插入第i(i≥2)个记录时，前面的r[1],r[2],…,r[i-1]已经排好序。这时,将r[i]的关键字依次与r[i-1],r[i-2]…的关键字进行比较，并同时将相关记录位置后移，直到找到插入r[i]的合适位置。3、举例：对序列{49，38，65，97，76，13，27，49}进行直接插入排序。9.2插入排序(49)38659776132749初始关键字：i=2:(38)(3849)659776132749i=3:(384965)9776132749i=4:(38496597)76132749i=5:(76)(3849657697)132749i=6:(13)(133849657697)2749i=7:(27)(13273849657697)49i=8:(49)(1327384949657697)结果9.2插入排序4、直接插入排序算法如下：

voidinerSort(LineListR[],intn){ inti,j; for(i=2;i<=n;++i) if(R[i].key<R[i-1].key) { R[0].key=R[i].key; for(j=i-1;R[0].key<R[j].key;--j) R[j+1]=R[j]；

R[j+1]=R[0]；

}}9.2插入排序直接插入排序的性能分析:(1)空间:只需一个记录的辅助空间r[0].(2)时间:基本运算:比较和移动记录;比较和移动记录的次数与关键字的初始序列有关:(1)待排序序列关键字正序排序:

关键字比较次数:n-1

移动记录的次数:0(2)待排序序列关键字逆序排序:

关键字比较次数:2+3+…+n=(n+2)(n-1)/2

移动记录的次数:3+4+5+…+(n+1)=(n+4)(n-1)/2直接插入排序算法的时间复杂度为O(n2)算法简便，容易实现,适用于待排记录基本有序或待排记录较小时，当待排序记录数n很大时，不宜使用。直接插入排序是一个稳定的排序方法。9.3交换排序1、冒泡排序的基本思想（正序）:首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第n-1个记录和第n个记录的关键字进行过比较为止。然后进行第二趟起泡排序，对前n-1个记录进行同样操作。……结束的条件:(1)趟数为n-1;(2)直到在某趟排序过程中没有进行过交换记录的操作为止。一、冒泡排序9.3交换排序2、举例:有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49`)第一趟:4938659776132749`3849659776132749`3849659776132749`3849659776132749`3849657697132749`3849657613972749`3849657613279749`38496576132749`97第一趟进行7次比较9.3交换排序整个排序过程4938659776132749`38496576132749`97初始关键字第一趟排序后384965132749`76第二趟排序后3849132749`65第三趟排序后3813274949`第四趟排序后13273849第五趟排序后132738第六趟排序后1327第七趟排序后9.3交换排序3、冒泡排序算法如下：

voidBubbleSort(LineListR[],intn){ inti,j; for(i=1;i<n;i++)//i为比较趟数 for(j=1;j<=n-i;j++)//一趟交换排序 if(R[j].key>R[j+1].key)//若逆序

{ R[0]=R[j]; R[j]=R[j+1]; R[j+1]=R[0]; }//用R[0]最为中间变量实现交换}9.3交换排序4、冒泡排序算法的性能分析:(1)空间:只需一个记录的辅助空间.(2)时间:基本运算:比较和移动记录;比较和移动记录的次数与关键字的初始序列有关:(1)待排序序列关键字正序排序:

关键字比较次数:n-1

移动记录的次数:0(2)待排序序列关键字逆序排序:

关键字比较次数:(n-1)+(n-2)+…+1=n(n-1)/2

移动记录的次数:3n(n-1)/2冒泡排序算法的时间复杂度为O(n2)冒泡排序是一个稳定的排序方法9.3交换排序二、快速排序1、快速排序的基本思想:通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。一趟快速排序的具体做法：附设两个指针i和j，i

指向第一个关键字(基准关键字),j指向最后一个关键字。首先从j

所指位置开始向前查找第一个关键字小于key的记录，找到后将其和i所指记录交换。然后再从i

所指位置开始向后查找第一个关键字大于key的记录，找到后将其和j

所指记录交换。重复上述两步，直到i

＝j为止。此时，所有比key

小的关键字都放到左边，所有比

key大的关键字都放到右边。9.3交换排序例:有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49`)9.3交换排序整个快速排序过程:[初始关键字]4938659776132749`第一趟快速排序：{273813}49{76976549`}第二趟快速排序：{13}27{38}{49`65}76{97}结束结束第三趟快速排序：49`{65}结束结束有序序列：1327384949`657697第四趟快速排序：9.3交换排序2、快速排序算法的性能分析:(算法略)快速排序是一个不稳定的排序方法时间复杂度：最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)

最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n²)平均情况T(n)=O(nlog2n)空间复杂度：需栈空间以实现递归

一般情况：O(log2n)如记录的关键字初始排列如下:(5，3，3，4，3，8，9，10，11)9.3希尔排序希尔排序是插入排序的一种，又称为缩小增量排序，是直接插入排序算法的一种更高效率的改进版本。9.3希尔排序从直接插入排序待排序序列基本有序可提高效率待排序序列的记录数n很小时可提高效率希尔排序的基本思想:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序.1、排序过程描述

①取定一个正整数d1<n，把d1作为间隔值，把全部记录从第一个记录起进行分组，所有距离为d1倍数的记录放在一组中，在各组内进行直接插入排序。

②取定一个正整数d2<d1，重复上述分组和排序工作，直至取di=1为止，即所有记录在一个组中进行直接插入排序。③希尔提出的方法是：d1=，di+1=n2di22、举例：对下列关键字进行希尔排序：4938659776132748554取d1＝5，d2＝3，d3＝1。取d1=5一趟分组：49

38

65

97

76

13

27

48

55

4

一趟排序结果：13

27

48

55

4

49

38

65

97

769.3希尔排序取d2=3二趟分组：13

27

48

55

4

49

38

65

97

76二趟排序结果：13

4

48

38

27

49

55

65

97

76取d3=1三趟分组：1344838

274955659776三趟排序结果：4132738

4849

5565

76

979.3希尔排序3、希尔排序算法如下：

voidshellSort(LineListR[],intn){ inti,j,d; d=n/2;//初始步长为表长的一半

while(d>0)//直到d为1 { for(i=d+1;i<=n;++i)//对每组进行直接插入排序

if(R[i].key<R[i-d].key) { R[0].key=R[i].key; for(j=i-d;j>0&&R[0].key<R[j].key;j=j-d) R[j+d]=R[j]；

R[j+d]=R[0]；

} d=d/2;//缩小步长值}}9.3希尔排序4、希尔排序算法分析：

子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序时间复杂度为O(nlog2n)希尔排序是一个不稳定的排序方法9.3希尔排序9.4选择排序基本思想是：每一趟从待排序列中选取一个关键字最小的记录，即第一趟从n个记录中选取关键字最小的记录，第二趟从剩下的n-1个记录中选取关键字最小的记录，继续下去，直到整个序列的记录选完。这样，按照选取记录的顺序将记录重新排列，便得到按关键字有序的序列。分为：直接选择排序和堆排序。9.4选择排序一、直接选择排序1、直接选择排序的算法设计:(1)需进行n-1趟选择操作;(2)第i趟选择操作为:通过n-i次关键字间比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录交换;9.4选择排序2、举例：对序列{42，7，48，15，48，25，18}进行直接选择速排序。9.4选择排序3、直接选择排序算法如下：voidselectSort(LineListR[],intn){ inti,j,index; for(i=1;i<n;++i) { index=i; for(j=i+1;j<=n;++j) if(R[j].key<R[index].key)index=j; if(index!=i) { R[0]=R[i]; R[i]=R[index]; R[index]=R[0]; } } }9.4选择排序4、直接选择速排序算法的性能分析:直接选择排序算法的时间复杂度为O(n2)直接选择排序是一个不稳定的排序方法时间复杂度：移动记录的次数：最好情况0，最坏情况3(n-1).关键字比较次数:∑n-1i=1(n-i)=n(n-1)/29.4选择排序二、堆排序堆的定义:n个元素的序列{k1,k2,...,kn}当且仅当满足下列关系时，称之为堆:关系一：ki<=k2i(或ki>=k2i)关系二：ki<=k2i+1(或ki>=k2i+1)（i=1,2,...,|n/2|)若将和此序列对应的一维数组看成是一个完全二叉树,则堆的含义表明:（1）完全二叉树中所有非叶子结点的值均不大(小)于其左、右孩子结点的值。（2）若序列{k1,k2,...,kn}为堆，则堆顶元素（完全二叉树的根）是序列中的最小(大)值。例1：{96,83,27,38,11,09}96832738119堆顶元素是序列最大值(大根堆)例2：{12,36,24,85,47,30,53}堆顶元素是序列最小值（小根堆）123624854730539.4选择排序堆排序——若在输出堆顶元素之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素中的次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。堆排序要解决两个问题：1、如何由一个无序序列建成一个堆？2、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？问题2的解决:(1)输出堆顶元素;(2)用堆中最后一个元素代替堆顶元素;(3)从堆顶至叶子进行调整(筛选);例:有一个堆如下:1397273849657649`输出1397替代堆顶9713273849657649`筛选2713973849657649`2713493897657649`输出2797替代堆顶结论：对于一个具有n个结点的堆,经过n次输出、n-2次筛选，则可得到一个关键字递增的输出序列；9713493827657649`筛选3813499727657649`38134949`27657697输出3865替代堆顶……97136576273849`49问题1的解决：例:有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49`)4949`6538271376974997653827137649`对97进行筛选对65进行筛选（2）依次对第|n/2|，|n/2|-1,|n/2|-2,…,1个元素进行筛选。4997133827657649`对38进行筛选499713