数据结构-第10章内部排序.ppt

第10章 内部排序 10.1 概述 4. 什么叫内部排序？什么叫外部排序？ 6. 顺序存储（顺序表）的抽象数据类型如何表示？ 10.2 插入排序 （1） 直接插入排序(最简单的排序法) 例2：关键字序列T= （21，25，49，25*，16，08），请写出直接插入排序的具体实现过程。 直接插入排序算法 （3）希尔（shell）排序（又称缩小增量排序） 例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），请写出希尔排序的具体实现过程。 10.3 交换排序 （1） 冒泡排序 冒泡排序的算法 （2） 快速排序 快速排序算法 10.4 选择排序 （1）简单选择排序 简单选择排序的算法如下： （2） 堆排序 2. 怎样建堆？ 3. 怎样进行堆排序？ 例：对刚才建好的大根堆进行排序 10.5 归并排序 10.6 基数排序 1.什么是“多关键字”排序？实现方法？ 2.单逻辑关键字怎样“按位值”排序？ 这种LSD排序方法称为： 第一趟收集的结果： 第二趟收集的结果： 各种内部排序方法的比较(教材P289） 练习 3、关键字序列 T=(21，25，49，25*，16，08），请写出快速排序算法的第一趟实现过程 4、有一组键值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大进行排序，请写出第一趟排序过程中键值的移动情况。 5、已知有五个待排序的记录，其关键字分别为：256，301，751，129，937,863，742，694，076，438请用快速排序的方法将它们从小到大排列。 6、设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。 (1) 写出直接插入排序的全过程，要求按递减顺序排序。 (2) 写出直接选择排序的全过程，要求按递减顺序排序。 7、设文件有12个记录,其关键字值分别为37,23,7,79,9,43,3,19,31,61,23,47,按非递减的次序进行排序。试分别给出用下列方法排序时第一,二趟处理后的结果序列。 1.冒泡排序 2.选择排序 3.快速排序 8、设文件有10个记录，其关键字值分别为:37,23,7,79,29,43,73,19,31,61,试给出冒泡排序法按非递减的次序进行排序过程中的每一趟结果序列。 9、判断以下序列是否为堆,若不是,调整为堆，并写出调整过程。 a.{12,15,23,35,28,87,49,86} b.{35,12,28,87,49,86,15,23} 10、将下列给定的关键字序列调整成一个堆，使其满足 Ki≤K2i 及 Ki≤K2i+1 ，并依次 画出输出关键字11的过程中所调整成的每一个堆结构。 11， 22， 27， 03， 31， 78， 40， 05， 61， 47， 93， 69， 12 11、利用堆排序的方法给已知数组A中的数据排序,写出在构成初始堆（大根堆）和利用堆排序的过程中,每次排序后数据的排列情况: 1 2 3 4 5 6 7 8 ┌─┬─┬─┬─┬─┬─┬─┬─┐ A│45│28│49│16│37│82│56│75│ └─┴─┴─┴─┴─┴─┴─┴─┘ 1.构成初始堆的过程 (1) (2) (3) (4) 2.利用堆排序的过程 (1) (2) (3) (4) (5) (6) (7) 12、设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： (1)冒泡排序第一趟的结果是： (2)初始步长为4的希尔（shell）排序第一趟的结果是: (3)二路归并排序第一趟的结果是： (4)快速排序第一趟的结果是: