实验一常见排序算法的实现与性能比较
一、实验环境
操作系统：Windows XP操作系统
编程语言：C语言
开发工具：Microsoft Visual C++ 6.0
二、问题描述
实现合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序算法
三、实验要求
A．在随机产生的空间大小分别为N = 10， 1000，10000，100000 的排序样本（取值为[0,1]）上测试以上算法。
B．结果输出:
1） N=10时，排序结果。
2） N=1000，10000，100000时，对同一个样本实例，不同排序完
成所需的时间。
3） N=1000，10000，100000时，每个排序用不同的样本多试验几次（最低5次）得出平均时间，比较不同排序算法所用的平均时间。
四、各种排序算法的原理及算法语言描述
（1）合并排序算法
1）合并排序的原理：
采用分治法。分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括n/2 个元素。治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作。合并: 合并两个排好序的子序列,生成排序结果。
2）合并排序算法语言描述：
void Merge(float A[],int p,int q,int r){
int n1,n2,i,j,k;
float L[10],R[10];
n1=q-p+1;
n2=r-q;
for(i=1;i<=n1;i++){
L[i]=A[p+i-1];
}
for(j=1;j<=n2;j++){
R[j]=A[q+j];
}
L[n1+1]=MAX;
R[n2+1]=MAX;
i=1;
j=1;
for(k=p;k<=r;k++){
if(L[i]<=R[j]){
A[k]=L[i];
i++;
}
else{
A[k]=R[j];
j++;
}
}
}
void Merge_sort(float A[],int p,int r){
int q;
if(pq=(p+r)/2;
Merge_sort(A,p,q);
Merge_sort(A,q+1,r);
Merge(A,p,q,r);
}
}
（2）插入排序算法
1）插入排序原理：
依次将待排的数据插入到已经排好的数组中合适的位置，使已排好数组依然是有序的，直到所有待排数据插入完毕。
2）插入排序算法语言描述：
void Insertion_sort(float A[],int n){ //要排序得数组A和A的长度n
int i,j;
float key;
for(j=1;jkey=A[j];
i=j-1;
while(i>=0&&A[i]>key){
A[i+1]=A[i];
i--;
}
A[i+1]=key;
}
}
（3）希尔排序算法
1）希尔排序原理：
首先取一个小于n的增量d1,将待排数据分成n/d1个组，其中距离
为d1的数据分在同一个组内。现在组内进行直接插入排序，取第二个增量d22）希尔排序算法语言描述：
Shell_sort(float A[],int n){ //数组A与数组的长度n int i,j,step;
float key;
for(step=n/2;step>0;step=step/2){ //step为步长，初始为n/2,每次减半
for(i=step;ikey=A[i];
j=i-step;
while(j>=0&&A[j]>key){
A[j+step]=A[j];
j=j-step;
}
A[j+step]=key;
}
}
}
（4）快速排算法
1）快速排序原理：
任找一个元素作为基准，对待排数组进行分组，使基准元素左边的数据比基准数据要小，右边的数据比基准数据要大，这样基准元素就放在了正确的位置上。然后对基准元素左边和右边的组进行相同的操作，最后将数据排序完成。
2）快速排算法语言描述：
void Quick_sort(float A[],int left,int right){
int i,j;
float key;
i=left;
j=right;
key=A[i];
while(iwhile(i=key){
j--;
}
A[i]=A[j];
while(ii++;
}
A[j]=A[i];
}
A[i]=key;
if(leftQuick_sort(A,left,i-1);
}
if(right>i+1){
Quick_sort(A,i+1,right);
}
}
（5）冒泡排序算法
1）冒泡排序原理：
两两比较待排序数据元素的大小，若发现两个数据元素的次序相反则进行交换，直到没有反序的数据为止。
2）冒泡排序算法语言描述：
void Bubble_sort(float A[],int n){
int i,j;
int flag;//作为是否发生变化的标志
float t;
for(i=0;iflag=0;
for(j=n-1;j>i;j--){
if(A[j]t=A[j-1];
A[j-1]=A[j];
A[j]=t;
flag=1;
}
}
if(flag==0){
return;
}
}
}
（6）桶排序算法
1）桶排序算法原理：
首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M 的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]....B[M]中的全部内容即是一个有序序列。
2）桶排序算法语言描述：
//桶排序算法思想：设置一个二维数组B[100][],将待排数组A[]中的数据根据小数点后的第一、二位数值0-99存入相应数组B[0-99][]中
//然后在数组B[0-99][]中进行快速排序，排好后再复制回数组A中
