#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 ;
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<L.r[j].key; --j ){
L.r[j+1]=L.r[j]; //记录后移
}
L.r[j+1]=L.r[0]; //插入到正确位置
}
}
}
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; k<t; ++k)
ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序
}//ShellSort
void ShellInsert(SqList &L,int dk){//对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子
for(i=dk+1; i<=L.length; ++i)
if(r[i].key < r[i-dk].key) {
r[0]=r[i];
for(j=i-dk; j>0 &&(r[0].key<r[j].key); j=j-dk)
r[j+dk]=r[j];
r[j+dk]=r[0];
}
}
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
}
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;
}
void SelectSort(SqList &K){
for (i=1; i<L.length; ++i){
k=i;
for(j=i+1; j<=L.length; j++)
if( L.r[j].key<L.r[k].key) k=j;//记录最小值位置
if(k!=i) L.r[i]<-->L.r[k]; //交换
}
}
void HeapAdjust (elem R[ ], int s, int m) {
/*已知R[s..m]中记录的关键字除R[s]之外均满足堆的定义，本函数调整R[s]的关键字，使R[s..m]成为一个大根堆*/
rc = R[s];
for ( j=2*s; j<=m; j *= 2){ //沿key较大的孩子结点向下筛选
if (j<m && R[j]<R[j+1])
++j; //j为key较大的记录的下标
if ( rc >= 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
mg-1mJQMHaH-1642926930837)]
[外链图片转存中…(img-6sMyUKaa-1642926930838)]
[外链图片转存中…(img-YzZfpCPR-1642926930838)]
[外链图片转存中…(img-daIMOOOn-1642926930838)]
[外链图片转存中…(img-xFufCyXy-1642926930839)]
[外链图片转存中…(img-zQEhGCaz-1642926930839)]
[外链图片转存中…(img-Hf6aaGqW-1642926930840)]
[外链图片转存中…(img-u4bbceay-1642926930841)]
[外链图片转存中…(img-c4E2GNAw-1642926930841)]