数据结构第十章内部排序讲解.ppt
文本预览下载声明
第10章 内部排序;待排序列的数据存储类型
#define MAXSIZE 20
typedef int KeyType ;
typedef struct {
KeyType key ;
InfoType otherinfo ;
} RedType ;
typedef struct {
RedType r [ MAXSIZE + 1 ] ;//r[0]闲置
int length ;
} SqList ;
;10.2 插入排序;10.2 插入排序;算法评价：;2、其它插入排序;2、其它插入排序; 2-路插入排序; 表插入排序;增加n个辅助空间 n个指针域;增加n个辅助空间 n个指针域;表插入排序重排记录算法
void Arrange ( SLinkListType SL )
{ p = SL.r[ 0 ].next ;
for ( i = 1 ; i SL.length ; ++i ) {
while ( p i ) p = SL.r[ p ].next ;
q = SL.r[ p ].next ;
if ( p != i ) {
SL.r[ p ] ←→ SL.r[ i ] ;
SL.r[ i ].next = p ;
}
p = q ;
}
}
;希尔排序
直接插入排序的时间复杂度为O(n2)，但若待排记录为正序时，则时间复杂度为O(n)，若“基本有序”，则可提高效率。另外在n较小时，算法效率较高且简单。;取d3=1
三趟分组：;增量的选择;10.3 快速排序;void sort ( SqList L )
{ for ( i = 1 ; i = L.length - 1 ; i ++ ) {
flag = FALSE ;
for ( j = 1 ; j = L.length – i ; j ++ ) {
if ( L.r[ j ].key L.r[ j + 1 ].key ) {
L.r[ j ] -- L.r[ j + 1 ] ;
flag = TRUE ;
}
}
if ( ! flag ) break ;
}
};算法评价：;2、快速排序;例;int Partition ( SqList L , int low , int high )
{ L.r[ 0 ] = L .r[ low ] ;
pivotkey = L.r[ low ].key ;
while ( low high ) {
while (lowhighL.r[high].key=pivotkey) - - high ;
L.r[ low ] = L.r[ high ] ;
while (lowhighL.r[low].key=pivotkey) + + low ;
L.r[high] = L.r[low] ;
}
L.r[ low ] = L.r[ 0 ] ;
return low ;
};void Qsort ( SqList L , int low , int high )
{ if ( low high ) {
pivotloc = Partition ( L , low , high ) ;
Qsort ( L , low , pivotloc – 1 ) ;
Qsort (L , pivotloc + 1 , high ) ;
}
}
;算法评价：;10.4 选择排序;简单选择排序算法;算法评价：;2、树形选择排序;2、树形选择排序;3、堆排序;堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序
堆排序需解决的两个问题：
如何由一个无序序列建成一个堆？
如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？
第二个问题解决方法——筛选
方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”;例;49;76;第一个问题解决方法
方法：从无序序列的第
显示全部