定它?4.排序定义 若给定一组记录序列r1,r,,…,rn,其排序码分别 为s1 ,sn,将这些记录排成顺序为rk 2,…,rm的一个序列R,满足条件s1≤2≤…≤Sn, 获得这些记录排成顺序为rn,rn2,…,rmn的一个序 列R,满足条件25…m的过程称为排序。 也可以说,将一组记录按某排序码递增或递减排列的 过程,称为排序 5.稳定与不稳定 因为排序码可以不是记录的关键字,同一排序码值可能对应 多个记录。对于具有同一排序码的多个记录来说,若采用的 排序方法使排序后记录的相对次序不变,则称此排序方法是 稳定的,否则称为不稳定的。在上例中(见表9-1,按年龄排 序),如果一种排序方法使排序后的结果必为前一个结果, 则称此方法是稳定的;若一种排序方法使排序后的结果可能 为后一个结果,则称此方法是不稳定的
4．排序定义 若给定一组记录序列r 1 ，r 2 ，…，r n，其排序码分别 为s1，s2 ，…，sn ，将这些记录排成顺序为r k1 ， r k2 ，…，r kn的一个序列R’，满足条件sk1 ≤sk2 ≤ …≤skn， 获得这些记录排成顺序为r p1 ，r p2 ，…，r pn的一个序 列R”，满足条件sp1 ≤sp2 ≤ …≤spn的过程称为排序。 也可以说，将一组记录按某排序码递增或递减排列的 过程，称为排序。 5．稳定与不稳定 因为排序码可以不是记录的关键字，同一排序码值可能对应 多个记录。对于具有同一排序码的多个记录来说，若采用的 排序方法使排序后记录的相对次序不变，则称此排序方法是 稳定的，否则称为不稳定的。在上例中（见表9-1，按年龄排 序），如果一种排序方法使排序后的结果必为前一个结果， 则称此方法是稳定的；若一种排序方法使排序后的结果可能 为后一个结果，则称此方法是不稳定的
6.内排序与外排序 按照排序过程中使用内外存的不同将排序方法分为内排序 和外排序。若排序过程全部在内存中进行,则称为内排序 若排序过程需要不断地进行内存和外存之间的数据交换 则称为外排序。内排序大致可分为五类:插入排序、交换 排序、选择排序、归并排序和分配排序。本章仅讨论内排 序 入7.排序的时间复杂性 排序过程主要是对记录的排序码进行比较和记录的移动过 程。因此排序的时间复杂性可以算法执行中的数据比较次 数及数据移动次数来衡量。当一种排序方法使排序过程在 最坏或平均情况下所进行的比较和移动次数越少,则认为 该方法的时间复杂性就越好,分析一种排序方法,不仅要 分析它的时间复杂性,而且要分析它的空间复杂性、稳定 性和简单性等
6．内排序与外排序 按照排序过程中使用内外存的不同将排序方法分为内排序 和外排序。若排序过程全部在内存中进行，则称为内排序； 若排序过程需要不断地进行内存和外存之间的数据交换， 则称为外排序。内排序大致可分为五类：插入排序、交换 排序、选择排序、归并排序和分配排序。本章仅讨论内排 序。 7．排序的时间复杂性 排序过程主要是对记录的排序码进行比较和记录的移动过 程。因此排序的时间复杂性可以算法执行中的数据比较次 数及数据移动次数来衡量。当一种排序方法使排序过程在 最坏或平均情况下所进行的比较和移动次数越少，则认为 该方法的时间复杂性就越好，分析一种排序方法，不仅要 分析它的时间复杂性，而且要分析它的空间复杂性、稳定 性和简单性等
它:?为了以后讨论方便,我们直接将排序码写成一个一维数 ′组的形式,具体类型设为 Elemtype,并且在没有声明的情 形下,所有排序都按排序码的值递增排列 插入排序(直插排序、二分排序、希尔排序) 交换排序(冒泡排序、快速排序) 排序选择排序(直选排序、树型排序、堆排序) 归并排序(二路归并排序、多路归并排序) 分配排序(多关键字排序、基数排序)
为了以后讨论方便，我们直接将排序码写成一个一维数 组的形式，具体类型设为Elemtype，并且在没有声明的情 形下，所有排序都按排序码的值递增排列。 排序 插入排序（直插排序、二分排序、希尔排序） 交换排序（冒泡排序、快速排序） 选择排序 （直选排序、树型排序、堆排序） 归并排序（二路归并排序、多路归并排序） 分配排序 （多关键字排序、基数排序）
∴:?9.2插入排序 921直接插入排序 1,直接插入排序的基本思想 直接插入排序( Straight Insertion Sorting)的基本思想是:把 n个待排序的元素看成为一个有序表和一个无序表,开始时 有序表中只包含一个元素,无序表中包含有n-1个元素,排序 入过程中每次从无序表中取出第一个元素,把它的排序码依次 与有序表元素的排序码进行比较,将它插入到有序表中的适 当位置,使之成为新的有序表。 2.直接插入的算法实现
9．2 插入排序 9.2.1直接插入排序 1．直接插入排序的基本思想 直接插入排序（Straight Insertion Sorting）的基本思想是：把 n个待排序的元素看成为一个有序表和一个无序表，开始时 有序表中只包含一个元素，无序表中包含有n-1个元素，排序 过程中每次从无序表中取出第一个元素，把它的排序码依次 与有序表元素的排序码进行比较，将它插入到有序表中的适 当位置，使之成为新的有序表。 2．直接插入的算法实现
void insertsort(ElemType R[l,int n) 待排序元素用个数组R表示,数组有n个元素 for(inti=1;i<mn;i+)作表示插入次数,共进行n1次 插入 ElemType temp=R[];∥把待排序元素赋给temp while((>=0)&&(temp<RiD) R[i+1]-Ri];j-;}∥顺序比较和移动 RL+ll=temp; i
void insertsort(ElemType R[],int n) //待排序元素用一个数组R表示，数组有n个元素 { for ( int i=1; i<n; i++) //i表示插入次数，共进行n-1次 插入 { ElemType temp=R[i]; //把待排序元素赋给temp int j=i-1; while ((j>=0)&& (temp<R[j])) { R[j+1]=R[j]; j--; } // 顺序比较和移动 R[j+1]=temp;} }