数据结构之排序算法讲解.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.r[
显示全部