《排序的基本概念》由会员分享，可在线阅读，更多相关《排序的基本概念（34页珍藏版）》请在金锄头文库上搜索。
1、9.1 排序的基本概念 9.2 插入排序 9.3 选择排序 9.4 交换排序 9.5 归并排序 9.6 基数排序 9.7 性能比较第第9 9章章 排序排序19.1排序的基本概念 1.排序: 将一组杂乱无章的数据按一定的规律顺次排列 起来的过程。 存放在数据表中按关键字排序2. 排序的目的：便于查找。 3.排序算法好坏的衡量标准： (1)时间复杂度 它主要是分析记录关键字的比较次数和记 录的移动次数。 (2)空间复杂度算法中使用的内存辅助空间的多少。 (3)稳定性若两个记录A和B的关键字值相等，但排序后A、B 的先后次序保持不变，则称这种排序算法是稳定的。 4、排序的种类：分为内部排序和外部排序
2、两大类。若待排序记录都在内存中，称为内部排序；若待排序 记录一部分在内存，一部分在外存，则称为外部排序 。注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外 存，显然外部排序要复杂得多。 25.待排序记录在内存中怎样存储和处理？ 顺序排序排序时直接移动记录； 链表排序排序时只移动指针； 地址排序排序时先移动地址，最后再移动记录 。注：地址排序中可以增设一维数组来专门存放记录的地址 。6. 内部排序的算法有哪些？ 按排序的规则不同，可分为5类：插入排序、交换排序、选择排序、归并排序、基数排序按排序算法的时间复杂度不同，可分为3类：v简单的排序算法：时间效率低，O(n2) v先进的
3、排序算法: 时间效率高，O( nlog2n ) v基 数 排 序 算法：时间效率高，O( dn)d关键字的位数(长度)39.2 插入排序插入排序的基本思想是：每步将一个待排序的对象，按 其关键码大小，插入到前面已经排好序的一组对象的适当位 置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。常用的插入排序有：直接插入排序和希尔排序两种。一、直接插入排序1、其基本思想是：顺序地把待排序的数据元素按其关键字值的大小插入到已排 序数据元素子集合的适当位置。最简单的排序法！最简单的排序法！4初始关键字序列：【13】, 6, 3, 31, 9, 27, 5, 11 第一次排序
4、： 【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】 例1：关键字序列T=（13，6，3，31，9，27，5，11），请写出直接插入排序的中间过程序列。注：方括号 中为已排
5、序记录的关键字，下划横线的 关键字 表示它对应的记录后移一个位置。52、C语言程序 void InsertSort(DataType a, int n) /*用直接插入法对a0-an-1排序*/ int i, j; DataType temp; for(i = 0; i -1 typedef struct KeyType key; DataType; #define MaxSize 100 #include “SeqList.h“7(1)时间效率： 因为在最坏情况下，所有元素的比较次数总 和为（01n-1)O(n2)。其他情况下也要 考虑移动元素的次数。 故时间复杂度为O(n2) (2)空间效
6、率：仅占用1个缓冲单元O O（1 1） (3)算法的稳定性：稳定3、直接插入排序算法分析二、希尔（二、希尔（shellshell）排序排序 （又称缩小增量排序） 1、基本思想：把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过程结束。 2、技巧：小组的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个小组,让增量dk逐趟缩短（例如依次取5,3,1），直到dk1为止。3、优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。8例2：设待排序的序列中
7、有12个记录，它们的关键字序列 T=(65 ，34，25，87，12，38，56，46，14，77，92，23），请写 出希尔排序的具体实现过程。算法分析：开始时d 的值较大，子序列中的对象较少，排序速度 较快；随着排序进展，d 值逐渐变小，子序列中对象个数 逐渐变多，由于前面工作的基础，大多数记录已基本有序 ，所以排序速度仍然很快。通常，di+1=di/2 (结果取整）时间效率：O(n(log2n)2)空间效率：O（1）因为仅占用1个缓冲单元算法的稳定性：不稳定下面给出希尔排序的具体实现过程：9第1趟 (d=6)第2趟 (d=3)第3趟 (d=1)104、C语言程序 void ShellSo
8、rt(DataType a, int n, int d, int numOfD) int i, j, k, m, span; DataType temp; for(m = 0; m -1 temp = aj; aj = aj+1; aj+1 = temp; 294、冒泡排序的算法分析 最好情况：初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动对象。 最坏情形：初始排列逆序，算法要执行n-1趟起泡，第i趟 (1 i n) 做了n- i 次关键码比较，执行了n-i 次对象交换 。此时的比较总次数KCN和记录移动次数RMN为：因此： 时间效率：O（n2) 因为要考虑最坏情况 空间效
9、率：O（1） 只在交换时用到一个缓冲单元 稳 定 性： 稳定 25和25*在排序前后的次序未改变30二、快速排序 1、基本思想：从待排序列中任取一个元素 (例如取第一个) 作 为中心，所有比它小的元素一律前放，所有比它大的元素一律 后放，形成左右两个子表；然后再对各子表重新选择中心元素 并依此规则调整，直到每个子表的元素只剩一个。此时便为有 序序列了。 2、优点：因为每趟可以确定不止一个元素的位置，而且呈指数 增加，所以特别快。 例7、关键字序列 T=(60，55，48，37，10，90，84，36），请按从小到大的顺序，写出快速排序的具体实现过程。31第一次快速排序过程323、C语言实现 v
10、oid QuickSort(DataType a, int low, int high) int i = low, j = high; DataType temp = alow; while(i j) while(i j if(i j) ai = aj; i+; while(i j if(i j) aj = ai; j-; ai = temp; if(low i) QuickSort(a, low, i-1); if(i high) QuickSort(a, j+1, high); 33时间效率：O(nlog2n) 因为每趟确定的元素呈指数增加空间效率：O（log2n）因为递归要用栈(存每层low，high 和pivot)稳 定 性： 不 稳 定 因为有跳跃式交换。4、快速排序算法分析：34
