标题:关于快排的一个bug
只看楼主
mscool
Rank: 1
等 级:新手上路
帖 子:53
专家分:0
注 册:2013-5-9
结帖率:92.31%
已结贴  问题点数:20 回复次数:8 
关于快排的一个bug
#include <stdio.h>

int a[8] = {3,5,0,8,2,4,9,3};

int partition(int start, int end)
{
    int len = end - start, j, mid;
    int pivot = a[start];
    int temp[len];

    for (j = start + 1; j <= end; j++)
        temp[j] = a[j];

    for (j = start + 1; j <= end; j++)
    {
        if (temp[j] < pivot)
        a[start++] = temp[j];
        else
        a[end--] = temp[j];
    }

    a[start] = pivot;

    return mid = start;
}

void quicksort(int start, int end)
{
    int mid;

    if (end > start)
    {
        mid = partition(start, end);
        quicksort(start,mid - 1);
        quicksort(mid + 1, end);
    }
}

int main(void)
{
    int i;

    quicksort(0,7);

    for (i =0; i <= 7; i++)
        printf("%d\n", a[i]);

    return 0;
}


程序出错 实在找不出来bug 哪位帮我查一下错在哪里?谢
搜索更多相关主题的帖子: include return start 
2013-08-23 07:15
yuccn
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:何方
等 级:版主
威 望:167
帖 子:6809
专家分:42393
注 册:2010-12-16
得分:5 
不说下具体什么情况?

我行我乐
我的博客:
http://blog.yuccn. net
2013-08-23 08:10
love云彩
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:青藏高原
等 级:贵宾
威 望:53
帖 子:3663
专家分:11416
注 册:2012-11-17
得分:5 
请参考本版置顶的帖子,220个代码分享,再看看与你的不同之处

思考赐予新生,时间在于定义
2013-08-23 08:40
就少个空格啊
Rank: 2
来 自:吉林省
等 级:论坛游民
帖 子:21
专家分:34
注 册:2013-7-9
得分:5 
len = end - start; int temp[len];  这里的两句,那要排序的a[]来说,temp[]的长度是7,及temp[0]-temp[6];
而for (j = start + 1; j <= end; j++)
        temp[j] = a[j];
你把a[1]-a[7]分别赋值给了temp[1]-temp[6],也就是丢了一个数据a[7],多了一个数据temp[0]=0.
我就看到这里,

不断的让自己变得更加强大!
2013-08-23 12:34
guhemeng
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:100
专家分:165
注 册:2013-7-27
得分:5 
刚好在看算法:  彼此参考下!
int find_middle(int array[],int low,int high)
{
    int tmp = array[low];
    while(1)
    {
        while( (low < high)&&(tmp <= array[high]) )
            high--;
            if(low == high) break;
            array[low++] = array[high];

        while( (low < high)&&(array[low] <= tmp) )
            low++;
            if(low == high) break;
            array[high--] = array[low];
    }
    array[high] = tmp;
    return low; //return high;
        
}
void quick_sort(int array[], int low,int high)
{
    int middle;
    if (low >= high) return;
    middle = find_middle(array, low, high);
    quick_sort(array,low,middle - 1);
    quick_sort(array, middle + 1, high);
}
2013-08-23 13:08
guhemeng
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:100
专家分:165
注 册:2013-7-27
得分:0 
快排的思想是:  首先取首值array[low],然后把整个数组中比首值大的从最后往前放(array[high];high--;),比首值小的从最前往后放(array[low];low++;). 当low == high 时,结束当次循环,返回low或high(两者是相等的);

你函数中下面这个循环干啥子?  增加函数复杂度?
for (j = start + 1; j <= end; j++)
        temp[j] = a[j];
2013-08-23 13:21
mscool
Rank: 1
等 级:新手上路
帖 子:53
专家分:0
注 册:2013-5-9
得分:0 
回复 6楼 guhemeng
这个是保存原始数值啊 因为要改变a[]  所以先把其原始数据保存到temp[]中 不然 容易丢失 或者篡改原始数据 就不准确了
2013-08-23 14:28
mscool
Rank: 1
等 级:新手上路
帖 子:53
专家分:0
注 册:2013-5-9
得分:0 
回复 4楼 就少个空格啊
谢 我仍是对细节太马虎了
2013-08-23 14:32
mscool
Rank: 1
等 级:新手上路
帖 子:53
专家分:0
注 册:2013-5-9
得分:0 
回复 6楼 guhemeng
如果不像我那样做 你要怎么实现你的这个想法
2013-08-23 14:33



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-419543-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018576 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved