1. 基本概念和排序方法概述
1.1 排序方法的分类1.2 存储结构 (顺序表) 2. 插入排序
2.1 插入排序的种类
直接插入折半插入希尔排序 3. 交换排序
3.1 冒泡排序3.2 快速排序 4. 选择排序
4.1 直接排序4.2 堆排序
堆的调整堆的建立
5. 归并排序6. 基数排序7. 外部排序7. 外部排序
#define MAXSIZE20 //设记录不超过20个
typedef int KeyType ; //设关键字为整型量(int型)
Typedef struct { //定义每个记录（数据元素)的结构
KeyType key ; //关键字
InfoType otherinfo; //其它数据项
}RedType ; //Record Type
Typedef struct { //定义顺序表的结构
RedType r[ MAXSIZE+1 ];//存储顺序表的向量
//r[0]一般作哨兵或缓冲区
int length ;/顺序表的长度
}SqList ;
2. 插入排序
2.1 插入排序的种类
直接插入
void InsertSort( SqList &L ) {
int i, j;
for (i=2; i<=L.length; ++i) {
if (L.r[i].key < L.r[i-1].key){ //若"<",需将L.r[i]插入有序子表
L.r[O]=L.r[i]; //复制为哨兵
for (j=i-1; L.r[O].key
折半插入
void BInsertSort ( SqList &L ) {
for ( i = 2; i<= L.length ; ++i ){//依次插入第2~第n个元素
L.r[0] = L.r[i]; //当前插入元素存到“哨兵”位置
low = 1 ; high = i-1; //采用二分查找法查找插入位置
while ( low <= high ) {
mid = ( low + high ) / 2 ;
if ( L.r[O].key < L.r[mid]. key ) high = mid -1
else low = mid + 1;
}//循环结束，high+1则为插入位置
for ( j=i-1; j>=high+1; --j){
L.r[j+1] = L.r[j];//移动元素
L.r[high+1] = L.r[0];//插入到正确位置
}
}
}// BInsertSort
希尔排序
void ShellSort (Sqlist &L, int dlta[],int t){
//按增量序列dlta[0..t-1]对顺序表L作希尔排序。
for(k=0; k0 &&(r[0].key
3. 交换排序
3.1 冒泡排序
void bubble_sort(SqList &L){//冒泡排序算法
int m,i,j; RedType x; //交换时临时存储
for(m=1; m<=n-1; m++){ //总共需m趟
for(j=1; j<=n-m; j++)
if(L.r[j].key>L.r[j+1].key){//发生逆序
x=L.r[j];
L.r[j]=L.r[j+1];
L.r[j+1]=x;//交换
}//endif
}//for
}
void bubble_sort(SqList &L){//改进的冒泡排序算法
int m,ij,flag=1; RedType x; //flag作为是否有交换的标记
for(m=1; m<=n-1&&flag==1; m++){
flag=0;
for(j=1; j<=m; j++)
if(L.r[j].key>L.r[j+1].key){//发生逆序
flag=1; //发生交换，flag置为1，若本趟没发生交换，flag保持为0
x=L.r[j];
L.r[j]=L.r[j+1];
L.r[j+1]=x;//交换
}//endif
}//for
}
3.2 快速排序
void main ( ) {
QSort ( L,1,L.length );
}
void QSort (SqList &L, int low, int high){//对顺序表L快速排序
if (low < high){ //长度大于1
pivotloc = Partition(L, low, high);
//将L.r[low..high]一分为二，pivotloc为枢轴元素排好序的位置
QSort(L, low, pivotloc-1);//对低子表递归排序
QSort(L, pivotloc+1, high);//对高子表递归排序
}//endif
} // QSort
int Partition ( SqList &L,int low, int high ) {
L.r[0] = L.r[low];
pivotkey = L.r[low].key;
while ( low < high ) {
while ( low < high && L.r[high].key >= pivotkey )
--high;
L.r[low] = L.r[high];
while ( low < high && L.r[low].key <= pivotkey )
++low;
L.r[high] = L.r[low];
}
L.r[low]=L.r[O];
return low;
}
4. 选择排序
4.1 直接排序
void SelectSort(SqList &K){
for (i=1; iL.r[k]; //交换
}
}
4.2 堆排序
堆的调整
void HeapAdjust (elem R[ ], int s, int m) {
rc = R[s];
for ( j=2*s; j<=m; j *= 2){ //沿key较大的孩子结点向下筛选
if (j= R[j] )
break;
R[s] = R[j];
s = j; //rc应插入在位置s上
}//for
R[s] = rc;//插入
}// HeapAdjust
堆的建立
void HeapSort ( elem R[ ] ){//对R[1]到R[n]进行堆排序
int i;
for ( i = n/2 ; i>= 1; i -- )
HeapAdjust ( R ,i , n );//建初始堆
for ( i = n; i >1 ; i - - ) {//进行n - 1趟排序
Swap ( R[1], R[i] );//根与最后一个元素交换
HeapAdjust ( R,1,i -1);//对R[1]到R[i-1]重新建堆}
}//HeapSort
5. 归并排序
6. 基数排序
7. 外部排序
mg-1mJQMHaH-1642926930837)]
[外链图片转存中…(img-6sMyUKaa-1642926930838)]
[外链图片转存中…(img-YzZfpCPR-1642926930838)]
[外链图片转存中…(img-daIMOOOn-1642926930838)]
7. 外部排序
[外链图片转存中…(img-xFufCyXy-1642926930839)]
[外链图片转存中…(img-zQEhGCaz-1642926930839)]
[外链图片转存中…(img-Hf6aaGqW-1642926930840)]
[外链图片转存中…(img-u4bbceay-1642926930841)]
[外链图片转存中…(img-c4E2GNAw-1642926930841)]
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）