《内部排序-数据结构DATASTRUCTURE》由会员分享，可在线阅读，更多相关《内部排序-数据结构DATASTRUCTURE（49页珍藏版）》请在装配图网上搜索。
1、 数据结构数据结构 计算机科学与技术学院计算机科学与技术学院课程代码：06000602第十章第十章 排序排序课程代码：0600060310.1 概述概述课程代码：06000604课程代码：06000605课程代码：06000606#define Maxsize 50 /待排序序列中记录的最大个数待排序序列中记录的最大个数 待排序表中每个数据元素的数据类型定义待排序表中每个数据元素的数据类型定义typedef struct int key;/表示排序关键字表示排序关键字 elemtype otherinfo;/排序记录中的其他所有数据项排序记录中的其他所有数据项 Snode;待排序数据表的数据类
2、型定义待排序数据表的数据类型定义typedef struct Snode RMaxsize+1;/存放待排序全体记录存放待排序全体记录 int length;/排序记录个数排序记录个数 SList;课程代码：06000607 插入排序插入排序(Insert Sorting)直接插入排序直接插入排序课程代码：06000608课程代码：06000609课程代码：060006010 void InsertSort(SqList&L)for(i=2；i=L.length；i+)if(L.Ri.key L.Ri-1.key)/小于时小于时,将将Ri插入有序表插入有序表 L.R0=L.Ri；/R0作监测哨
3、兵作监测哨兵 for(j=i-1；L.R0.key=1&change;i-)change=0;for(j=0;j aj+1)Swap(j+1,j);change=1;课程代码：060006018课程代码：0600060191111123121nininninnnin)()(3)()(课程代码：060006020 快速排序快速排序(Quick Sort)课程代码：060006021课程代码：060006022。课程代码：06000602310.4 选择排序选择排序课程代码：060006024 直接选择排序直接选择排序课程代码：060006025课程代码：060006026)(21)(211nni
4、nni课程代码：060006027 树型选择排序树型选择排序课程代码：060006028课程代码：060006029 堆排序堆排序1 1）堆的定义：）堆的定义：n n个元素的序列个元素的序列(R1,R2,Rn),(R1,R2,Rn),对应对应的关键字序列为的关键字序列为(k1,k2,kn)(k1,k2,kn)，若此关键字序，若此关键字序列满足下列关系，则称该元素序列为堆。列满足下列关系，则称该元素序列为堆。或或(i=1,2,.n/2)ki k2iki k2i+1ki k2iki k2i+1例例 (96,83,27,38,11,9）例例 (13,38,27,50,76,65,49,97)9627
5、91138831327384965765097可将堆序列看成完全二叉树，则堆顶可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中元素（完全二叉树的根）必为序列中n n个元素的最小值或最大值个元素的最小值或最大值课程代码：0600060302)2)堆排序基本思想堆排序基本思想课程代码：060006031课程代码：0600060324 4）初建堆）初建堆 自下而上自下而上3 3）堆调整）堆调整 自上而下自上而下课程代码：060006033课程代码：060006034课程代码：060006035 归并排序归并排序(Merge Sort)课程代码：060006036课程代码：060006
6、037例例初始关键字：初始关键字：49 38 65 97 76 13 27一趟归并后：一趟归并后：38 49 65 97 13 76 27二趟归并后：二趟归并后：38 49 65 97 13 27 76三趟归并后：三趟归并后：13 27 38 49 65 76 97课程代码：060006038课程代码：060006039课程代码：060006040 基数排序基数排序(分配排序分配排序)课程代码：060006041课程代码：060006042diiiKKK ,21djjjdiiiKKKKKK ,2121课程代码：060006043diKdiK课程代码：060006044课程代码：06000604
7、5 各种排序方法的比较各种排序方法的比较 比比较较次次数数 移移动动次次数数 附附加加存存储储 排排 序序 方方 法法 最最好好 最最差差 最最好好 最最差差 稳稳定定 性性 最最好好 最最差差 直直接接插插入入排排序序 n n2 0 n2 1 SHELL排排序序 n log2n 0 n2 1 起起泡泡排排序序 n n2 0 n2 1 快快速速排排序序 nlog2n n2 n log2n n2 log2n n 简简单单选选择择排排序序 n2 0 n 1 堆堆排排序序 n log2n n log2n 1 归归并并排排序序 n log2n n log2n n 基基数数排排序序 d(n+rd)n+2
8、rd 课程代码：060006046本章小结本章小结 需要复习的知识点需要复习的知识点u 排序的基本概念排序的基本概念u 关键字、初始关键字排列关键字、初始关键字排列u 关键字比较次数、数据移动次数关键字比较次数、数据移动次数u 稳定性稳定性u 直接插入排序、直接插入排序、Shell排序的过程排序的过程u 直接插入排序的算法直接插入排序的算法u 排序的性能分析排序的性能分析当待排序的关键字序列已经基本有序时，用直接插入当待排序的关键字序列已经基本有序时，用直接插入排序最快排序最快 课程代码：060006047u直接选择排序、堆排序的过程直接选择排序、堆排序的过程u直接选择排序的算法直接选择排序的
9、算法u性能分析性能分析 用直接选择排序在一个待排序区间中选出最小用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，不是顺次的数据时，与区间第一个数据对调，不是顺次后移。这导致方法不稳定。后移。这导致方法不稳定。在堆排序中将待排序的数据组织成完全二叉树在堆排序中将待排序的数据组织成完全二叉树的顺序存储。的顺序存储。课程代码：060006048u 用事例表明起泡排序和快速排序的过程用事例表明起泡排序和快速排序的过程u 起泡排序算法，快速排序的起泡排序算法，快速排序的递归算法递归算法和和非非递归算法递归算法u二路归并排序的过程二路归并排序的过程u二路归并排序的非递归算法二路归并排序的非递归算法u该算法的性能分析该算法的性能分析 u基数排序的思想、方法基数排序的思想、方法课程代码：060006049
内部排序-数据结构DATASTRUCTURE
