数据结构课件 第10章内部排序.pptVIP

第10 章 内部排序;10.1基本概念10.1.1排序介绍;学生档案表;在学生档案表中，若以每个记录的学号为关键字，按排序码年龄的递增（由小到大）排序，则所有记录的排序结果可简记为： {（99006，16），（99003，17），（99001，18），（99004，18），（99002，19），（99005，20）}； 也可能为： {（99006，16），（99003，17），（99004，18），（99001，18），（99002，19），（99005，20）}； 这两个结果都是按年龄的递增排序结果。若按排序码姓名来进行递增排序，则得到的排序结果为： {（99006，李小燕），（99002，林一鹏），（99001，王晓佳），（99003，谢宁），（99004，张丽娟），（99005，周涛）} 当然，我们还可以按排序码性别来进行递增排序，在此不再作进一步的分析。;10.1.2 基本概念1. 排序码（sort key）;2. 有序表与无序表;3. 正序表与逆序表;4. 排序定义;5. 稳定与不稳定;6. 内排序与外排序;7. 排序的时间复杂性;为了以后讨论方便，我们直接将排序码写成一个一维数组的形式，具体类型设为ElemType，并且在没有声明的情形下，所有排序都按排序码的值递增排列。;排序方法分类：;10.2 插入排序10.2.1 直接插入排序1. 直接插入排序的基本思想;例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。它的直接插入排序的执行过程如图所示。;2. 直接插入的算法实现;3. 直接插入排序的效率分析;则上述直接插入算法对应的这些量为： Cmin=n-1 Mmin=2(n-1) Cmax=1+2+…+n-1=(n2-n)/2 Mmax=3+4+…+n+1=(n2+3n-4)/2 Cave=(n2+n-2)/4 Mave=(n2+7n-8)/4 因此，直接插入排序的时间复杂度为O(n2)。 直接插入算法的元素移动是顺序的，该方法是稳定的。;10.2.2 二分插入排序1. 二分插入排序的基本思想;2. 二分插入排序的算法实现;3. 二分插入排序的效率分析;10.2.3 希尔排序1. 希尔排序的基本思想;2. 希尔排序的执行过程;算法见教材P271;3. 希尔排序的效率分析;10.3 交换排序10.3.1 冒泡排序1. 冒泡排序的基本思想;因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从??减少不必要的比较。 例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。下面用图给出冒泡排序算法的执行过程。;2. 冒泡排序的算法实现;3. 冒泡排序的效率分析;10.3.2 快速排序1. 快速排序的基本思想;快速排序的过程为：把待排序区间按照第一个元素（即基准元素）的排序码分为左右两个子序列的过程叫做一次划分。设待排序序列为R[left]～R[right]，其中left为下限，right为上限，left＜right，R[left]为该序列的基准元素，为了实现一次划分，令i、j的初值分别为left和right。;在划分过程中，首先让j从它的初值开始，依次向前取值，并将每一元素R[j]的排序码同R[left]的排序码进行比较，直到R[j]R[left]时，交换R[j]与R[left]的值，使排序码相对较小的元素交换到左子序列，然后让i从i+1开始，依次向后取值，并使每一元素R[i]的排序码同R[j]的排序码（此时R[j]为基准元素）进行比较，直到R[i]＞R[j]时，交换R[i]与R[j]的值，使排序码大的元素交换到后面子区间；再接着让j从j-1开始，依次向前取值，重复上述过程，直到i等于j,即指向同一位置为止，此位置就是基准元素最终被存放的位置。此次划分得到的前后两个待排序的子序列分别为R[left]～R[i-1]和R[i+1]～R[right]。;例如，给定排序码为：（46，55，13，42，9，5，17，70），具体划分如图所示。;2. 快速排序的算法实现; while((R[i]=temp)(ji)) i=i+1; if (ij){ R[j]=R[i]; j=j-1; } } //一次划分得到基准值的正确位置 R[i]=temp; if(lefti-1) QuickSort(R,left,i-1); //递归调用左子区间 if(i+1right) QuickSort(R,i+1,right); //递归调用右子区间 };3. 快速排序的效率分