回 帖 发 新 帖 刷新版面

主题:[讨论]看看这个快速排序算法错在哪里?

该排序算法有时会出错,我测试时用的随机产生数组,有时会出错
用的是Dev-C++
[code=c]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10
void kuaisu(int *a,int n);
void quick(int *a,int left,int right);
int main()
{
    int arr[N],i;
    srand(time(NULL));
    for(i=0;i<N;i++)
    {
         arr[i]=rand()/1000+100;
    }
    kuaisu(arr,N);
    for(i=0;i<N;i++)
    {
        printf("%d ",arr[i]);
    }
    getch();
    return 0;
}
void kuaisu(int *a,int n)   //快速排序
{
    quick(a,0,n-1);
}

void quick(int *a,int left,int right)
{
    int f,l,r,t;
    l=left;
    r=right;
    f=a[(left+right)/2];
    while(l<r)
    {
        while(a[l]<f) ++l;
        while(a[r]>f) --r;
        if(l<=r)
        {
            t=a[l];
            a[l]=a[r];
            a[r]=t;
            ++l;
            --r;
        }
    }
    if(l==r)
    {
        l++;
    }
    if(left<r) 
    {
        quick(a,left,l-1);
    }
    if(l<right) 
    {
        quick(a,r+1,right);
    }
}

[/code]

回复列表 (共4个回复)

沙发

我也遇到同样的错误,下面的这个算法有时间也会出错,请大侠顺便也点点!
[code=c]
template<class T>
void dataList<T>::QuickSort(const int left,const int right)
{
    int i,j;
    i=left;
    j=right;
    Element<T> pivot=Vector[left];
    while(i<j)
    {
        while(i<j&&pivot<=Vector[j])
            j--;
        if(i<j)
            Vector[i++]=Vector[j];
        while(i<j&&pivot>Vector[i])
            i++;
        if(i<j)
            Vector[j--]=Vector[i];
    }
    Vector[i]=pivot;
    if(i-left>1)
        QuickSort(left,i-1);
    if(right-j>1)
        QuickSort(j+1,right);
}
[/code]

板凳

没法调试,vc下没有遇到错误

3 楼

while(l<r)
    {
        while(a[l]<f) ++l;
        while(a[r]>f) --r;
        if(l<=r)
        {
            t=a[l];
            a[l]=a[r];
            a[r]=t;
            ++l;
            --r;
        }
    }
你看看101,102,103,104,105,106,103,107,108,101这些数调用上面的代码会排列成什么样,是不是你要想要的结果

4 楼

这组数很有代表性,但修改程序能够排列这组数后,随机测试其他数组还是会出问题,出现了死循环

我来回复

您尚未登录,请登录后再回复。点此登录或注册