数据结构——c语言 8种排序方法比较

  戳这里还有其他数据结构的题目噢

https://blog.csdn.net/qq_45724947/article/details/115625130?spm=1001.2014.3001.5501

在完善12.11.4参考源程序”的基础上,进行典型内部排序算法的比较。

(1)随机产生整数样本，进行8种排序，并比较各种排序算法的执行时间，如执行时间均为0,可考虑增大样本，如加大至5000或10000。

(2)设计方案，修改“12.11.4 参考源程序”，对8种排序算法的数据元素比较次数和移动次数进行比较。

(3)修改12.11.4参考源程序”，输出8种排序算法每一趟排序的输 出结果。

 涉及到的8种排序方法：冒泡排序 ，选择排序， 直接插入排序， 希尔排序， 快速排序， 堆排序， 归并排序， 折半插入。

 直接上代码：

# include <stdio.h>
# include <stdlib.h>
# include <time.h>
#include <windows.h>
#define WIDTH 20
#define MAXK 10
int n=0;
long num,compare;
int da[2000000];
int dd[2000000];
void myhead(){
printf("**
排序算法比较
**n");
printf("===========================n");
printf("**
1 ---冒泡排序
**n");
printf("**
2 ---选择排序
**n");
printf("**
3 ---直接插入排序 **n");
printf("**
4 ---希尔排序
**n");
printf("**
5 ---快速排序
**n");
printf("**
6 ---堆排序
**n");
printf("**
7 ---归并排序
**n");
printf("**
8 ---折半插入排序 **n");
printf("**
9 ---退出程序
**n");
printf("===========================n");
printf("n");
}
void myrand(){
int i;
srand((unsigned)time(NULL)); /*随机种子*/
for(i = 0; i < n; i ++)
dd[ i ] = rand();
}
void myinit(){
int i;
for(i = 0; i < n; i ++) da[ i ] = dd[ i ];
num=0;
compare=0;
}
void swap(int *a,int *b){
int temp;
temp=*a;
*a=*b;
*b=temp;
num++;
}
void mymaopao(){
int i,j,k=0;
for(i=0;i<n-1;i++)
for(j=n-1;j>i;j--){
compare++;
if(da[j]<da[j-1])
swap(&da[j],&da[j-1]);
}
}
void myxuanzhe(){
int i,j,temp;
for(i=0;i<n-1;i++){
temp=i;
for(j=i+1;j<n;j++){
compare++;
if(da[j]<da[temp]){temp=j;num++;}
}
if(temp!=i)swap(&da[temp],&da[i]);
}
}
void mycharu(){
int i,j;
int temp=0;
for(i = 1; i < n ; i++){
temp = da[i];
for(j = i; j > 0&& temp < da[j - 1]; j--){
compare++;
if(temp < da[j - 1])
swap(&da[j],&da[j-1]);
}
da[j] = temp;
}
}
void myxier(){
int i, j, k;
int temp, gap;
for (gap = n / 2; gap > 0; gap /= 2){
for (i = 0; i < gap; i++){
for (j = i + gap; j < n; j += gap){
if (da[j] < da[j - gap]){
temp = da[j];
k = j - gap;
while (k >= 0 && da[k] > temp){
da[k + gap] = da[k];
k -= gap;
}
da[k + gap] = temp;
num++;
}
compare++;
}
}
}
}
void myqsort(int l,int r) {
int i, j, x;
if (l < r){
i = l;
j = r;
x = da[i];
while (i < j){
while(i < j && da[j] > x) {
j--;compare++;
}
if(i < j) da[i++] = da[j];
while(i < j && da[i] < x) {
i++;compare++;
}
if(i < j) da[j--] = da[i];
}
da[i] = x;
num++;
myqsort(l, i-1);
myqsort(i+1, r);
}
}
void mykuaisu(){
myqsort(0,n);
}
void HeapAdjust(int i, int nLength){
int nChild, nTemp;
for (nTemp = da[i]; 2 * i + 1 < nLength; i = nChild){
nChild = 2 * i + 1;
compare++;
if (nChild != nLength - 1 && da[nChild + 1] > da[nChild])
++nChild;
if (nTemp < da[nChild]){
da[i] = da[nChild];
num++;
}else{
break;
}
}
da[i] = nTemp;
}
void mydui(){
int i;
for (i = n / 2 - 1; i >= 0; --i){
HeapAdjust(i, n);
}
for (i = n - 1; i > 0; --i){
swap(&da[0], &da[i]);
HeapAdjust(0, i);
}
}
void Merge(int left, int m, int right){
int aux[200000] = {0};
int i;
int j;
int k;
for (i = left, j = m+1, k = 0; k <= right-left; k++){
num++;
compare++;
if (i == m+1){
aux[k] = da[j++];
continue;
}
if (j == right+1){
aux[k] = da[i++];
continue;
}
if (da[i] < da[j]){
aux[k] = da[i++];
}else{
aux[k] = da[j++];
}
}
for (i = left, j = 0; i <= right; i++, j++){
da[i] = aux[j];
}
}
void MergeSort(int start,int end){
if (start < end){
int i;
i = (end + start) / 2;
MergeSort(start, i);
MergeSort(i + 1, end);
Merge(start, i, end);
}
}
void myguibing(){
MergeSort(0,n-1);
}
void myzhebancharu(){
int left=0,right=n;
int low,high,mid;
int temp;
for(int i=left+1;i<=right;++i){
temp=da[i];
low=left;
high=i-1;
while(low<=high){
mid=(low+high)/2;
if(da[i]<da[mid])
high=mid-1;
else
low=mid+1;
compare++;
}
for(int j=i-1;j>=low;--j)
da[j+1]=da[j];
da[low]=temp;
num++;
}
}
int main()
{
clock_t tt1,tt2;
double tt;
myhead();
printf("请输入要产生的随机数的个数（不超过10000）：");
scanf("%d",&n);
myrand();
printf("n");
int flag = 1;
while (flag){
myinit();
printf("n");
printf("请选择排序算法：");
int ch;
scanf("%d", &ch);
switch(ch){
case 1 :
tt1=clock();
mymaopao();
tt2=clock();
tt = (double)(tt2-tt1)/CLOCKS_PER_SEC;
printf("冒泡排序所用时间：
%f秒n",tt);
printf("冒泡排序所用交换次数：
%ldn",num);
printf("冒泡排序所用比较次数：
%ldn",compare);
break;
case 2 :
tt1=clock();
myxuanzhe();
tt2=clock();
tt = (double)(tt2-tt1)/CLOCKS_PER_SEC;
printf("选择排序所用时间：
%f秒n",tt);
printf("选择排序所用交换次数：
%ldn",num);
printf("选择排序所用比较次数：
%ldn",compare);
break;
case 3 :
tt1=clock();
mycharu();
tt2=clock();
tt = (double)(tt2-tt1)/CLOCKS_PER_SEC;
printf("插入排序所用时间：
%f秒n",tt);
printf("插入排序所用交换次数：
%ldn",num);
printf("插入排序所用比较次数：
%ldn",compare);
break;
case 4 :
tt1=clock();
myxier();
tt2=clock();
tt = (double)(tt2-tt1)/CLOCKS_PER_SEC;
printf("希尔排序所用时间：
%f秒n",tt);
printf("希尔排序所用交换次数：
%ldn",num);
printf("希尔排序所用比较次数：
%ldn",compare);
break;
case 5 :
tt1=clock();
mykuaisu();
tt2=clock();
tt = (double)(tt2-tt1)/CLOCKS_PER_SEC;
printf("快速排序所用时间：
%f秒n",tt);
printf("快速排序所用交换次数：
%ldn",num);
printf("快速排序所用比较次数：
%ldn",compare);
break;
case 6 :
tt1=clock();
mydui();
tt2=clock();
tt = (double)(tt2-tt1)/CLOCKS_PER_SEC;
printf("堆排序所用时间：
%f秒n",tt);
printf("堆排序所用交换次数：
%ldn",num);
printf("堆排序所用比较次数：
%ldn",compare);
break;
case 7 :
tt1=clock();
myguibing();
tt2=clock();
tt = (double)(tt2-tt1)/CLOCKS_PER_SEC;
printf("归并排序所用时间：
%f秒n",tt);
printf("归并排序所用交换次数：
%ldn",num);
printf("归并排序所用比较次数：
%ldn",compare);
break;
case 8 :
tt1=clock();
myzhebancharu();
tt2=clock();
tt = (double)(tt2-tt1)/CLOCKS_PER_SEC;
printf("折半插入所用时间：
%f秒n",tt);
printf("折半插入所用交换次数：
%ldn",num);
printf("折半插入所用比较次数：
%ldn",compare);
break;
case 9 : flag = 0;
}
}
return 0;
}

 （代码如有雷同，可能存在借鉴他人部分代码情况）

（请不要直接复制使用。总结的代码仅供参考，希望读者借此代码自身可以理解学习）

如果代码对您有帮助，不要忘记评论收藏噢~

最后

以上就是细心蜡烛为你收集整理的数据结构——c语言 8种排序方法比较的全部内容，希望文章能够帮你解决数据结构——c语言 8种排序方法比较所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。