课程名称：数据结构第14周，第_14_讲次摘要第八章排序授课题目（章、节）第一节排序的基本概念第二节插入排序第三节交换排序【目的要求】通过本讲课程的学习，了解排序的基本概念，掌握衡量排序算法优劣的标准（时间复杂度、空间复杂度、稳定性），掌握插入排序和交换排序的基本思想以及不同排序算法的性能比较。[重点】掌握插入排序和交换排序两类排序方法的基本思想。【难点】掌握希尔排序和快速排序的基本思想及实现方法。内容【本讲课程的引入】在我们进行应用软件的设计中，排序是最经常遇到的问题之一。这一次课我们要讨论几类经常会用到的排序算法，在讲述排序算法之间我们先从概念上讨论一下什么是排序，以及怎么样衡量一个排序算法优劣。【本讲课程的内容】第8章排序8.1排序的基本概念1.排序是对数据元素序列建立某种有序排列的过程。2.排序的目的：便于查找。3.关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。关键字分主关键字和次关键字两种。对要排序的数据元素集合来说，如果关键字满足数据元素值不同时该关键字的值也一定不同，这样的关键字称为主关键字。不满足主关键字定义的关键字称为次关键字。学生成绩表中学号为主关键字。姓名序号数学语文物理英吾8407Q. 078077.001004Wang Yun100275088.092.085.01Zhang Pen284.066080.01012Li Cheng9003100880095.077.084.3Chen Hing::....:.m1022Chu San9Q.095.0880100. 04.排序的种类：分为内部排序和外部排序两大类。若待排序记录都在内存中，称为内部排序：若待排序记录一部分在内存，一部分在外存，则称为外部排序。注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。5.排序算法好坏的衡量标准：（1）时间复杂度一一它主要是分析记录关键字的比较次数和记录的移动次数。(2)空间复杂度一一算法中使用的内存辅助空间的多少。(3)稳定性一一若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变：则称这种排序算法是稳定的
课程名称：数据结构 第 14 周，第 14 讲次 摘 要 授课题目（章、节） 第八章 排序 第一节 排序的基本概念 第二节 插入排序 第三节 交换排序 【目的要求】通过本讲课程的学习，了解排序的基本概念，掌握衡量排序算法优劣的标准（时间复杂度、空 间复杂度、稳定性），掌握插入排序和交换排序的基本思想以及不同排序算法的性能比较。 【重 点】掌握插入排序和交换排序两类排序方法的基本思想。 【难 点】掌握希尔排序和快速排序的基本思想及实现方法。 内 容 【本讲课程的引入】在我们进行应用软件的设计中，排序是最经常遇到的问题之一。这一 次课我们要讨论几类经常会用到的排序算法，在讲述排序算法之间我们先从概念上讨论一 下什么是排序，以及怎么样衡量一个排序算法优劣。 【本讲课程的内容】 第 8 章 排序 8.1 排序的基本概念 1.排序是对数据元素序列建立某种有序排列的过程。 2.排序的目的：便于查找。 3.关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。 关键字分主关键字和次关键字两种。对要排序的数据元素集合来说，如果关键字满足 数据元素值不同时该关键字的值也一定不同，这样的关键字称为主关键字。不满足主关键 字定义的关键字称为次关键字。 学生成绩表中学号为主关键字。 4.排序的种类：分为内部排序和外部排序两大类。 若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外 存，则称为外部排序。 注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部 排序要复杂得多。 5.排序算法好坏的衡量标准： (1)时间复杂度—— 它主要是分析记录关键字的比较次数和记录的移动次数。 (2)空间复杂度——算法中使用的内存辅助空间的多少。 (3)稳定性——若两个记录 A 和 B 的关键字值相等，但排序后 A、B 的先后次序保持不变， 则称这种排序算法是稳定的
8.2插入排序插入排序的基本思想是：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。常用的插入排序有：直接插入排序和希尔排序两种。9.2.1直接插入排序1、其基本思想是：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。例1：关键字序列T=（13，6，3，31，9，27，5，11)，请写出直接插入排序的中间过程序列。初始关键字序列：【13】，6,3,31,9,27,5,11第一次排序：【6,13】，3,31,9,27,5,11第二次排序：【3,6,13】，31,9,27,5,11第三次排序：[3,6,13,31],9,27,5,11第四次排序：【3,6,9,13,31】,27,5,11第五次排序：【3,6,9,13，27,31】，5,11第六次排序：【3,5,6,9,13,27,31]，11第七次排序：【3,5,6,9,11,13,27,31]注：方括号【］中为已排序记录的关键字，下划横线的关键字表示它对应的记录后移-个位置。publicstaticvoidinsertSort(int[a)(int i,j, temp:int n = a. length;for(i=o:i-l &&temp<a[i])(a[j + 1] = a[j];j -;1a[j + 1] = temp:113、直接插入排序算法分析(1)时间效率：因为在最坏情况下，所有元素的比较次数总和为（0+1十十n-1)→0(n2）。其他情况下也要考虑移动元素的次数。故时间复杂度为0(n2）(2)空间效率：仅占用1个缓冲单元一一0（1)(3)算法的稳定性：稳定8.2.2希尔（shel1）排序（又称缩小增量排序）1、基本思想：把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序：小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过
8.2 插入排序 插入排序的基本思想是：每步将一个待排序的对象，按其关键码大小，插入到前面已经 排好序的一组对象的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证 子序列中随时都是排好序的。 常用的插入排序有：直接插入排序和希尔排序两种。 9.2.1 直接插入排序 1、其基本思想是： 顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当 位置。 例 1：关键字序列 T=（13，6，3，31，9，27，5，11），请写出直接插入排序的中间过程序 列。 初始关键字序列： 【13】, 6, 3, 31, 9, 27, 5, 11 第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11 第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11 第三次排序： 【3, 6, 13，31】, 9, 27, 5, 11 第四次排序： 【3, 6, 9, 13，31】, 27, 5, 11 第五次排序： 【3, 6, 9, 13，27, 31】, 5, 11 第六次排序： 【3, 5, 6, 9, 13，27, 31】, 11 第七次排序： 【3, 5, 6, 9, 11，13，27, 31】 注：方括号 [ ]中为已排序记录的关键字，下划横线的 关键字表示它对应的记录后移一 个位置。 public static void insertSort(int[] a){ int i, j, temp; int n = a.length; for(i = 0; i -1 && temp < a[j]){ a[j + 1] = a[j]; j -; } a[j + 1] = temp; } } 3、直接插入排序算法分析 (1)时间效率：因为在最坏情况下，所有元素的比较次数总和为（0＋1＋.＋n-1)→O(n2)。 其他情况下也要考虑移动元素的次数。 故时间复杂度为 O(n2) (2)空间效率：仅占用 1 个缓冲单元——O（1） (3)算法的稳定性：稳定 8.2.2 希尔（shell）排序 （又称缩小增量排序） 1、基本思想：把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接 插入法排序；小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过
程结束。2、技巧：小组的构成不是简单地“遂段分割”，而是将相隔某个增量d的记录组成一个小组，让增量d逐趟缩短（例如依次取5,31），直到d=1为止。（通常，di+1=di/2（结果取整))3、优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。例2：设待排序的序列中有12个记录，它们的关键字序列T=（65，34，25，87，12，38，56，46，14，77，92，23)，请写出希尔排序的具体实现过程。下面给出希尔排序的具体实现过程：258712385646779265341423第1越（d=6)结果序列5677122365341446258792(a)第2趟(d=3)结果序列5612146523387T26)第3越（d=1)结果序列121423253438465665778792(e)public static void shellSort(int[ a, int[J d, int numofD)(int i,j,k,m,span;int temp;int n = a.length:for（m=O;m-1&&temp<=a[j])fa[j + span] = a[j];j=j-span;中a[j+ span] = temp;
程结束。 2、技巧：小组的构成不是简单地“逐段分割”，而是将相隔某个增量 dk 的记录组成一个 小组,让增量 dk 逐趟缩短（例如依次取 5,3,1），直到 dk＝1 为止。（通常，di+1=di/2 (结 果取整）） 3、优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理， 时间效率会高很多。 例 2：设待排序的序列中有 12 个记录，它们的关键字序列 T=(65，34，25，87，12，38， 56，46，14，77，92，23)，请写出希尔排序的具体实现过程。 下面给出希尔排序的具体实现过程： public static void shellSort(int[] a, int[] d, int numOfD){ int i, j, k, m, span; int temp; int n = a.length; for(m = 0; m -1 && temp <= a[j]){ a[j + span] = a[j]; j = j - span; } a[j + span] = temp; } }
17算法分析：开始时d的值较大，子序列中的对象较少，排序速度较快；随着排序进展，d值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数记录已基本有序，所以排序速度仍然很快。时间效率：0（n1og2n）2)空间效率：0（1）一一因为仅占用1个缓冲单元算法的稳定性：不稳定8.3交换排序交换排序的基本思想是：利用交换数据元素的位置进行排序的方法。交换排序的主要算法有：1）冒泡排序2）快速排序8.3.1冒泡排序1、基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。2、优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素：一旦下趟没有交换发生，还可以提前结束排序。例：关键字序列T=(21，225，49，25*，16，08），请按从小到大的顺序，写出冒泡排序的具体实现过程。初态：21，225,49,25*，16，08弟121,25,25*,16,08.49第2趟21,25,16,08,25*，4921,16,08,25,25*，49第3麺16,08,21,25,25*,49第4麺08,16,21,25,25*，49弟范public static voidbubbleSort(int[)a)(int i,j, flag=l;int temp;int n = a. length;for(i=l;ia[j+])(flag = 1;temp = a[j];a[j] = a[j+1];a[j+1] = temp;子身114、冒泡排序的算法分析·最好情况：初始排列已经有序，只执行一趟起泡，做Ⅱ-1次关键码比较，不移动对象。：最坏情形：初始排列逆序，算法要执行nr-1起泡，第i（1f<n）做了n-i次关键码比较，执行了n-i次对象交换。此时的比较总次数KCN和记录移动次数RMN为：
} } 算法分析：开始时 d 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，d 值 逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数记录已基本有序， 所以排序速度仍然很快。 时间效率：O(n(log2n)2) 空间效率：O（1）——因为仅占用 1 个缓冲单元 算法的稳定性：不稳定 8.3 交换排序 交换排序的基本思想是：利用交换数据元素的位置进行排序的方法。 交换排序的主要算法有：1) 冒泡排序 2) 快速排序 8.3.1 冒泡排序 1、基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。 2、优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素； 一旦下趟没有交换发生，还可以提前结束排序。 例：关键字序列 T=(21，25，49，25*，16，08），请按从小到大的顺序，写出冒泡排序的 具体实现过程。 public static void bubbleSort(int[] a){ int i, j, flag=1; int temp; int n = a.length; for(i = 1; i a[j+1]){ flag = 1; temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } 4、冒泡排序的算法分析 •最好情况：初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动对象。• 最坏情形：初始排列逆序，算法要执行 n-1 趟起泡，第 i 趟(1£ i< n) 做了 n- i 次关键 码比较，执行了 n-i 次对象交换。此时的比较总次数 KCN 和记录移动次数 RMN 为：
1KCN(n-i):n(n-1)2is1-13RMN=(n-i=n(n-1)2i1is因此：时间效率：0（n2）一因为要考虑最坏情况空间效率：0（1）一只在交换时用到一个缓冲单元稳定性：稳定一25和25*在排序前后的次序未改变8.3.2快速排序1、基本思想：从待排序列中任取一个元素（例如取第一个）作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表：然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。2、优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快。public static void quickSort(int[ a, int low, int high)(int i,j;int temp;i = low;j = high;temp=a[1ow]：//取第一个元素为标准数据元素while(i< j)t//在数组的右端扫描while(i< j&&temp<=a[jl) j--;if(ij){a[i] = a[];i++;1while(i<j&&a[i]<temp)i++;if(ij)a[j] = a[i];j--;11a[i] = temp:if(low<i)quickSort(a,low,i-1)//对左端子集合递归if(i<high）quickSort（a，j+1，high)：//对右端子集合递归例、关键字序列T=（60，55，48，37，10，90，84，36），请按从小到大的顺序，写出快速排序的具体实现过程
− = − = = − = − = − = − 1 1 1 1 1 2 3 3 1 2 1 n i n i RMN n i n n KCN n i n n ( ) ( ) ( ) ( ) 因此： 时间效率：O（n2) —因为要考虑最坏情况 空间效率：O（1） —只在交换时用到一个缓冲单元稳 定 性： 稳定 —25 和 25*在排序前 后的次序未改变 8.3.2 快速排序 1、基本思想：从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素 一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中 心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。 2、优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快。 public static void quickSort(int[] a, int low, int high){ int i, j; int temp; i = low; j = high; temp = a[low]; //取第一个元素为标准数据元素 while(i < j){ //在数组的右端扫描 while(i < j && temp <= a[j]) j-; if(i < j){ a[i] = a[j]; i++; } while(i < j && a[i] < temp) i++; if(i < j){ a[j] = a[i]; j-; } } a[i] = temp; if(low < i) quickSort(a, low, i-1); //对左端子集合递归 if(i < high) quickSort(a, j+1, high); //对右端子集合递归 } 例、关键字序列 T=(60，55，48，37，10，90，84，36），请按从小到大的顺序，写出快速 排序的具体实现过程
初始关键字序列：60554836371090844415(1)365548371090844Ti55(2)364837109084↑.A1554837(3)36109084ATi(4)373655481090844Ti(5)103655483790844A1iIj(6)1036554837908447Ti15(7)103655483784904j(8)5548371060368490AAij第一次快速排序过程5548371060908136关车州：(1)3655483710}60901(2)(0)363755)6081(90)36(3)(0](37)48[55)]60&90最后储果103637&556084904、快速排序算法分析：时间效率：0（nlog2n）一因为每确定的元素呈指数增加空间效率：0（log2n）一因为递归要用栈（存每层1low，high和pivot）稳定性：不稳定一因为有跳跃式交换。【本讲课程的小结】插入排序和交换排序是常见的两类排序方法，对于这两类排序算法的思想我们应该熟练掌握，对于它们各自的特点（时间复杂度、空间复杂度和稳定性）要有
60 55 48 37 10 90 84 36 36 55 48 37 10 90 84 90 90 36 55 48 37 10 90 84 36 55 48 37 10 90 84 36 55 48 37 10 90 84 36 55 48 37 10 90 84 36 55 48 37 10 90 84 36 55 48 37 10 84 36 55 48 37 10 60 84 i i i i i i i i j j j j j j j j i j 初始关键字序列: (1) (2) (3) (4) (5) (6) (7) (8) 第一次快速排序过程 4、快速排序算法分析： 时间效率：O(nlog2n) —因为每趟确定的元素呈指数增加 空间效率：O（log2n）—因为递归要用栈(存每层 low，high 和 pivot)稳 定 性： 不 稳 定 —因为有跳跃式交换。 【本讲课程的小结】插入排序和交换排序是常见的两类排序方法，对于这两类排序算法的 思想我们应该熟练掌握，对于它们各自的特点（时间复杂度、空间复杂度和稳定性）要有
所了解，这是我们遇到实际问题选择排序算法的依据，【本讲课程的作业】编写实现单链表上的直接插入排序函数
所了解，这是我们遇到实际问题选择排序算法的依据。 【本讲课程的作业】 编写实现单链表上的直接插入排序函数