给出一组实验来比较快速排序与冒泡算法的时间性能 急求代码模版~ 谢谢~~~

发布网友 发布时间：2022-04-22 16:45

我来回答

共4个回答

热心网友 时间：2022-04-22 18:14

/*快速排序*/
#include<iostream>
using namespace std;
int a[10001];
void qs(int s,int e)
{
int x=a[s],l=s,r=e;//以第一个数为参照做比较
if(l>=r)
return;
while(l<r)
{
while(l<r&&a[r]>=x)
r--; //不小于分界值的留在右边，遇到小于的停止
a[l]=a[r];
while(l<r&&a[l]<=x)
l++; //小于分界值的留在左边，遇到不小于的停止
a[r]=a[l];
}
a[r]=x;
qs(s,r-1);
qs(r+1,e);//递归
}
int main()
{
int i,n;
cin>>n;
//输入要排序的数组元素个数即 数组长度
for(i=0;i<n;i++)
cin>>a[i];//输入数组元素
qs(0,n-1);//执行排序函数
for(i=0;i<n;i++)//输出排序后结果
cout<<a[i];
system("pause");
}

/*冒泡排序*/
#include <stdio.h>
#include <stdlib.h>

void bubble_sort(int array[], int size)
{
int temp, i, j;

for (i = 0; i < size; i++)
for (j = 0; j < size; j++)
if (array[i] < array[j])
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}

void main(void)
{
int values[30], i;

for (i = 0; i < 30; i++)
{
if (i % 5 == 0)
printf("\n");
values[i] = rand() % 100;
printf("%2d ",values[i]);
}
printf("\n\n");

bubble_sort(values, 30);

for (i = 0; i < 30; i++)
{
if (i % 5 == 0)
printf("\n");
printf("%2d ", values[i]);
}
getchar();
}

热心网友 时间：2022-04-22 19:32

数据简单啊

int p[100000];
int n;
int arrSize;
long long t1=0,t2=0;
n = 10000;
arrSize = 10+ rand()%9991;

while (n-->0)
{
for(int i=0;i<arrSize;i++) p[i] = rand();
t1 += calTime( qsort,p,arrSize);
t2 += calTime( bubble,p,arrSize);
}
自己写calTime函数

热心网友 时间：2022-04-22 21:07

必须给模板参数，int型，再次两个模板参数的>>中间必须加空格。

热心网友 时间：2022-04-22 22:58

快速排序时间复杂度为O(N),
冒泡排序理想状态下时间复杂度O(N)，最坏情况O(n*n)。一般平均为nlogn