【问题描述】
从标准输入中输入一组互不相同的整数（个数不超过100）及排序方式，按照从小到大排序，输出按某种算法排序的结果及元素的比较次数。
说明：排序方式为一个1~5的整数，分别表示：
1：选择排序，比较次数是指选择未排序部分的最小元素时的比较次数。
2：冒泡排序，比较次数是指相邻元素的比较次数，若某趟排序中没有进行数据交换，就认为排序结束。
3：堆排序，比较次数是指根元素调整过程中根元素与子树根结点的比较次数，即下面算法中红色语句的执行次数：
void adjust(int k[ ],int i,int n)
{
int j,temp;
temp=k[i];
j=2*i+1;
while(j<n){
if(j<n-1 && k[j]<k[j+1])
j++;
if(temp>=k[j])
break;
k[(j-1)/2]=k[j];
j=2*j+1;
}
k[(j-1)/2]=temp;
}4：二路归并排序，比较次数是指两组有序数据合并成一组时的比较次数，即下面算法中红色语句的执行次数：
void merge(int x[ ],int tmp[ ],int left,int leftend,int rightend)
{
int i=left, j=leftend+1, q=left;
while(i<=leftend && j<=rightend)
{
if(x[i]<=x[j])
tmp[q++]=x[i++];
else
tmp[q++]=x[j++];
}
while(i<=leftend)
tmp[q++]=x[i++];
while(j<=rightend)
tmp[q++]=x[j++];
for(i=left; i<=rightend; i++)
x[i]=tmp[i];
}5：快速排序，比较次数是指分界元素与其它元素的比较次数，即下面算法中红色语句的执行次数：
void quickSort(int k[ ],int left,int right)
{
int i, last;
if(left<right){
last=left;
for(i=left+1;i<=right;i++)
if(k[i]<k[left])
swap(&k[++last],&k[i]);
swap(&k[left],&k[last]);
quickSort(k,left,last-1);
quickSort(k,last+1,right);
}
}【输入形式】
首先在屏幕上输入2个整数，分别表示待排序的整数个数及排序方式，然后在下一行依次输入待排序的整数。各整数之间都以一个空格分隔。
【输出形式】
先在一行上输出排序结果，各整数间以一个空格分隔。然后在下一行上输出排序过程中的元素比较次数。
【样例1输入】
20 1
38 356 98 -102 126 46 65 -9 100 0 21 2 90 8 18 12 78 16 189 23【样例1输出】
-102 -9 0 2 8 12 16 18 21 23 38 46 65 78 90 98 100 126 189 356
190【样例1说明】
输入了20个整数数据，要求按照选择排序算法对输入的数据进行从小到大排序，输出排序结果，排序过程中元素的比较次数为190次。
【其它样例说明】
若输入的待排序数据与样例1完全相同，要求的排序算法不同，则输出的排序结果与样例1完全一样，但比较次数不同，为了方便说明，下面左侧为排序方式，右侧为对应的比较次数：
2 162
3 58
4 66
5 75【评分标准】
该题要求按照指定算法对输入的数据进行排序。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 1010
int num[maxn];
int merge_temp[maxn];
int cmp_times;
void selectSort(int k[],int n);
void bubbleSort(int k[],int n);
void adjust(int arr[],int low,int high);
void heapSort(int arr[],int n);
void Merge(int a[],int s,int m,int e,int b[]);
void MergeSort(int a[],int s,int e,int b[]);
void quickSort(int v[],int left,int right);
void swap(int v[],int i,int j);
int main()
{
int n,sort_way,i;
scanf("%d %d",&n,&sort_way);
for( i=0;i<n;i++){
scanf("%d",&num[i]);
}
cmp_times=0;
switch(sort_way){
case 1:
selectSort(num,n);
break;
case 2:
bubbleSort(num,n);
break;
case 3:
heapSort(num,n);
break;
case 4:
MergeSort(num,0,n-1,merge_temp);
break;
case 5:
quickSort(num,0,n-1);
break;
}
for( i=0;i<n;i++){
printf("%d ",num[i]);
}
printf("\n%d\n",cmp_times);
return 0;
}
void selectSort(int k[],int n)
{
int i,j,d;
int temp;
for(i=0;i<n-1;i++){
d=i;
for(j=i+1;j<n;j++){
if(k[j]<k[d]){
d=j;
}
cmp_times++;
}
if(d!=i){
temp=k[d] ;
k[d]=k[i];
k[i]=temp;
}
}
}
void bubbleSort(int k[],int n)
{
int i,j,flag=1;
int temp;
for(i=n-1; i>0 && flag==1; i--){
flag=0;
for(j=0;j<i;j++){
if(k[j]>k[j+1]){
temp=k[j];
k[j]=k[j+1];
k[j+1]=temp;
flag=1;
}
cmp_times++;
}
}
}
void adjust(int arr[],int low,int high)
{
int i,j,temp;
i=low;
temp=arr[i];
j=2*i+1;
while(j<high){
if(j<high-1&&arr[j]<arr[j+1]){
j++;
}
cmp_times++;
if(temp>=arr[j]){
break;
}
arr[(j-1)/2]=arr[j];
j=2*j+1;
}
arr[(j-1)/2]=temp;
}
void heapSort(int arr[],int n)
{
int i;
int temp;
for(i=n/2-1;i>=0;--i)
adjust(arr,i,n);
for(i=n-1;i>=1;--i){
temp=arr[i];
arr[i]=arr[0];
arr[0]=temp;
adjust(arr,0,i);
}
}
void Merge(int a[],int s,int m,int e,int b[])
{
int pb=s,i,t;
int p1=s,p2=m+1;
while(p1 <= m && p2 <= e){
cmp_times++;
if(a[p1]>a[p2]){
b[pb]=a[p2];
pb++;
p2++;
}
else{
b[pb]=a[p1];
pb++;
p1++;
}
}
while(p1 <= m){
b[pb]=a[p1];
pb++;
p1++;
}
while(p2 <= e){
b[pb]=a[p2];
pb++;
p2++;
}
for(t=s;t<=e;t++)
a[t] = b[t];
}
void MergeSort(int a[],int s,int e,int b[])
{
if(s<e){
int m=s+(e-s)/2;
MergeSort(a,s,m,b);
MergeSort(a,m+1,e,b);
Merge(a,s,m,e,b);
}
}
void quickSort(int v[],int left,int right)
{
int i,last;
if(left>=right)
return;
last=left;
for(i=left+1;i<=right;i++){
cmp_times++;
if(v[i]<v[left])
swap(v,++last,i);
}
swap(v,left,last);
quickSort(v,left,last-1);
quickSort(v,last+1,right);
}
void swap(int v[],int i,int j)
{
int tmp;
tmp=v[i];
v[i]=v[j];
v[j]=tmp;
}
printf("\n%d\n",cmp_times);
return 0;
}
void selectSort(int k[],int n)
{
int i,j,d;
int temp;
for(i=0;i<n-1;i++){
d=i;
for(j=i+1;j<n;j++){
if(k[j]<k[d]){
d=j;
}
cmp_times++;
}
if(d!=i){
temp=k[d] ;
k[d]=k[i];
k[i]=temp;
}
}
}
void bubbleSort(int k[],int n)
{
int i,j,flag=1;
int temp;
for(i=n-1; i>0 && flag==1; i--){
flag=0;
for(j=0;j<i;j++){
if(k[j]>k[j+1]){
temp=k[j];
k[j]=k[j+1];
k[j+1]=temp;
flag=1;
}
cmp_times++;
}
}
}
void adjust(int arr[],int low,int high)
{
int i,j,temp;
i=low;
temp=arr[i];
j=2*i+1;
while(j<high){
if(j<high-1&&arr[j]<arr[j+1]){
j++;
}
cmp_times++;
if(temp>=arr[j]){
break;
注意：因为原文代码有点小bug,所以本篇文章对原文略作改动，下面附上转载声明。
————————————————
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/weixin_45568867/article/details/117573423