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

#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
分类
贪心 点击显示
标签
递交数
6636
已通过
2581
通过率
39%
上传者