数据结构-程序员联合开发网.ppt

第三章第三章 内部排序算法内部排序算法 3.1 3.1 直接插入排序直接插入排序 3.2 3.2 希尔排序 3.3 3.3 冒泡排序 3.4 3.4 快速排序 3.5 3.5 简单选择排序 3.6 3.6 归并排序归并排序 第六章 首页上页下页退出 分类： 内部排序：全部记录都可以同时调入内存进 行的排序。 外部排序：文件中的记录太大，无法全部将 其同时调入内存进行的排序。 第六章 首页上页下页退出 内内 部部 排排 序序 插入排序插入排序 交换排序交换排序 选择排序选择排序 归并排序归并排序 基数排序基数排序 有序表中插入元素，并保持其有序 将表中关键字比较，位置不对交换 先查找关键字，再交换。 将两个有序的关键字序列进行归并 不比较，按多关键字排序方法 直接折半2-路表希尔 冒泡快速 简单树型堆 第六章 首页上页下页退出 3.1 3.1 直接插入排序直接插入排序 直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序 列中第1个记录看成是一个有序子序列，然后从第 2个记录开始，逐个进行插入，直至整个序列有序 第六章 首页上页下页退出 例 49 38 65 97 76 13 27 i=2 38 (38 49) 65 97 76 13 27 i=3 65 (38 49 65) 97 76 13 27 i=4 97 (38 49 65 97) 76 13 27 i=5 76 (38 49 65 76 97) 13 27 i=6 13 (13 38 49 65 76 97) 27 i=1 ( ) i=7 (13 38 49 65 76 97) 2727 jjjjjj 977665493827 (13 27 38 49 65 76 97)排序结果： 第六章 首页上页下页退出 typedef struct int key; float info; JD; void straisort(JD r,int n) int i,j; for(i=2;ir2.key， 则交换；然后比较第二个记录与第三个记录 ；依次类推，直至第n-1个记录和第n个记录 比较为止第一趟冒泡排序，结果关键字 最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果 使关键字次大的记录被安置在第n-1个记录位 置 重复上述过程，直到“在一趟排序过程中没 有进行过交换记录的操作”为止 第六章 首页上页下页退出 例 49 38 65 97 76 13 27 30 初始关键字 38 49 65 76 13 27 30 97 第一趟 38 49 65 13 27 30 76 第二趟 38 49 13 27 30 65 第三趟 38 13 27 30 49 第四趟 13 27 30 38 第五趟 38 49 76 9713 9727 9730 97 13 76 76 76 27 30 13 6527 6530 65 13 13 49 4930 4927 3827 3830 38 1 2 3 4 5 6 7 8 第六章 首页上页下页退出 void bubble_sort(JD r,int n) int m,i,j,flag=1; JD x; m=n-1; while(m0) for(j=1;jrj+1.key) flag=1; x=rj; rj=rj+1; rj+1=x; m-; 注:冒泡排序等价与沉底算法 第六章 首页上页下页退出 3.4快速排序 基本思想： 通过一趟排序，将某关键字通过比较直 接到位，并将待排序记录分割成独立的 两部分，其中一部分记录的关键字均比 另一部分记录的关键字小，则可分别对 这两部分记录进行排序，以达到整个序 列有序 第六章 首页上页下页退出 排序过程：对rst中记录进行一趟快速排 序，附设两个指针i和j，设枢轴记录rp=rs， x=rp.key 初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小 于x的记录，并和rp交换 再从i所指位置起向后搜索，找到第一个关 键字大于x的记录，和rp交换 重复上述两步，直至i=j为止 再分别对两个子序列进行快速排序，直到每 个子序列只含有一个记录为止 第六章 首页上页下页退出 例 初始关键字： 49 38 65 97 76 13 27 50 ij x ji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 97 4927 i ji j ij 4965 j i 1349 i j 4997 ij 第六章 首页上页下页退出 例 初始关键字： 49 38 65 97 76 13 27 50 ij x.key=49 ji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 27 i ji j ij 65 j i 13 i j 49 97 ij 第六章 首页上页下页退出 void qksort(JD r,int s,int t) int i,j,k