数据结构排序.ppt
第第1010章章 排序排序排序的基本概念排序的基本概念插入排序插入排序( (直接插入排序、直接插入排序、) )选择排序选择排序( (直接直接选择排序选择排序、堆、堆) )交换排序交换排序( (冒泡排序、快速排序冒泡排序、快速排序) )归并排序归并排序基数排序基数排序性能比较性能比较主要知识点主要知识点10.1 10.1 排序的基本概念排序的基本概念 排序排序是对数据元素序列建立某种有序排列的过程是对数据元素序列建立某种有序排列的过程, ,是把一个数是把一个数据元素序列整理成按关键字递增（或递减）排列的过程。据元素序列整理成按关键字递增（或递减）排列的过程。关键字关键字是要排序的数据元素集合中的一个域，排序是以关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。为基准进行的。主关键字主关键字: :数据元素值不同时该关键字的值也一定不同，是能数据元素值不同时该关键字的值也一定不同，是能够惟一区分各个不同数据元素的关键字够惟一区分各个不同数据元素的关键字; ;不满足主关键字定义不满足主关键字定义的关键字称为的关键字称为次关键字次关键字。内部排序内部排序是把待排数据元素全部调入内存中进行的排序。是把待排数据元素全部调入内存中进行的排序。外部排序外部排序是因数量太大，把数据元素分批导入内存，排好序后是因数量太大，把数据元素分批导入内存，排好序后再分批导出到磁盘和磁带外存介质上的排序方法。再分批导出到磁盘和磁带外存介质上的排序方法。比较排序算法优劣的标准比较排序算法优劣的标准: : (1)时间复杂度时间复杂度:它主要是分析记录关键字的比较次数和记录的它主要是分析记录关键字的比较次数和记录的 移动次数移动次数(2)空间复杂度空间复杂度 :算法中使用的内存辅助空间的多少算法中使用的内存辅助空间的多少 (3)稳定性稳定性:若两个记录若两个记录A A和和B B的关键字值相等，但排序后的关键字值相等，但排序后A A、B B的的 先后次序保持不变，则称这种排序算法是稳定的先后次序保持不变，则称这种排序算法是稳定的10.210.2插入排序插入排序 插入排序的插入排序的基本思想基本思想是：是：每步将一个待排序的数据元素，每步将一个待排序的数据元素，按其关键码大小，插入到前面已经排好序的一组数据元素的适按其关键码大小，插入到前面已经排好序的一组数据元素的适当位置上，直到数据元素全部插入为止。当位置上，直到数据元素全部插入为止。1.1.直接插入排序直接插入排序常用的插入排序有常用的插入排序有直接插入排序直接插入排序和和希尔排序希尔排序两种。两种。 其基本思想是：其基本思想是： 顺序地把待排序的数据元素按其关键字值的大小插入到顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。已排序数据元素子集合的适当位置。算法如下：算法如下：void InsertSort (DataType a, int n)/用直接插入法对用直接插入法对a0-an-1排序排序 int i, j; DataType temp; for(i=0; i -1 & temp.key aj.key) aj+1 = aj; j-; aj+1 = temp; 算法分析算法分析: :(1)空间效率：空间效率：仅占用若干个临时内存单元仅占用若干个临时内存单元(2)算法的稳定性：算法的稳定性：稳定稳定(3)时间效率：时间效率： 在最坏情况下（反序），所有元素的比较次在最坏情况下（反序），所有元素的比较次数总和为（数总和为（12n-1)O(n2)。平均时间复杂度也为平均时间复杂度也为O(n2) 但在最好情况下（正序），所有元素的比较次数但在最好情况下（正序），所有元素的比较次数总和为（总和为（111)O(n)。 分析：分析：元素序列越接近有序，比较次数越少。时间复杂元素序列越接近有序，比较次数越少。时间复杂度越接近度越接近O(n) 。64789624564896245764624576489245676489567246489589624初始关键字序列初始关键字序列:第一次排序第一次排序:第二次排序第二次排序:第三次排序第三次排序:第四次排序第四次排序:第五次排序第五次排序:7直接插入排序过程直接插入排序过程 10.3 10.3 选择排序选择排序 基本思想是：基本思想是：每次从待排序的数据元素集合中选取每次从待排序的数据元素集合中选取关键字关键字最小（或最大）最小（或最大）的数据元素放到数据元素集合的的数据元素放到数据元素集合的某个位置，某个位置，数据元素集合不断缩小，当数据元素集合为空时选择排序结数据元素集合不断缩小，当数据元素集合为空时选择排序结束。束。常用的选择排序算法：常用的选择排序算法： （1 1）直接选择排序）直接选择排序 （2 2）堆排序）堆排序 基本思想是：基本思想是：从待排序的数据元素集合中选取关键字最小从待排序的数据元素集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第一个数据元素交的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上数据元素的集合中选取关换位置；然后从不包括第一个位置上数据元素的集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第二个数键字最小的数据元素并将它与原始数据元素集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素为止。据元素为止。 优点：优点：实现简单实现简单缺点：缺点：每趟只能确定一个元素，表长为每趟只能确定一个元素，表长为n n时需要时需要n-1n-1趟趟算法如下：算法如下：void SelectSort(DataType a, int n) int i, j, small; DataType temp; for(i = 0; i n-1; i+) small = i; /设第设第i个数据元素关键字最小个数据元素关键字最小 for(j = i+1; j n; j+)/寻找关键字最小的数据元素寻找关键字最小的数据元素 if(aj.key asmall.key) small=j; /记住最小元素的下标记住最小元素的下标 if(small != i)/当最小元素的下标不为当最小元素的下标不为i时交换位置时交换位置 temp = ai; ai = asmall; asmall = temp; 645789624564789624567896424567896424567246489567246489初始关键字序列初始关键字序列:第一次排序结果第一次排序结果:第二次排序结果第二次排序结果:第三次排序结果第三次排序结果:第四次排序结果第四次排序结果:第五次排序结果第五次排序结果:567246489最后结果序列最后结果序列:直接选择排序的排序过程直接选择排序的排序过程 算法分析算法分析时间效率：时间效率： O(nO(n2 2) )虽移动次数较少，但比较次数仍多。虽移动次数较少，但比较次数仍多。 空间效率：空间效率：O(1)O(1)仅用到若干个临时变量。仅用到若干个临时变量。算法的稳定性：算法的稳定性：不稳定不稳定10.4 10.4 交换排序交换排序 交换排序的基本思想是：利用交换数据元素的位交换排序的基本思想是：利用交换数据元素的位置进行排序的方法。置进行排序的方法。交换排序的主要算法有：交换排序的主要算法有：1)1)冒泡排序冒泡排序2)2)快速排序快速排序1.1.冒泡排序冒泡排序 基本思想：基本思想：每趟不断将数据元素两两比较，并按每趟不断将数据元素两两比较，并按“前小后前小后大大”（或（或“前大后小前大后小”）规则交换。）规则交换。优点：优点：每趟结束时，不仅能挤出一个最大值到最后面位置，每趟结束时，不仅能挤出一个最大值到最后面位置，还能还能同时部分理顺其他元素同时部分理顺其他元素；一旦下趟没有交换发；一旦下趟没有交换发生，还可以生，还可以提前结束排序提前结束排序。算法核心语句如下：算法核心语句如下： flag = 1;for(i = 1;i n & flag = 1; i+) flag = 0; for(j = 0;j aj+1.key) flag = 1; temp = aj; aj = aj+1aj+1; aj+1 = temp; 初始关键字序列初始关键字序列:第一次排序结果第一次排序结果:第二次排序结果第二次排序结果:第三次排序结果第三次排序结果:第四次排序结果第四次排序结果:第五次排序结果第五次排序结果:最后结果序列最后结果序列:385192649971665192638491669751926381496697519261384966975191263849669751192638496697151926384966971519263849669715192638496697第六次排序结果第六次排序结果:第七次排序结果第七次排序结果:冒泡排序算法的排序过程冒泡排序算法的排序过程 算法分析：算法分析：最好情况：最好情况：初始排列已经有序，只执行一趟起泡，做初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动数据元素。次关键码比较，不移动数据元素。最坏情形：最坏情形：初始排列逆序，算法要执行初始排列逆序，算法要执行n-1趟起泡，第趟起泡，第i趟趟(1 i n) 做了做了n- i 次关键码比较，执行了次关键码比较，执行了n-i 次数据元素交次数据元素交换。此时的比较总次数和记录移动次数为：换。此时的比较总次数和记录移动次数为：11111233121nininninnnin)()()()(移移动动次次数数比比较较次次数数因此：因此：时间效率：时间效率：O O（n n2 2) ) 考虑最坏情况考虑最坏情况空间效率：空间效率：O O（1 1） 仅用到若干个临时变量仅用到若干个临时变量稳稳 定定 性：性： 稳定的稳定的排序方法排序方法最好时最好时 间间平均时间平均时间最坏时间最坏时间辅助空间辅助空间稳定性稳定性直接插入排序直接插入排序O(n)O(n2)O(n2)O(1)稳定稳定 直接选择排序直接选择排序O(n2)O(n2)O(n2)O(1)不稳定不稳定冒泡排序冒泡排序O(n)O(n2)O(n2)O(1)稳定稳定10.7 10.7 性能比较性能比较
