实验项目名称：实验六 内部排序
一、 实验目的
1.掌握插入排序的方法及效率分析
2.掌握选择排序的方法及效率分析
3.掌握交换排序的方法及效率分析
4.掌握归并排序的方法及效率分析
二、 实验内容
6-4 快速排序
本题要求实现快速排序的一趟划分函数，待排序列的长度1<=n<=1000。
函数接口定义：
int Partition ( SqList L, int low, int high )；
其中L是待排序表，使排序后的数据从小到大排列。
###类型定义：
typedef int KeyType;typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList;
裁判测试程序样例：
#include<stdio.h>#include<stdlib.h>typedef int KeyType;typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList;void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ int Partition ( SqList L,int low, int high );void Qsort ( SqList L,int low, int high );int main(){ SqList L; int i; CreatSqList(&L); Qsort(L,1,L.Length); for(i=1;i<=L.Length;i++) printf("%d ",L.elem[i]); return 0;}void Qsort ( SqList L,int low, int high ) { int pivotloc; if(low<high) { pivotloc = Partition(L, low, high ) ; Qsort (L, low, pivotloc-1) ; Qsort (L, pivotloc+1, high ); }}/*你的代码将被嵌在这里 */
输入样例：
第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：
10
5 2 4 1 8 9 10 12 3 6
输出样例：
输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。
1 2 3 4 5 6 8 9 10 12
6-5 堆排序
本题要求实现堆排序中的筛选函数，待排序列的长度1<=n<=1000。
函数接口定义：
void HeapAdjust( HeapType H, int s, int m);
其中L是待排序表，使排序后的数据从小到大排列。
###类型定义：
typedef int KeyType;typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList;typedef SqList HeapType;
裁判测试程序样例：
#include<stdio.h>#include<stdlib.h>typedef int KeyType;typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList;typedef SqList HeapType; void CreatSqListHeapType *L);/*待排序列建立，由裁判实现，细节不表*/ void HeapAdjust( HeapType H, int s, int m);void HeapSort( HeapType H);int main(){ HeapType L; int i; CreatSqList(&L); HeapSort(L); for(i=1;i<=L.Length;i++) { printf("%d ",L.elem[i]); } return 0;}void HeapSort( HeapType H){ /*堆顺序表H进行堆排序*/ int i; KeyType rc; /*建立初始堆*/ for( i=H.Length/2;i>0; i--) { HeapAdjust(H, i, H.Length); } for(i=H.Length;i>1;i--) { rc=H.elem[1]; H.elem[1]=H.elem[i]; H.elem[i]=rc; HeapAdjust(H, 1, i-1); } }/*你的代码将被嵌在这里 */
输入样例：
第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：
10
5 2 4 1 8 9 10 12 3 6
输出样例：
输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。
1 2 3 4 5 6 8 9 10 12
6-6 归并排序
本题要求实现二路归并排序中的归并操作，待排序列的长度1<=n<=1000。
函数接口定义：
void Merge(SqList L,int low,int m,int high);
其中L是待排序表，使排序后的数据从小到大排列。
###类型定义：
#include<stdio.h>#include<stdlib.h>typedef int KeyType;typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList;void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ void MergeSort(SqList L,int low,int high);void Merge(SqList L,int low,int m,int high); int main(){ SqList L; int i; CreatSqList(&L); MergeSort(L,1,L.Length); for(i=1;i<=L.Length;i++) { printf("%d ",L.elem[i]); } return 0;}void MergeSort(SqList L,int low,int high) { /*用分治法进行二路归并排序*/ int mid; if(low<high) /*区间长度大于1*/ { mid=(low+high)/2; /*分解*/ MergeSort(L,low,mid); /*递归地对low到mid序列排序 */ MergeSort(L,mid+1,high); /*递归地对mid+1到high序列排序 */ Merge(L,low,mid,high); /*归并*/ } }/*你的代码将被嵌在这里 */
输入样例：
第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：
10
5 2 4 1 8 9 10 12 3 6
输出样例：
输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。
1 2 3 4 5 6 8 9 10 12
6-7 直接插入排序
本题要求实现直接插入排序函数，待排序列的长度1<=n<=1000。
函数接口定义：
void InsertSort(SqList L);
其中L是待排序表，使排序后的数据从小到大排列。
###类型定义：
typedef int KeyType;typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList;
裁判测试程序样例：
#include<stdio.h>#include<stdlib.h>typedef int KeyType;typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList;void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ void InsertSort(SqList L);int main(){ SqList L; int i; CreatSqList(&L); InsertSort(L); for(i=1;i<=L.Length;i++) { printf("%d ",L.elem[i]); } return 0;}/*你的代码将被嵌在这里 */
输入样例：
第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：
10
5 2 4 1 8 9 10 12 3 6
输出样例：
输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。
1 2 3 4 5 6 8 9 10 12
6-8 希尔排序的实现
本题要求实现一趟希尔排序函数，待排序列的长度1<=n<=1000。
函数接口定义：
void ShellInsert(SqList L,int dk);
其中L是待排序表，使排序后的数据从小到大排列。
###类型定义：
typedef int KeyType;typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList;
裁判测试程序样例：
#include<stdio.h>#include<stdlib.h>typedef int KeyType;typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList;void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ void ShellInsert(SqList L,int dk);void ShellSort(SqList L);int main(){ SqList L; int i; CreatSqList(&L); ShellSort(L); for(i=1;i<=L.Length;i++) { printf("%d ",L.elem[i]); } return 0;}void ShellSort(SqList L){ /*按增量序列dlta[0…t-1]对顺序表L作Shell排序,假设规定增量序列为5,3,1*/ int k; int dlta[3]={5,3,1}; int t=3; for(k=0;k<t;++k) ShellInsert(L,dlta[k]);} /*你的代码将被嵌在这里 */
输入样例：
第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：
10
5 2 4 1 8 9 10 12 3 6
输出样例：
输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。
1 2 3 4 5 6 8 9 10 12
三、 设计文档
四、 源程序
1.
int Partition ( SqList L,int low, int high ){
int temp=L.elem[low];
while(low<high)
{
while(low<high&&L.elem[high]>=temp){
high--;
}
if(low<high){
L.elem[low]=L.elem[high];
low++;
}
while(low<high&&L.elem[low]<temp){
low++;
}
if(low<high){
L.elem[high]=L.elem[low];
high--;
}
}L.elem[low]=temp;
return low;
}
2.
void HeapAdjust( HeapType H, int s, int m){
KeyType a;
int i;
a=H.elem[s];
for(i=2*s;i<=m;i*=2){
if(i<m&&H.elem[i]<H.elem[i+1]) ++i;
if(a>=H.elem[i]) break;
H.elem[s]=H.elem[i]; s=i;
}
H.elem[s]=a;
}
3.
void Merge(SqList L,int low,int m,int high){
int i,j,now;
i=low;
j=m+1;
now=1;
int a[10000];//开个数组保存中间比较过程
while (i<=m&&j<=high){
if(L.elem[i]<=L.elem[j]){
a[now++]=L.elem[i++];
}
else{
a[now++]=L.elem[j++];
}
}
while (i<=m) a[now++]=L.elem[i++];
while (j<=high) a[now++]=L.elem[j++];
for (i=low,now=1;i<=high;i++){
L.elem[i]=a[now++];
}
}
4.
void InsertSort(SqList L){
int i,j;
for(i=1;i<=L.Length;i++){
L.elem[0]=L.elem[i];
for(j=i;L.elem[j-1]>L.elem[0]&&j>0;j--)
L.elem[j]=L.elem[j-1];
L.elem[j]=L.elem[0];
}
}
5.
void ShellInsert(SqList L,int dk){
for(int i=dk+1;i<=L.Length;i++){//elem[0]是哨兵
if(L.elem[i-dk]>L.elem[i]){
L.elem[0]=L.elem[i-dk];
L.elem[i-dk]=L.elem[i];
L.elem[i]=L.elem[0];
i=dk+1;
}
}
}
标签：排序,int,void,elem,算法,low,SqList,数据结构 From： https://www.cnblogs.com/DREAM2021/p/16976183.html