截图
简介
这是数据结构基数排序ppt，包括了内部排序，概述，插入排序，交换排序，选择排序，归并排序，基数排序，什么是排序等内容，欢迎点击下载。
数据结构基数排序ppt是由红软PPT免费下载网推荐的一款课件PPT类型的PowerPoint.
数据结构课程的内容
第10章 内部排序
10.1 概述
10.1 概述
4. 什么叫内部排序？什么叫外部排序？
6. 顺序存储（顺序表）的抽象数据类型如何表示？
7. 内部排序的算法有哪些？
10.2 插入排序
1) 直接插入排序
例2：关键字序列T= （21，25，49，25*，16，08）， 请写出直接插入排序的具体实现过程。
Void InsertSort(SqList &L)
{ // 对顺序表L做直接插入排序
for ( i=2; i<=L.length; ++i )
if ( LT(L.r[i].key，L.r[i-1].key) )
// “<“，需将L.r[i]插入有序子表
{ L.r[0] = L.r[i]; // 复制为哨兵
L.r[i] = L.r[i-1];
for( j=i-2; LT(L.r[0].key，L.r[i].key);--j )
L.r[ j+1] = L.r[ j]; // 记录后移
L.r[ j+1] = L.r[0]; // 插入到正确位置
}
} // InsertSort
直接插入排序的算法分析
2） 折半插入排序
Void BInsertSort (SqList &L) // 折半插入排序
{ for ( i=2；i<=L.length；++i )
{ L.r[0] = L.r[ i ]； // 将L.r [i] 暂存到L.r[0]
low=1；high=i-1；
while (low<=high) // 比较，折半查找插入位置
{ m=(low+high)/2； // 折半
if (LT(L.r[0].key，L.r[m].key)) high=m-1；//插入点在低半区
else low=m+1； // 插入点在高半区
} // while
for (j=i-1；j>=high+1；--j) L.r [j+1] = L.r [j]；// 记录后移
L.r [high+1] = L.r [0]； // 插入
} // for
} // BInsertSort
折半插入排序的算法分析
讨论：若记录是链表结构，用直接插入排序行否？折半插入排序呢？
答：直接插入不仅可行，而且还无需移动元素，时间效率更高！但链表无法“折半”！
折半插入排序的改进——2-路插入排序见教材P267。
（1）基本思想： P267
（2）举 例：P268 图10.2
（3）算法分析：移动记录的次数约为n2/8
2-路插入排序只能减少移动记录的次数，而不能绝对避免移动记录。实现是借助循环向量。
=> 若希望在排序过程中不移动记录，只有改变存储结构，进行表插入排序。
4）希尔（shell）排序（又称缩小增量排序）
例：关键字序列 T=(49，38，65，97， 76， 13， 27， 49*，55， 04），请写出希尔排序的具体实现过程。
时间效率：
附：希尔排序算法分析
希尔排序算法（其中某一趟的排序操作）
课堂练习：
原始序列： 256，301，751，129，937，863，742，694，076，438
原始序列： 256，301，751，129，937，863，742，694，076，438
10.3 交换排序
1) 冒泡排序
for(j=0;j<n;j++)
for(i=0;i<n-1-j;i++)
if (a[i]>a[i+1]) // 需要互换
{
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
冒泡排序的算法分析
2） 快速排序
例1：关键字序列 T=(21，25，49，25*，16，08），请写出快速排序的算法步骤。
讨论1.这种不断划分子表的过程，计算机如何自动实现？
例2：关键字序列 T=(21，25，49，25*，16，08），请写出快速排序算法的一趟实现过程。
一趟快速排序算法流程图
整个快速排序的递归算法：
例3：以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法的各趟排序结束时，关键字序列的状态。
快速排序算法详细分析：
讨论2. “快速排序”是否真的比任何排序算法都快？
10.4 选择排序
1）简单选择排序
例：关键字序列T= （21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。
简单选择排序的算法如下：（亦可参见教材P276）
2） 锦标赛排序 (又称树形选择排序)
第一趟：
第二趟：
第三趟：
第四趟：
第五趟：
第六趟：
第七趟：
算法分析：
3） 堆排序
例：
2. 怎样建堆？
Void HeapAdjust(HeapType &H， int s，int m)
{ //
rc = H.r[s];
for ( j=2*s; j<=m; j*=2) // 沿key较大的孩子结点向下筛选
{ if ( j<m && LT(H.r[ j].key， H.r[ j+1].key) )
++j ; // j 为key较大的记录的下标
if (!LT(rc.key，H.r[ j].key)) break; // rc应插入在位置s上
H.r[s] = H.r[ j]; s=j;
}
H.r[s]=rc; // 插入
}
3. 怎样进行堆排序？
例：对刚才建好的大根堆进行排序：
堆排序的算法
附1：基于初始堆进行堆排序的算法步骤：
附2： 算法流程
堆排序算法分析：
10.5 归并排序
一趟归并排序算法: (两路有序并为一路) 参见教材P283
递归形式的两路归并排序算法: 参见教材P284 (一路无序变为有序)
归并排序算法分析：
各种内部排序方法的比较 (教材P289）
讨论：若初始记录基本无序，则选用哪些排序方法比较适合？若初始记录基本无序，则最好选用哪些排序方法？
展开
