NOI排序算法课程胶片

1、排序1. 冒泡排序2. 快速排序3. 直接插入排序4. 希尔排序5. 选择排序6. 小结冒泡排序算法描述设待排序记录序列中的记录个数为n一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录的关键字，如果发生逆序，则交换之其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。算法示例10 1 2 3 4 5算法示例20 1 2 3 4 5总体演示初始关键字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序算法实现输入n 个数给a1 到 anfor j=1 to n-1for i=1 to n-jaiai+1真假aiai+1输出a1 到 an#inclu

2、de main() int a11,i,j,t; printf(Input 10 numbers:n); for(i=1;i11;i+) scanf(%d,&ai); printf(n); for(j=1;j=9;j+) for(i=1;iai+1) t=ai; ai=ai+1; ai+1=t; printf(The sorted numbers:n); for(i=1;i11;i+) printf(%d ,ai); 1. 冒泡排序2. 快速排序3. 直接插入排序4. 希尔排序5. 选择排序6. 小结快速排序 快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成

3、两部分一部分所有记录的关键码大于等于支点记录的关键码另一部分所有记录的关键码小于支点记录的关键码 算法描述任取待排序记录序列中的某个记录(例如取第一个记录)作为基准(枢),按照该记录的关键字大小,将整个记录序列划分为左右两个子序列左侧子序列中所有记录的关键字都小于或等于基准记录的关键字 右侧子序列中所有记录的关键字都大于基准记录的关键字基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止。基准记录也称为枢轴（或支点）记录。取序列第一个记录为枢轴记录，其关键字为Pivotkey指针low指向序列第一个记录位置指

4、针high指向序列最后一个记录位置算法示例1始关键字pivotkey一次交换二次交换三次交换high-1完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh算法示例212完成一趟排序分别进行快速排序有序序列算法分析快速排序是一个递归过程;利用序列第一个记录作为基准，将整个序列划分为左右两个子序列。只要是关键字小于基准记录关键字的记录都移到序列左侧；快速排序的趟数取决于递归树的高度。如果每次划分对一个记录定位后, 该记录的左侧子序列与右侧子序列的长度相同, 则下一步将是对两个长度减半的子序列进行排序, 这是最理想的情况 131. 冒泡排序2. 快速排序

5、3. 直接插入排序4. 希尔排序5. 选择排序6. 小结直接插入排序 算法描述：记录存放在数组R0.n-1中，排序过程的某一中间时刻，R被划分成两个子区间R0i-1和Ri.n-1，其中：前一个子区间是已排好序的有序区；后一个子区间则是当前未排序的部分。基本操作将当前无序区的第1个记录Ri插入到有序区R0.i-1中适当的位置，使R0i变为新的有序区 直接插入排序 操作细节：当插入第i(i1)个对象时, 前面的r0, r1, , ri-1已经排好序。用ri的关键字与ri-1, ri-2, 的关键字顺序进行比较(和顺序查找类似)，如果小于，则将rx向后移动(插入位置后的记录向后顺移)找到插入位置即将

6、ri插入直接插入排序 实用例子：已知待序的一组记录的初始排列为：21, 25, 49, 25*, 16, 080 1 2 3 4 5算法示例0 1 2 3 4 5 temp250 1 2 3 4 5 temp4925*0 1 2 3 4 5算法示例0 1 2 3 4 5 temp160 1 2 3 4 5 temp080 1 2 3 4 5完成算法实现void InsertSort (int r , int n ) / 假设关键字为整型，放在向量r中 int i, j, temp; for (i = 1;i0;j- -) /从后向前顺序比较，并依次后移 if ( temp rj-1 ) rj

7、= rj-1; else break; rj = temp; 算法分析关键字比较次数和记录移动次数与记录关键字的初始排列有关。最好情况下, 排序前记录已按关键字从小到大有序, 每趟只需与前面有序记录序列的最后一个记录比较1次, 移动2次记录, 总的关键字比较次数为 n-1, 记录移动次数为 2(n-1)在平均情况下的关键字比较次数和记录移动次数约为 n2/4。直接插入排序是一种稳定的排序方法直接插入排序最大的优点是简单，在记录数较少时，是比较好的办法1. 冒泡排序2. 快速排序3. 直接插入排序4. 希尔排序5. 选择排序6. 小结希尔排序 希尔排序又称缩小增量排序是1959年由D.L.She

