快速排序确实比冒泡快很多

``````#include <stdio.h>
int limit,num;

void swap(int* a,int* b){
int temp = *a;
*a = *b;
*b = temp;
}

//三数中值分割法
void middle(int* a,int left,int right){
int mid = (left+right)/2;
if(a[mid]>a[right])
swap(&a[mid],&a[right]);
if(a[mid]>a[left])
swap(&a[mid],&a[left]);
if(a[left]>a[right])
swap(&a[right],&a[left]);
}

//快速排序比冒泡排序要快
void quick(int* a, int left, int right){
if(left >= right){
return ;
}
int i = left;
int j = right;
middle(a,left,right);
int key = a[left];
while(i < j){
while(i < j && key <= a[j]){
j--;
}
swap(&a[i],&a[j]);
while(i < j && key >= a[i]){
i++;
}
swap(&a[i],&a[j]);
}
a[i] = key;
quick(a, left, i - 1);
quick(a, i + 1, right);
}

int group(int* objs,int limit,int num){
int beg = 0,
tail = num-1,
number = 0;
for(;tail>beg;tail--){
if(objs[tail]+objs[beg]<=limit)
beg++;
number++;
}
if(tail==beg&&objs[beg]<=limit)
return number+1;
else
return number;
}

int main()
{
scanf("%d",&limit);
scanf("%d",&num);
int order[num];
for(int i=0;i<num;i++)
scanf("%d",&order[i]);
quick(order,0,num-1);
int number = group(order,limit,num);
printf("%d",number);
return 0;
}

``````

2 条评论

• @ 2017-08-09 16:14:41

这是必然的。。。

• @ 2017-08-09 00:09:39

建议发表在题解区…

• 1

ID
1409

4

6800

2644

39%