帮我看下 - C语言论坛

第 11 楼

得分:0

是两边往中间排不是冒泡..

第 12 楼

得分:0

还不是一样，冒泡的基本方法，从两端交替进行，复杂度不变，还是n^2…………

专心编程………
飞燕算法初级群：3996098
我的Blog

第 13 楼

得分:0

两个方法本质上不不一样的　　排列出发点不一样　这方法更先进点

第 14 楼

得分:0

Bubblet1 Use time:23569ms
Bubblet2 Use time:15259ms
HeapSort Use time:15ms
请按任意键继续. . .

这是测试的数据，1是经典冒泡，2是你改进过的冒泡，3是堆排……
程序如下：

/********************************************************
** Highlight software by yzfy(雨中飞燕) http:// *
*********************************************************/
#include <iostream>
#include <time.h>
using namespace std;

void Bubblet1(int *a,int len)
{
    for (int i=1;len--,i;)
    {
        for (int j=i=0;j<len;j++)
            if (a[j]>a[j+1])
                {int t=a[j];a[j]=a[j+1];a[j+1]=t;i=1;}
    }
}

void Bubblet2(int *a,int len)
{
    for (int i=1,j=len-1,k=0;!k;i++)
    {
        k=1;
        for (int l=i-1;l<j;l++)
            if (a[l]>a[l+1])
                {int t=a[l];a[l]=a[l+1];a[l+1]=t;k=0;}
        if (k)break;
        for (int l=--j;l>=i;l--)
            if (a[l-1]>a[l])
                {int t=a[l];a[l]=a[l-1];a[l-1]=t;k=0;}
    }
}

void AdjustHeap(int *a,int begin,int len)
{
    int child,x=a[begin];
    while(child=begin<<1|1,child<len)
    {
        if(child<len-1 && a[child]<a[child+1])child++;
        if(x<a[child]){a[begin]=a[child];begin=child;}else break;
    }
    a[begin]=x;
}

void HeapSort(int *a,int len)
{
    for(int i=len/2-1;i>=0;i--)
        AdjustHeap(a,i,len);
    while(len-->1)
    {
        int t=a[len];a[len]=a[0];a[0]=t;
        AdjustHeap(a,0,len);
    }
}

#define N 100000

int a[N];

int main()
{
    clock_t t;
    for (int i=0;i<N;i++)a[i]=rand();
    t=clock();
    Bubblet1(a,N);
    printf("Bubblet1 Use time:%ldms\n",clock()-t);

    for (int i=0;i<N;i++)a[i]=rand();
    t=clock();
    Bubblet2(a,N);
    printf("Bubblet2 Use time:%ldms\n",clock()-t);

    for (int i=0;i<N;i++)a[i]=rand();
    t=clock();
    HeapSort(a,N);
    printf("HeapSort Use time:%ldms\n",clock()-t);

}

专心编程………
飞燕算法初级群：3996098
我的Blog

第 15 楼

得分:0

不要在中间定义变量
.c不能运行的!

我秀我自己

第 16 楼

得分:0

谢了! 看过了很好我写的那程序不知道还有什么地方有误我机子上没VC 堆排的思路是什么
#include <iostream>
printf 也能用吗没试过

[[it] 本帖最后由走一圈于 2008-5-10 14:14 编辑 [/it]]

第 17 楼

得分:0

Bubblet1 Use time:23951ms
Bubblet2 Use time:17710ms
HeapSort Use time:15ms
QuickSort Use time:7ms
请按任意键继续. . .

新的一轮测试结果。加入了快排。
C99正式支持在任意位置定义变量。如果你没有C99编译器，请用C++编译器代替。
我的所有代码，请都不要用TC编译……
附上源码：

/********************************************************
** Highlight software by yzfy(雨中飞燕) http:// *
*********************************************************/
#include <iostream>
#include <time.h>
using namespace std;

void Bubblet1(int *a,int len)
{
    int i=1,j;
    while (len--,i)
    {
        for (j=i=0;j<len;j++)
            if (a[j]>a[j+1])
                {int t=a[j];a[j]=a[j+1];a[j+1]=t;i=1;}
    }
}

void Bubblet2(int *a,int len)
{
    for (int i=1,j=len-1,k=1;k;i++)
    {
        int l;k=0;
        for (l=i-1;l<j;l++)
            if (a[l]>a[l+1])
                {int t=a[l];a[l]=a[l+1];a[l+1]=t;k=1;}
        if (!k)break;
        for (l=--j;l>=i;l--)
            if (a[l-1]>a[l])
                {int t=a[l];a[l]=a[l-1];a[l-1]=t;k=1;}
    }
}

void AdjustHeap(int *a,int begin,int len)
{
    int child,x=a[begin];
    while (child=begin<<1|1,child<len)
    {
        if (child!=len-1 && a[child]<a[child+1])child++;
        if (x<a[child]){a[begin]=a[child];begin=child;}
        else break;
    }
    a[begin]=x;
}

void HeapSort(int *a,int len)
{
    for (int i=len/2-1;i>=0;i--)
        AdjustHeap(a,i,len);
    while (len-->1)
    {
        int t=a[len];a[len]=a[0];a[0]=t;
        AdjustHeap(a,0,len);
    }
}

int* Partition(int* begin,int* end)
{
    int x=*end;
    for (;begin<end;begin++)
        if (*begin > x) *end--=*begin;
    return *begin=x,begin;
}

void QuickSort(int* begin,int* end)
{
    if (begin < end)
    {
        int *p=Partition(begin,end);
        QuickSort(begin,p-1);
        QuickSort(p+1,end);
    }
}

#define N 100000

int a[N];

int main()
{
    clock_t t;
    srand((unsigned)time(NULL));

    for (int i=0;i<N;i++)a[i]=rand();
    t=clock();
    Bubblet1(a,N);
    printf("Bubblet1 Use time:%ldms\n",clock()-t);

    for (int i=0;i<N;i++)a[i]=rand();
    t=clock();
    Bubblet2(a,N);
    printf("Bubblet2 Use time:%ldms\n",clock()-t);

    for (int i=0;i<N;i++)a[i]=rand();
    t=clock();
    HeapSort(a,N);
    printf("HeapSort Use time:%ldms\n",clock()-t);

    for (int i=0;i<N;i++)a[i]=rand();
    t=clock();
    QuickSort(a,a+N-1);
    printf("QuickSort Use time:%ldms\n",clock()-t);
}

专心编程………
飞燕算法初级群：3996098
我的Blog

第 18 楼

得分:0

做大顶堆调整..然后和最后一个元素交换..这样刚好保证重小到大排列...这个应该快在交换时间比较小吧...
for(int i=len/2-1;i>=0;i--) AdjustHeap(a,i,len);
这个是做什么?建堆?

学习需要安静。。海盗要重新来过。。

第 19 楼

得分:0

LS：回答正确……

专心编程………
飞燕算法初级群：3996098
我的Blog

第 20 楼

得分:0

Bubblet1 Use time:24209ms
Bubblet2 Use time:16138ms
SelectSort Use time:9888ms
HeapSort Use time:17ms
QuickSort Use time:6ms
请按任意键继续. . .

你看，连选择排序都比你的快。等我写完了插入排序，就把代码一起发上来……

专心编程………
飞燕算法初级群：3996098
我的Blog