Chapter10——排序讲解.ppt

第十章 排序;10.1 概述;10.1 概 述;一、什么是排序？;一般情况下， 假设含n个记录的序列为{ R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn };排序算法的稳定性： 如果待排序的序列中，存在多个具有相同关键字的记录，若经过排序这些记录的相对次序保持不变，则称这种排序算法是稳定的；经过排序这些记录的相对次序发生了改变，则称这种排序算法是不稳定的。;二、内部排序和外部排序;三、内部排序的方法;按排序过程中依据的不同原则 插入排序 交换排序 选择排序 归并排序 基数排序 按排序过程所需的工作量 简单的排序方法，其时间复杂度为O(n2) 先进的排序方法，其时间复杂度为O(nlogn) 基数排序，其时间复杂度为O(d.n);1. 插入类;2. 交换类;3. 选择类;4. 归并类;待排记录的数据类型定义如下:; 10. 2 插 入 排 序;一趟直接插入排序的基本思想：;有序序列R[1..i-1];实现“一趟插入排序”可分三步进行：;直接插入排序（基于顺序查找）;一、直接插入排序;从R[i-1]起向前进行顺序查找， 监视哨设置在R[0]；; 对于在查找过程中找到的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动；;令 i = 2，3，…, n, 实现整个序列的排序。;直接插入排序示例;void InsertionSort ( SqList L ) { // 对顺序表 L 作直接插入排序 for ( i=2; i=L.length; ++i ) if (L.r[i].key L.r[i-1].key) { } } // InsertSort;内部排序的时间分析：;对于直接插入排序：;对于直接插入排序：其时间复杂度为O(n2); 因为 R[1..i-1] 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。;void BiInsertionSort ( SqList L ) { } // BInsertSort;low = 1; high = i-1; while (low=high) { };14 36 49 52 80;对于折半插入排序，其时间复杂度为O(n2) 折半插入排序适用于当待排序记录的数量很大时，可大幅度降低关键字的比较次数。; 三、希尔排序(又称缩小增量排序);将记录序列分成若干子序列，分别对每个子序列进行插入排序。;初始关键字 49 38 65 97 76 13 27 49 55 04 49 13 38 27 65 49 97 55 76 04 ;void ShellInsert ( SqList L, int dk ) { for ( i=dk+1; i=n; ++i ) if ( L.r[i].key L.r[i-dk].key) { L.r[0] = L.r[i]; // 暂存在R[0] for (j=i-dk; j0(L.r[0].keyL.r[j].key); j-=dk) L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置 L.r[j+dk] = L.r[0]; // 插入 } // if } // ShellInsert;void ShellSort (SqList L, int dlta[], int t) { // 增量为dlta[ ]的希尔排序 for (k=0; kt; ++t)