各种经典排序算法.ppt

排排 序序本节基本内容与要求本节基本内容与要求o基本内容基本内容n顺序查找、二分查找、二叉树查找以及散列表上查找顺序查找、二分查找、二叉树查找以及散列表上查找 及算法思想及算法思想n排序的基本概念以及选择、插入、交换和归并四类排排序的基本概念以及选择、插入、交换和归并四类排序的基本思想和算法序的基本思想和算法o要求要求n掌握线性表、树和散列表掌握线性表、树和散列表(或称哈希表或称哈希表)的查找方法及的查找方法及算法实现以及各种查找方法的应用算法实现以及各种查找方法的应用n熟练掌握选择、插入、交换和归并四类排序的基本思熟练掌握选择、插入、交换和归并四类排序的基本思想和算法想和算法排排 序序1.4 内部排序内部排序一、基本概念一、基本概念二、插入排序二、插入排序三、交换排序三、交换排序四、选择排序四、选择排序五、归并排序五、归并排序排排 序序一、基本概念一、基本概念1.排序的功能排序的功能：将一个数据元素（或记录）：将一个数据元素（或记录）的的任意序列任意序列，重新排成一个按关键字，重新排成一个按关键字有序有序的序列。的序列。例如例如：下列是一组记录对应的关键字序列下列是一组记录对应的关键字序列(52,49,80,36,14,58,61,23,97,75)调整为调整为(14,23,36,49,52,58,61,75,80,97)排排 序序2.排序的定义排序的定义假设含假设含n个记录的序列为个记录的序列为 R1,R2,，Rn 其相应的关键字序列为其相应的关键字序列为 K1,K2,，Kn 这些关键字相互之间可以进行比较，即在这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系它们之间存在着这样一个关系：Kp1Kp2Kpn按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1,Rp2,，Rpn 的操作称作的操作称作排序排序。排排 序序3、排序的基本操作、排序的基本操作o排序的概念：排序的概念：就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。o排序过程的组成步骤排序过程的组成步骤：首先比较两个关键字的大小；然后将记录从一个位置移动到另一个位置。n对记录的关键字大小进行比较n将记录从一个位置移动到另一个位置o当待排序记录的关键字均不相同时，则排序结果是唯一的，否则排序的结果不一定唯一。排排 序序4、排序的稳定性、排序的稳定性若有：若有：R1,.,Ri,.,Rj,.且关键字：且关键字：Ki=Kj ij排序后：排序后：Ri,Rj,.则称该排序结果具有稳定性。则称该排序结果具有稳定性。在待排序的文件中，若存在在待排序的文件中，若存在多个关键字相同的记录，经多个关键字相同的记录，经过排序后这些具有相同关键过排序后这些具有相同关键字的记录之间的字的记录之间的相对次序相对次序保保持持不变不变，该排序方法是，该排序方法是稳定稳定的；的；若具有相同关键字的记录之若具有相同关键字的记录之间的间的相对次序相对次序发生发生变化变化，则，则称这种排序方法是称这种排序方法是不稳定不稳定的。的。排排 序序o内部排序内部排序：是指在排序的整个过程中，：是指在排序的整个过程中，数据数据全部存放全部存放在计算机的在计算机的内存内存储器里，并且在内存储器里调整数据储器里，并且在内存储器里调整数据的位置；的位置；o当文件很大以致内存不足以存放全部数据时，在排序当文件很大以致内存不足以存放全部数据时，在排序过程中需要对过程中需要对外存外存进行存取访问，称这种借助于外存进行存取访问，称这种借助于外存储器进行排序的方法为储器进行排序的方法为外部排序外部排序。o注意：注意：n 内排序适用于记录个数不很多的小文件内排序适用于记录个数不很多的小文件n 外排序则适用于记录个数太多，不能一次将其外排序则适用于记录个数太多，不能一次将其全部记录放入内存的大文件。全部记录放入内存的大文件。5、排序的分类、排序的分类排排 序序 o每次将一个待排序的记录，按其关键字大小插入到前面每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入已经排好序的子文件中的适当位置，直到全部记录插入完成为止。完成为止。o把新元素（未排序的元素的关键字）逐个插入正在增长把新元素（未排序的元素的关键字）逐个插入正在增长的顺序表中。的顺序表中。o寻找插入位置的方法寻找插入位置的方法：n线性插入排序线性插入排序n对半插入排序对半插入排序n希尔排序希尔排序二、插入排序二、插入排序排排 序序有序序列L.r1.i-1L.ri无序序列 L.ri.n有序序列L.r1.i无序序列 L.ri+1.n1、线性插入排序、线性插入排序o基本思想：基本思想：每步将一个待排序的元素按其大小插入到前每步将一个待排序的元素按其大小插入到前面已排序的数据中的适当位置。面已排序的数据中的适当位置。重复该工作，直至有序重复该工作，直至有序区包含所有元素。区包含所有元素。排排 序序方法方法：o具体方法具体方法：先将第一个数据看成是一个有序的子序列，：先将第一个数据看成是一个有序的子序列，然后从第然后从第2个数据起逐个插入到这个有序的子序列中去，个数据起逐个插入到这个有序的子序列中去，相应的元素要移动。相应的元素要移动。3将将L.ri 插入插入到到L.rj+1的位置上。的位置上。2将将L.rj+1.i-1中的所有中的所有记录记录均均后移后移 一个位置；一个位置；1在在L.r1.i-1中中查找查找L.ri的插入位置，的插入位置，L.r1.j L.ri L.rj+1.i-1；排排 序序该该算算法法适适合合于于n n 较较小小的的情情况况，时时间间复复杂度为杂度为O(nO(n2 2).).待排元素序列：待排元素序列：5353 27 36 15 69 42 27 36 15 69 42第一次排序：第一次排序：27 5327 53 36 15 69 42 36 15 69 42第二次排序：第二次排序：27 36 5327 36 53 15 69 42 15 69 42第三次排序：第三次排序：15 27 36 5315 27 36 53 69 42 69 42第四次排序：第四次排序：15 27 36 53 6915 27 36 53 69 42 42第五次排序：第五次排序：15 27 36 42 53 6915 27 36 42 53 69 线性插入排序示例线性插入排序示例对于有对于有n n个数个数据元素的待排据元素的待排序列，插入操序列，插入操作要进行作要进行n-1n-1次次例：例：排排 序序void insertSort(RedType L,int n)int i,j;for(i=2;i=n;i+)L0=Li;/作为监视哨 for(j=i-1;L0.keyLj.key;j)Lj+1=Lj;/记录后移 Lj+1=L0;/插入 插入算法插入算法o方法:Ki与Ki-1,K i-2,K1依次比较,直到找到应插入的位置。排排 序序哨兵哨兵(监视哨监视哨)o哨兵(监视哨)有两个作用n作为临时变量存放Ri(当前要进行比较的关键字)的副本；n在查找循环中用来监视下标变量j是否越界。R0 R1 R2 R3 R4 R5 6 206157315 62015737 6152073367152033671520直接插入排序的程序：直接插入排序的程序：#include stdio.h#define n 5 int arn;int c,t;void d_insort(a)int an;int i,j;for(i=2;i0)&(taj)aj+1=aj;j=j-1;aj+1=t;main()int i;printf(请输入数据请输入数据:);for(i=1;i=n;i+)scanf(%d,&ari);d_insort(ar);printf(排序后的序列排序后的序列:);for(i=1;i=n;i+)printf(%d|,ari);printf(n);运行结果：运行结果：请输入数据请输入数据:50 60 20 40 80排序后的序列排序后的序列:20|40|50|60|80|排排 序序性能分析性能分析最好情况（原始记录按关键字有序排列）：最好情况（原始记录按关键字有序排列）：O（n）“比较”的次数：最坏情况（原始记录按关键字逆序排列）：最坏情况（原始记录按关键字逆序排列）：O（n2）“比较”的次数：0“移动”的次数：“移动”的次数：结论：适用原始数据基本有序或数据量不大的情况。排排 序序 希尔排序（希尔排序（Shells method）又称为）又称为“缩小增量排序缩小增量排序”，本质上讲是插入排序，它是对线性插入排序的改进。本质上讲是插入排序，它是对线性插入排序的改进。其基本思想是：其基本思想是：先取一个小于先取一个小于n的整数的整数d1并作为第一个增量，并作为第一个增量，将文件将文件的全部记录分成的全部记录分成d1个组，所有距离为个组，所有距离为d1倍数的记录放在同倍数的记录放在同一个组中，在各组内进行直接插入排序；一个组中，在各组内进行直接插入排序；然后取第二个增量然后取第二个增量d2d1，重复上述的分组和排序，重复上述的分组和排序，直至所取的增量直至所取的增量dt=1(dtdt 1d2d1)为止，此时，为止，此时，所有的记录放在同一组中进行直接插入排序。所有的记录放在同一组中进行直接插入排序。2 2 希尔插入排序希尔插入排序算法思想算法思想排排 序序o如何选择增量序列才能产生最好的排序效果，这个问题如何选择增量序列才能产生最好的排序效果，这个问题至今没有得到解决。至今没有得到解决。o希尔本人最初提出取希尔本人最初提出取nd1=d1=n/2n/2，ndi+1=di+1=di/2di/2，ndt=1dt=1，t=t=log2nlog2n。排排 序序希尔插入排序希尔插入排序步骤步骤（1 1）首先选取一个整数）首先选取一个整数d d11n n（n n为待排序数据的个数），为待排序数据的个数），作为两个数据之间的作为两个数据之间的距离距离，这样把全部数据分成，这样把全部数据分成d d1 1个组，个组，凡是距离为凡是距离为d d1 1的数据放在一个组里，在各组内进行内部的数据放在一个组里，在各组内进行内部排序，直到各组排好序为止。排序，直到各组排好序为止。（2 2）从上述的结果序列出发，再选择）从上述的结果序列出发，再选择d d22d d1 1，重复上面的，重复上面的分组与排序工作。分组与排序工作。（3 3）依次取）依次取didi+1+1didi，直到，直到dmdm=1=1（设一共需要（设一共需要m m次分组），次分组），即所有数据放在一组中排序为止。此时，全部数据便按即所有数据放在一组中排序为止。此时，全部数据便按次序排好了。次序排好了。设待排序共有设待排序共有10个记录，其关键字分别为个记录，其关键字分别为47,33,61,82,71,11,25,47,57,02，增量序列取值依次为，增量序列取值依次为5,3,1。希尔插入排序希尔插入排序过程过程 排排 序序 希尔排序实质上还是一种插入排序，其主要特点是：希尔排序实质上还是一种插入排序，其主要特点是：每一趟以不同的增量进行排序。每一趟以不同的增量进行排序。在每趟的插入排序中，记录在每趟的插入排序中，记录的关键字是和同一组中的前一个关键字进行比较，所以关键的关键字是和同一组中的前一个关键字进行比较，所以关键字较小的记录在排序过程中是作跳跃式的移动。字较小的记录在排序过程中是作跳跃式的移动。另外，另外，由于开始时增量的取值较大，每组中记录较少，由于开始时增量的取值较大，每组中记录较少，故排序比较快，故排序比较快，随着增量值的逐步变小，每组中的记录逐渐随着增量值的逐步变小，每组中的记录逐渐变多，但由于此时记录已基本有序了，因次在进行最后一趟变多，但由于此时记录已基本有序了，因次在进行最后一趟增量为增量为1的插入排序时，只需作少量的比较和移动便可完成的插入排序时，只需作少量的比较和移动便可完成排序，从而提高了排序速度。排序，从而提高了排序速度。希尔插入排序希尔插入排序特点特点 排排 序序 希尔排序比直接插入排序的平均性能要好：希尔排序比直接插入排序的平均性能要好：l在在最好情况最好情况（原始记录按关键字有序排列）下，（原始记录按关键字有序排列）下，移动次数为移动次数为0，比较次数界于，比较次数界于n n2 之间。之间。l在在最坏情况最坏情况（原始记录按关键字逆序排列）下，（原始记录按关键字逆序排列）下，移动次数和比较次数接近移动次数和比较次数接近n2。l在在平均情况平均情况下下，移动次数和比较次数在移动次数和比较次数在O（n1.3）左右，好于直接插入排序。左右，好于直接插入排序。希尔插入排序希尔插入排序性能效率性能效率排排 序序例例1.19 希尔排序的程序希尔排序的程序#include stdio.h#define max 10 int datamax+1;int indexmax+1;int i;排排 序序 void shell_sort(a)int amax+1;int i,j,n,m,skip;int alldone;for(i=1;i1)skip=skip/2;do alldone=1;for(j=1;j=max-skip;j+)i=j+skip;n=indexi;m=indexj;if(anam)indexi=m;indexj=n;alldone=0;while(alldone=0);排排 序序main()printf(请输入数据请输入数据:);for(i=1;i=max;i+)scanf(%d,&datai);printf(n);for(i=1;i=max;i+)printf(%d ,datai);printf(n);shell_sort(data);for(i=1;ilength;i1;-i)for(j=1;jrj+1rj)Swap(L-rj,L-rj+1);时间性能分析：时间性能分析：比较次数比较次数:最坏最坏(n-1)+(n-2)+.+1;最好：最好：n-1 移动次数移动次数:最坏：最坏：3(n-1)+(n-2)+.+1)；最好：；最好：0 7.3.1 冒泡排序冒泡排序算法和性能分析算法和性能分析排排 序序25531579 89i=7i=6for(j=1;j rj+1 rj)13i=27.3.1 冒泡排序冒泡排序改进改进排排 序序void BubbleSort(SqList *L)i=L-length;while(i1)/定位第定位第i个位置的记录个位置的记录 lastExchangeIndex=1;for(j=1;jrj+1rj)Swap(L-rj,L-rj+1);lastExchangeIndex=j;i=lastExchangeIndex;7.3.1 冒泡排序冒泡排序改进算法改进算法排排 序序最好情况（记录按关键字有序排列）：只需进行一趟冒泡最好情况（记录按关键字有序排列）：只需进行一趟冒泡“比较”的次数：最坏情况（记录按关键字逆序排列）：需进行最坏情况（记录按关键字逆序排列）：需进行n-1趟冒泡趟冒泡“比较”的次数：0“移动”的次数：“移动”的次数：n-17.3.1 冒泡排序冒泡排序性能分析性能分析排排 序序 首先对无序的记录序列进行首先对无序的记录序列进行“一次划分一次划分”，通过一趟排序通过一趟排序将待排序列将待排序列分成两部分分成两部分，使其中，使其中一部分记录一部分记录的关键字均比的关键字均比另另一部分小一部分小，再，再分别分别对这两部分排序，以达到整个序列有序。对这两部分排序，以达到整个序列有序。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序7.3.2 快速排序快速排序基本思想基本思想排排 序序快速排序快速排序 目标目标o找一个记录，找一个记录，以它的关键字作为以它的关键字作为“枢轴枢轴”，凡凡其其关键字小于枢轴关键字小于枢轴的记录的记录移至该记录之前，移至该记录之前，反反之，之，移至该记录之后。移至该记录之后。o一趟排序一趟排序之后，无序序列之后，无序序列L.r low.high将被将被分割成两个部分分割成两个部分：L.rlow.i-1和和L.r i+1.high 且且 L.r j L.r i L.r j (lowji-1)枢轴枢轴 (i+1jhigh)。排排 序序快速排序快速排序 方法方法o关键字通常取第一个记录的值为基准值。关键字通常取第一个记录的值为基准值。o方法：附设两个指针方法：附设两个指针i i和和j j ，初值分别指向，初值分别指向第一第一个记录个记录和和最后一个记录最后一个记录，设关键字为，设关键字为 key key ，首，首先从先从 j j所指位置起所指位置起向前向前搜索，找到第一个搜索，找到第一个小于小于基准值的记录与基准记录交换，然后从基准值的记录与基准记录交换，然后从i i 所指所指位置起位置起向后向后搜索，找到第一个搜索，找到第一个大于大于基准值的记基准值的记录与基准记录交换，重复这两步直至录与基准记录交换，重复这两步直至i=ji=j为止。为止。初始值初始值 46 55 13 42 94 5 17 70快速排序一趟算法快速排序一趟算法初始值初始值 46 55 13 42 94 5 17 70ij17 55 13 42 94 5 17 7017 55 13 42 94 5 55 70基准X=4617 5 13 42 94 5 55 70移动jij移动ij移动jiii17 5 13 42 94 94 55 7017 5 13 42 94 94 55 7046i jiiii排排 序序第一趟第一趟 13 5 17 42 46 94 55 70快速排序例快速排序例初始值初始值 46 55 13 42 94 5 17 70第二趟第二趟 5 13 17 42 46 70 55 94第三趟第三趟 5 13 17 42 46 55 70 94第四趟第四趟 5 13 17 42 46 55 70 94快速排序快速排序步骤步骤(1)(1)令指针令指针L L1 1，R Rn n ，即分别指向，即分别指向A A1 1和和AnAn；(2)(2)自尾端开始进行比较：将自尾端开始进行比较：将ARAR与与ALAL比较，若比较，若ALALARAR，则数，则数据就不交换，此时固定据就不交换，此时固定L L（即（即L L指针不动），调整尾指针，指针不动），调整尾指针，使使R RR R-1-1。继续比较，直至。继续比较，直至ALALARAR时为止，将时为止，将ARAR与与ALAL交交换位置，并修改左指针，使换位置，并修改左指针，使L LL L+1+1；(3)(3)将将ALAL与与ARAR比较，若比较，若ALALARAR，则调整左指针，使，则调整左指针，使L LL L+1+1，R R指针不动。继续比较，直至指针不动。继续比较，直至ALALARAR时为止，将时为止，将ALAL与与ARAR交换位置，并修改右指针交换位置，并修改右指针R R，使，使R RR R-1-1；(4)(4)重复重复(2)(3)(2)(3)步骤，直到从两边开始的扫描在中间相遇，步骤，直到从两边开始的扫描在中间相遇，即即L L、R R指针重合于中间某一个元素，此时该元素即在排指针重合于中间某一个元素，此时该元素即在排序的序列中找到了自己合适的位置，并且此元素将原序序的序列中找到了自己合适的位置，并且此元素将原序列分成了前后两个子集。虽然此时这两个子集还是无序列分成了前后两个子集。虽然此时这两个子集还是无序的，但前一个子集的所有元素均小于后一个子集的所有的，但前一个子集的所有元素均小于后一个子集的所有元素。这称为一趟。元素。这称为一趟。排排 序序设设 L.rlow=46为枢轴为枢轴，在调整过程中，设立两个指针：在调整过程中，设立两个指针：low 和和high，之后，之后逐渐减小逐渐减小 high或或增加增加 low，并保证：，并保证：将将 L.rhigh和枢轴的关键字进行比较，要求和枢轴的关键字进行比较，要求L.rhigh枢轴枢轴的关键字的关键字将将 L.rlow和枢轴的关键字进行比较，要求和枢轴的关键字进行比较，要求L.rlow枢轴枢轴的关键字的关键字 L.rhigh枢轴枢轴且且L.rlow枢轴枢轴,否则进行记录的否则进行记录的“交换交换”。快速排序算法快速排序算法void quicksort(int r,int left,int right)int i=left,j=right;int x=ri;while(i=x)&(ji)j=j-1;/向前比较向前比较 ri=rj;/比比x小的元素左移小的元素左移 while(rii)i=i+1;/向后比较向后比较 rj=ri;/比比x大的元素右移大的元素右移ri=x;/基准值基准值x归位归位quicksort(r,left,i-1);/递归调用左子区间递归调用左子区间quicksort(r,i+1,right);/递归调用右子区间递归调用右子区间leftrighti排排 序序快速排序的时间主要耗费在划分操作上，对长度为快速排序的时间主要耗费在划分操作上，对长度为k k的区的区间进行划分，共需间进行划分，共需k-1k-1次关键字的比较。次关键字的比较。最坏情况最坏情况是每次划分选取的基准都是当前无序区中是每次划分选取的基准都是当前无序区中关键字关键字最小最小(或最大或最大)的记录的记录，划分的结果是基准左边的子区间为，划分的结果是基准左边的子区间为空空(或右边的子区间为空或右边的子区间为空)，而划分所得的另一个非空的子，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做一个。因此，快速排序必须做n-1n-1次划分，第次划分，第i i次划分开始次划分开始时区间长度为时区间长度为n-i+1n-i+1，所需的比较次数为，所需的比较次数为n-in-i(1in-1)(1in-1)，故总的比较次数达到最大值：故总的比较次数达到最大值：n(n-1)/2=O(nn(n-1)/2=O(n2 2)快速排序快速排序时间分析时间分析排排 序序在在最好情况最好情况下，每次划分所取的基准都是当前无序区的下，每次划分所取的基准都是当前无序区的“中值中值”记录记录，划分的结果是基准的左、右两个无序子区间，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：的长度大致相等。总的关键字比较次数：O(nlogn)因为快速排序的因为快速排序的记录移动次数不大于比较的次数记录移动次数不大于比较的次数，所以快，所以快速排序：速排序：最坏最坏时间复杂度应为时间复杂度应为O(n2)最好最好时间复杂度为时间复杂度为O(nlogn)平均平均时间复杂度为时间复杂度为O(nlogn)快速排序快速排序时间分析时间分析排排 序序 快速排序在系统内部需要一个栈来实现递归。若每次划分快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为较为均匀，则其递归树的高度为O(logn)，故递归后需栈空间，故递归后需栈空间为为O(logn)。最坏情况下，递归树的高度为。最坏情况下，递归树的高度为O(n)，所需的栈空，所需的栈空间为间为O(n)。因为快速排序的因为快速排序的划分次数在划分次数在lognn之间之间，所以快速排序的：，所以快速排序的：最坏最坏空间复杂度应为空间复杂度应为O(n)最好最好空间复杂度为空间复杂度为O(logn)平均平均空间复杂度为空间复杂度为O(logn)快速排序快速排序空间分析空间分析排排 序序若待排记录的初始状态为按关键字有序时，快速排序若待排记录的初始状态为按关键字有序时，快速排序将退化为冒泡排序将退化为冒泡排序，其时间复杂度为，其时间复杂度为O(n2)。因此，快速排序适用于原始数据杂乱无章的倾向。因此，快速排序适用于原始数据杂乱无章的倾向。辅助空间数量为递归调用所开辟的栈空间。辅助空间数量为递归调用所开辟的栈空间。7.3.2 快速排序快速排序适用范围适用范围结论结论:快速排序的时间复杂度为快速排序的时间复杂度为O(nlogn)且适用于且适用于原始数据杂乱无章的情况。快速排序是非稳定的。原始数据杂乱无章的情况。快速排序是非稳定的。快速排序的程序：快速排序的程序：#include stdio.h#define n 10 int arn+1;int i,l1;int quick1(a,l,r)int an+1;int l,r;/*指针指针*/int l1;int r1,w;l1=l;r1=r;w=al1;do while(ar1=w)&(l1r1)r1=r1-1;if(l1r1)al1=ar1;l1=l1+1;while(al1=w)&(l1r1)l1=l1+1;if(l1r1)ar1=al1;r1=r1-1;while(l1!=r1);al1=w;return(l1);排排 序序void q_sort(a,l,r)int an+1;int l,r;int l1;if(lr)l1=quick1(a,l,r);q_sort(a,l,l1-1);q_sort(a,l1+1,r);main()printf(请输入数据请输入数据:n);for(i=1;i=n;i+)scanf(%d,&ari);q_sort(ar,1,n);printf(排序后的序列排序后的序列:n);for(i=1;i=n;i+)printf(%d,ari);if(i%5=0)printf(n);运行结果：运行结果：请输入数据请输入数据:42 23 74 11 65 58 94 36 99 87排序后的序列排序后的序列:11 23 36 42 58 65 74 87 94 99 排排 序序排排 序序排排 序序排排 序序23,10,20,36,40,13,27,1111,10,20,13,23,40,27,3610,11,20,13,23,40,27,3610,11,13,20,23,40,27,3610,11,13,20,23,36,27,4010,11,13,20,23,27,36,4010,11,20,13,23,40,27,3610,11,13,20,23,40,27,367.3.2 快速排序快速排序过程过程排排 序序7.4 选择选择 排排 序序简单选择排序简单选择排序堆堆 排排 序序排排 序序假设排序过程中，待排记录序列的状态为：假设排序过程中，待排记录序列的状态为：有序序列有序序列L.r 1.i-1无序序列无序序列 L.r i.n 第第 i 趟趟简单选择排序简单选择排序从中选出从中选出关键字最小的记录关键字最小的记录有序序列有序序列L.r1.i无序序列无序序列 L.ri+1.n7.4.1 简单选择排序简单选择排序基本思想和过程基本思想和过程排排 序序四、选择排序四、选择排序o直接选择排序直接选择排序n又称为简单选择排序，是一种简单直观的排序方法。n从待排序的所有记录中，选取关键字最小的记录，并将它与原始序列中的第一个记录交换，然后从去掉了关键字最小记录的剩余记录中选择关键字最小的记录将它与原始记录序列的第二个记录交换位置，以此类推，直到序列中全部记录排序完毕。排排 序序排排 序序o算法：算法：/对记录序列对记录序列x0 xn-1进行直接选择排序进行直接选择排序void selectsort(elemtype x,int n)int i,j,small;elemtype swap;for(i=0;in-1;i+)small=i;for(j=i+1;jn;j+)if(xj.keyxsmall.key)small=j;if(small!=i)swap=xi;Xi=xsmall;Xsmall=swap;排排 序序对对 n 个记录进行简单选择排序，所需进行的个记录进行简单选择排序，所需进行的 关键字间的比较次数关键字间的比较次数 总计为：总计为：移动记录的次数移动记录的次数，最小值为最小值为 0,最大值为最大值为3(n-1)。7.4.1 简单选择排序简单选择排序算法时间性能分析算法时间性能分析排排 序序o堆就是一个关键字序列堆就是一个关键字序列：并且这并且这n个关键字的序个关键字的序列列K1,K2.Kn要满足以下性质要满足以下性质(堆性质堆性质)，就是，就是:KiK2i且且KiK2i+1 或者或者 KiK2i且且KiK2i+1 2、堆排序、堆排序堆的定义堆的定义(正堆正堆)(逆堆逆堆)12,36,27,65,40,34,98,81,73,55,49是正堆是正堆12,36,27,65,40,14,98,81,73,55,49不是堆不是堆1 2 3 4 5 6 7 8 9 10 11排排 序序o当把这个序列存入一个向量并把它看作是一棵完全二当把这个序列存入一个向量并把它看作是一棵完全二叉树的存储结构时，堆就是这样一棵二叉树：叉树的存储结构时，堆就是这样一棵二叉树：任一非任一非叶结点的关键字均不小于叶结点的关键字均不小于(或不大于或不大于)其左右孩子结点其左右孩子结点的关键字。的关键字。2、堆排序、堆排序1236276549817355403498是堆是堆14不不排排 序序1 2 3 4 5 6 7 89470174642550513堆堆最大值排排 序序897624331510112536497856a)堆顶元素取最大值堆顶元素取最大值大根堆大根堆b)堆顶元素取最小值堆顶元素取最小值小根堆小根堆排排 序序堆排序基本思想堆排序基本思想o因为堆顶是最大的数，所以当把一个关键字序列排成一个大根堆时，就很容易地找到最大的数，它就在序列的第一个位置上o然后把这个最大的数与最后一个记录交换，这时，最后一个记录就是关键字最大的记录了。o对于剩下的关键字序列，我们仍然把它排成一个大根堆，然后再把第一个记录(当前堆中的堆顶)与当前堆的最后一个记录交换。这时，在整个序列后面就有了两个有序的关键字(从小到大)。o重复这样的过程，就可以把有序区不断扩大直到全部关键字都进入有序区。直到排序完成。9470174642550513初始堆初始堆42701746945505131355174694420570排排 序序堆的构造堆的构造o无序序列无序序列r1：n构成的完全二叉树。构成的完全二叉树。o从它最后一个非叶子结点（第从它最后一个非叶子结点（第n/2个元素）开始直到根个元素）开始直到根结点为止，逐步进行结点为止，逐步进行调整调整即可将此完全二叉树构成堆。即可将此完全二叉树构成堆。o调整：调整：与其左右子树根结点值比较，取其中大的进行交与其左右子树根结点值比较，取其中大的进行交换。换。排排 序序堆的构造例堆的构造例465513427094051746 55 13 42 94 05 17 707017594421355461 2 3 4 5 6 7 81 2 3 4 5 6 7 8排排 序序465513704294 051746551342709405177017594421355461 2 3 4 5 6 7 8对调对调4217594701355461 2 3 4 5 6 7 8对调对调1313堆的构造例堆的构造例46 55 13 42 94 05 17 70排排 序序46551770429405134213594701755461 2 3 4 5 6 7 8对调5555对调46941770425505134213555701794461 2 3 4 5 6 7 8对调4646对调堆的构造例堆的构造例46 55 13 42 94 05 17 70排排 序序94461770425505134213555701746941 2 3 4 5 6 7 8对调4646对调94701746425505134213555461770941 2 3 4 5 6 7 8成堆成堆!堆的构造例堆的构造例46 55 13 42 94 05 17 70排排 序序4655134270940517初始无序结点,从42开始调整4655137042940517将以13为根的子树调整成堆4655177042940513将以55为根的子树调整成堆堆的构造例堆的构造例46 55 13 42 94 05 17 70排排 序序4694177042550513将以46为根的子树调整成堆9470174642550513成堆排排 序序调整成堆算法调整成堆算法void SIFT(int r,int i,int n)/调整调整r1:n中结点中结点ri,使成为一个堆使成为一个堆int j;int T;T=ri;j=2*i;/j为为i结点的左孩子序号结点的左孩子序号while(jn)if (jn)&(rj rj+1)j+;/找出找出i的大孩的大孩子子 if (T=0;i-)/将将r调整成堆调整成堆SIFT(r,i,n);for(i=n-1;i=0;i-)t=r0;r0=ri;ri=t;SIFT(r,0,i-1);i0堆排序的程序：堆排序的程序：#include stdio.h#define mm 8 int amm+1;int k;void shift(a,l,m)void heapsort(a)int amm+1;int i,x;for(i=mm/2;i=1;i-)shift(a,i,mm);/*从第开始进行筛选建堆*/for(i=mm;i=2;i-)x=a1;a1=ai;ai=x;/*将堆顶元素和堆中最后一个元素交换*/shift(a,1,i-1);/*调整第一个元素使之重又成为堆*/main()printf(请输入数据请输入数据:n);for(k=1;k=mm;k+)scanf(%d,&ak);printf(初始数据初始数据:n);for(k=1;k=mm;k+)printf(a%d=%d,k,ak);printf(n);heapsort(a);printf(排序后的数据排序后的数据:n);for(k=1;k=mm;k+)printf(|a%d=%d|,k,ak);printf(n);排排 序序五、五、基数排序基数排序l 前前面面介介绍绍的的几几种种排排序序方方法法都都是是按按数数据据元元素素（或或记记录录关关键键字字）值的大小进行排序的值的大小进行排序的l 而而多多关关键键字字排排序序是是一一种种按按组组成成数数据据元元素素或或关关键键字字的的各各位位值值进进行行排排序序的的方方法法，基基数数排排序序借借助助的的就就是是这这种种思思想想，它它属属于于分分布式排序布式排序，也称，也称口袋排序口袋排序。l 基基数数排排序序是是把把逻逻辑辑关关键键字字看看成成由由若若干干个个子子关关键键字字复复合合而而成成的的 假设有假设有n个关键字个关键字r1，r2，rn需进行排序需进行排序 每每个个关关键键字字由由d元元组组（k1k2k3kd）子子关关键键字字组组成成，k1是是关键字值的最高位，关键字值的最高位，kd是关键字值的最低位，其基数为是关键字值的最低位，其基数为rd排排 序序五、五、基数排序基数排序l 前前面面介介绍绍的的几几种种排排序序方方法法都都是是按按数数据据元元素素（或或记记录录关关键键字字）值的大小进行排序的值的大小进行排序的l 多多关关键键字字排排序序是是一一种种按按组组成成数数据据元元素素或或关关键键字字的的各各位位值值进进行排序行排序的方法，基数排序借助的就是这种思想的方法，基数排序借助的就是这种思想。l基数排序基数排序属于属于分布式排序分布式排序，也称口袋排序，也称口袋排序、“桶子法桶子法”。l基数排序法是属于基数排序法是属于稳定性稳定性的排序的排序l时时间间复复杂杂度度为为O(nlog(r)m)，其其中中r为为所所采采取取的的基基数数，而而m为为堆堆数数，在在某某些些时时候候，基基数数排排序序法法的的效效率率高高于于其其它它的的比比较较性性排序法。排序法。排排 序序o基数排序的方式可以采用：基数排序的方式可以采用：nLSD（Least significant digital）的排序方式由键的排序方式由键值的值的最右边最右边开始开始nMSD（Most si