数据结构之排序算法资料.ppt

;注意带以下内容： 图2-8-1 图2-8-2 图2-8-3 图2-8-4 图2-8-5 ;第二章?数据结构与算法;2.8 排 序 2.8.1 概 述;假设待排序的记录存放在地址连续的一组存储单元中，那么这种存储方式下的数据类型可描述为： ;排序方法;2.8.2 插入排序 直接插入、折半插入;2.8.2 插入排序 直接插入、折半插入;void insertSort(RedType L[ ],int n) { int i ,j; for(i=2; i=n; i++) if(L[i].keyL[i-1].key) { L[0]=L[i]; /* 作为监视哨*/ for( j=i-1; L[0].keyL[j].key; ? ?j ) L[j+1]=L[j]; /* 记录后移*/ L[j+1]=L[0]; /* 插入 */ } };2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置 。待排序元素越多，改进效果越明显。;2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个???较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。;void BinsertSort(RedType L[ ],int n) { int i,low,high,mid; for(i=2; i=n; ++i){ L[0]=L[i]; /* r[0]作为监视哨*/ low=1; high=i-1; While(low=high) {mid=(low+high)/2; if (L[0].keyL[mid].key) high=mid-1; //插入点在低半区 else low=mid+1; } for( j=i-1; j=high+1; ? ?j ) L[j+1]=L[j]; /* 记录后移*/ L[high+1]=L[0]; /* 插入*/ } /* for*/ }/*折半插入排序*/; 1、简单选择排序 思想：首先从1~n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2 个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。 时间复杂度为O(n2)， 适用于待排序元素较少的情况。;2.8.3 选择排序 简单选择排序、堆排序。 1、简单选择排序 思想：首先从1~n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2 个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。 时间复杂度为O(n2)， 适用于待排序元素较少的情况。;简单选择排序的算法如下： void SelectSort( RedType L[ ],int n) { int i,j,k,t; for (i=1,i=n;++i） /*选择第i小的元素，并交换到位*/ { k=i； for(j=i+1;j=n;++j) if ( L[j].keyL[k].key) k=j; /*L[k] 中存放的是第I小的元素*/ if(k!=i) { t=L[i]; /*交换*/ L[i]=L[k]; L[k]=t ；} } /*FOR*/ } /* SelectSort*/ ;?2?????堆排序　也是一种选择排序。是具有特定条件的顺序存储的完全二叉树，其特定条件是：任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。 (1) 堆的示例 ; (3) 输出堆顶元素并调整建新堆的过程(筛选);（4）由无序序列建初始堆的过程;E、筛选算法（调整建堆） typedef Sqlist HeapType; //堆采用顺序表存储表示 void HeapAdjust( HeapType H, int s, int m){ // 已知H.r[s..m]中记录的关键字除H.