8、ll提出来的 算法描述首先取一个整数 gap n(待排序记录数) 作为间隔, 将全部记录分为 gap 个子序列, 所有距离为 gap 的记录放在同一个子序列中在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap, 例如取 gap = gap/2重复上述的子序列划分和排序工作，直到最后取gap = 1, 将所有记录放在同一个序列中排序为止。算法示例已知待排序的一组记录的初始排列为：21, 25, 49, 25*, 16, 080 1 2 3 4 5 算法示例t 30 1 2 3 4 50 1 2 3 4 5t 2t 1算法分析开始时 gap 的值较大, 子序列中的记录较少, 排序速度较快随

9、着排序进展, gap 值逐渐变小, 子序列中记录个数逐渐变多,由于前面大多数记录已基本有序, 所以排序速度仍然很快Gap的取法有多种。 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。1. 冒泡排序2. 快速排序3. 直接插入排序4. 希尔排序5. 选择排序6. 小结排序过程首先通过n-1次比较，从n个数中找出最小的， 将它与第一个数 交换第一趟选择排序，结果最小的数被安置在第一个元素位置上再通过n-2次比较，从剩余的n-1个数中找出关键字次小的记录，将它与第二个数交换第二趟选择排序重复上述过程，共经过n-1趟排序后，排序结束排序示例初始：初始： 49 38

10、 65 97 76 13 27 kji=11349一趟：一趟： 13 38 65 97 76 49 27 i=22738二趟：二趟： 13 27 65 97 76 49 38 三趟：三趟： 13 27 38 97 76 49 65 四趟：四趟： 13 27 38 49 76 97 65 五趟：五趟： 13 27 38 49 65 97 76 六趟：六趟： 13 27 38 49 65 76 97 kkkkjjjjjjjjjj算法示例0 1 2 3 4 5算法示例0 1 2 3 4 5最小者最小者各趟排序后的结果算法示例0 1 2 3 4 5i =2时选择排序的过程i k j i k j i k

11、 j 算法示例0 1 2 3 4 5i k j 算法实现输入n 个数给a1 到 anfor i=1 to n-1for j=i+1 to najak真假k=j输出a1 到 ank=iaiaki != k真假#include main() int a11,i,j,k,x; printf(Input 10 numbers:n); for(i=1;i11;i+) scanf(%d,&ai); printf(n); for(i=1;i10;i+) k=i; for(j=i+1;j=10;j+) if(ajak) k=j; if(i!=k) x=ai; ai=ak; ak=x; printf(The s

12、orted numbers:n); for(i=1;i11;i+) printf(%d ,ai); 1. 冒泡排序2. 快速排序3. 直接插入排序4. 希尔排序5. 选择排序6. 小结36基本概念排序排序（Sorting）： 简单地说，排序就是把一组记录一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。（如按年龄从小到大排序）学号姓名年龄性别2004001张佳18男2004002王鹏19男2004003刘宁17女2004004李娟18女2004005陈涛19男2004006李小燕18女37作为比较基础的一个(或多个)字段，称为排序码排序码。排序码可以

13、是数值、符号或符号串。排序码排序码不一定是关键码，是关键码，关键码可以作为排序码。关键码是唯一的，但排序码不一定唯一。排序码不唯一时，排序的结果可能不唯一。参与排序的对象，称为记录。一个记录可以包含多个字段。如果记录集合中存在多个排序码排序码相同的记录，经过排序后，排序码排序码相同的记录的前后次序保持不变，则这种排序方法称为是稳定稳定的，否则是不稳定不稳定的。排序码 与 关键码（primary key）38 排序方法可以分为五种 插入插入排序、选择选择排序、交换交换排序、分配分配排序和归并归并排序。 在排序过程中，全部记录存放在内存，则称为内排序内排序，如果排序过程中需要使用外存，则称为外排序。外排序。排序的类型评价排序算法好坏的标准 执行算法所需的时间 执行算法所需要的附加空间 算法本身的复杂程度也是考虑的一个因素排序的时间开销时间开销是算法好坏的最重要的标志排序的时间开销衡量标准: 算法执行中的比较次数（必须）。 算法执行中的移动次数（有可能避免）。通常会关注最坏情况和平均情况的开销。排序算法的评价39阶段小节几种