第十章内部排序(白底黑字).ppt

10.1 概 述 1、排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~ 2、排序分类 按待排序记录所在位置 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序 按排序依据原则 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 基数排序 10.1 概 述 按排序所需工作量 简单的排序方法：T(n)=O(n2) 先进的排序方法：T(n)=O(nlogn) 基数排序：T(n)=O(d.n) 排序基本操作 比较两个关键字大小 将记录从一个位置移动到另一个位置 10.1 概 述 10.1 概 述 10.1 概 述 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.3 快速排序 10.3 快速排序 10.3 快速排序 2、快速排序 基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序 排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key 初始时令i=s,j=t 首先从j所指位置向前有哪些信誉好的足球投注网站第一个关键字小于x的记录，并和rp交换 再从i所指位置起向后有哪些信誉好的足球投注网站，找到第一个关键字大于x的记录，和rp交换 重复上述两步，直至i==j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止 10.3 快速排序 10.3 快速排序 10.3 快速排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 2、堆排序 堆的定义：n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆 10.4 选择排序 堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫~ 堆排序需解决的两个问题： (1)如何由一个无序序列建成一个堆？ (2)如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 第二个问题解决方法——筛选 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选” 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 【算法10.10】 void HeapAdjust(Sqlist *h，int s，int m) {/*r[s…m]中的记录关键码除r[s]外均满足堆的定义，本函数将对第s个结点为根的 子 树筛选，使其成为大顶堆*/ rc=h-r[s]； for(j=2*s；j=m；j=j*2) /* 沿关键码较大的子女结点向下筛选 */ { if(jmh-r[j].keyh-r[j+1].key) j=j+1； /* 为关键码较大的元素下标*/ if(rc.key=h-r[j].key) break； /* rc应插入在位置s上*/ h-r[s]=h-r[j]； s=j； /* 使s结点满足堆定义 */ } h-r[s]=rc； /* 插入 */ } void HeapSort(Sqlist *h) { for(i=h-length/2；i0；i- -) /* 将r[1..length]建成堆 */ HeapAdjust(h，i，h-length)； for(i=h-length；i1；i--) { h-r[1]--h-r[i]； /* 堆顶与堆低元素交换 */ HeapAdjust(h，1，i-1)； /*将r[1..i-1]重新调整为堆*/ } } 10.4 选择排序 10.5 归并排序 归并排序 归并——将两个或两个以上的有序表组合成一个新的有序表，叫~ 2-路归并排序 排序过程 设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1 两两合并，得到?n/2