下面这段代码怎么修改可以统计比较的次数和交换的次数?
void quickSort(int a[],int left,int right)
{
int i,j,temp;
i=left;
j=right;
temp=a[left];
if(i>=j)return;
while(i!=j)
{
while(a[j]>=temp && j>i)
{j=j-1;}
if(j>i)
{a[i]=a[j];i=i+1;}
while(a[i]<=temp && j>i)
{i=i+1;}
if(j>i)
{a[j]=a[i];j=j-1;}
}
a[i]=temp;
quickSort(a,left,i-1);
quickSort(a,i+1,right);
}
快速排序统计比较的次数
答案:2 悬赏:30 手机版
解决时间 2021-02-18 03:36
- 提问者网友:美人性情
- 2021-02-17 17:57
最佳答案
- 五星知识达人网友:duile
- 2021-02-17 18:45
加一个全局变量来统计
全部回答
- 1楼网友:一袍清酒付
- 2021-02-17 19:26
要统计交换次数,最简单的思考就是每次交换的时候都+1,所以找到交换函数也就找到了计数点,该程序中swap()函数就是交换函数,跟踪该函数,每次调用都计数+1,就统计到了交换次数。
#include "iostream.h"
void swap(int *a,int low,int high);
void quicksort(int *a,int start,int end);
void output(int *a,int low,int high);
//定义一个保存交换次数的全局变量
static int count=0;
void swap(int *a,int low,int high)
{
int temp=a[low];
a[low]=a[high];
a[high]=temp;
}
void quicksort(int *a,int start,int end)
{
int balance=(a[start]+a[end])/2;
int low=start;
int high=end;
while(low<high)
{
while(a[high]>=balance) high--;
while(a[low]<=balance) low++;
if(low<high)
{
//每交换一次,计数一次
swap(a,low,high);
count++;
}
if(high==start-1)
{
if(a[start]>a[end])
{
//同理,每交换一次,计数一次
swap(a,start,end);
count++;
}
high=start;
low=start+1;
}
}
int t=low;
low=high;
high=t;
if(low>=start+1)
quicksort(a,start,low);
if(high<=end-1)
quicksort(a,high,end);
}
void output(int *a,int low,int high)
{
for(int i=low;i<=high;i++)
cout<<a[i]<<" ";
cout<<endl;
}
void main()
{
int arr[15]={
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