请教－关于快排

chenchanjob

我自己复习基础算法的时候写了个快速排序的代码，但总是进入死循环，帮我看看怎么回事吧，谢谢！
我的代码：
void q_sort(int *arr, int low, int high){
        int i;
        while(low < high){
                i = partion(arr, low, high);
                q_sort(arr, low, i - 1);
                q_sort(arr, i + 1, high);
        }
}
int partion(int *arr, int low, int high){
        printf("low and high are %d, %d\n", low, high);
        int temp = arr[low];
        while(low < high){
                while(low < high && arr[high] >= temp)
                        high--;
                arr[low] = arr[high];
                while(low < high && arr[low] <= temp)
                        low++;
                arr[high] = arr[low];
        }
        arr[low] = temp;
        printf("mid is %d\n", low);
        return low;
}
以下是我用gdb查错的一个地方，很诡异（gdb用得少，不知道怎么会这样），明明low 和high 相等，但还是进入了while，我想程序的bug就在这里吧，但不知道如何修改程序。
(gdb) s
q_sort (arr=0xbf808be0, low=4, high=4) at sort.c:116
116          while(low < high){
(gdb) s
117                  i = partion(arr, low, high);
请牛人解说一下，谢谢！

chenchanjob

是我的问题太弱智了吗 。。。

bladmin

你这代码写的真是有点郁闷人！上面第一个函数中的low 和 high 值一直没有变化！吼吼！

[ 本帖最后由 bladmin 于 2009-4-9 09:49 编辑 ]

bladmin

原帖由 chenchanjob 于 2009-4-8 15:55 发表
我自己复习基础算法的时候写了个快速排序的代码，但总是进入死循环，帮我看看怎么回事吧，谢谢！
我的代码：
void q_sort(int *arr, int low, int high){
        int i;
        while(low < high){
     ...

我大概修改了下你的代码，这样应该可以了，你看看！
#include<stdio.h>
void q_sort(int *arr, int low, int high){
                int i;
                i = partion(arr, low, high);
                printf("%d\n",i);
                if(low <i-1){
                        q_sort(arr, low, i - 1);
                }
                if(high>i+1){
                        q_sort(arr, i + 1, high);
                }
}
int partion(int *arr, int low, int high){
        printf("low and high are %d, %d\n", low, high);
        int temp = arr[low];
        while(low < high){
                while(low < high && arr[high] >= temp){
                        high--;
                }
                arr[low] = arr[high];
                while(low < high && arr[low] <= temp){
                        low++;
                }
                arr[high] = arr[low];
        }
        arr[low] = temp;
        printf("mid is %d\n", low);
        return low;
}
int main(){
        int index =0;
        int arr[] = {49,38,65,97,76,13,27};
        q_sort(arr,0,6);
        for(index=0;index<7;i++){
                printf("%d",  arr[index]);   
                printf("\n");
        }
}

[ 本帖最后由 bladmin 于 2009-4-9 10:01 编辑 ]

langue

template <class T>
inline void my_swap(T &x, T &y)
{
    T z;
    z = y;
    y = x;
    x = z;
}

或者：

#include <algorithm>

swap(x, y);

或者：

typedef int Element;
#define swap_(a, b) { Element tmp = b; b = a; a = tmp; }

皇家救星

快排的时候确实是这样就行了，不用中间交换

皇家救星

void q_sort(int *arr, int low, int high){
        int i;
        while(low < high){
                i = partion(arr, low, high);
                q_sort(arr, low, i - 1);
                q_sort(arr, i + 1, high);
        }
}

这里不应该是while(low < high) 应该是if

皇家救星

(gdb) s
q_sort (arr=0xbf808be0, low=4, high=4) at sort.c:116
116          while(low < high){
(gdb) s
117                  i = partion(arr, low, high);


这是递归产生的，你试着在这里打印low和high就知道，是这；视觉误差

皇家救星

把while换成if就ok了

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int partion(int *arr, int low, int high){
   
5.         printf("low and high are %d, %d\n", low, high);
   
6.         int temp = arr[low];
   
7.         while(low < high){
   
8.                 while(low < high && arr[high] >= temp)
   
9.                         high--;
   
10.                 arr[low] = arr[high];
    
11.                 while(low < high && arr[low] <= temp)
    
12.                         low++;
    
13.                 arr[high] = arr[low];
    
14.         }
    
15.         arr[low] = temp;
    
16.         printf("mid is %d\n", low);
    
17.         return low;
    
18. }
    
19. 
    
20. void q_sort(int *arr, int low, int high){
    
21.         int i;
    
22.         if(low < high){
    
23.                 i = partion(arr, low, high);
    
24.                 q_sort(arr, low, i - 1);
    
25.                 q_sort(arr, i + 1, high);
    
26.         }
    
27. }
    
28. 
    
29. 
    
30. int main()
    
31. {
    
32.         int array[] = {1,2,3,8,9,6,7};
    
33.         q_sort(array, 0, sizeof(array) / sizeof(array[0]) - 1);
    
34.         for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
    
35.         {
    
36.                 printf("%d ", array[i]);
    
37.         }
    
38.         return 0;
    
39. }
    

复制代码

bladmin

原帖由 皇家救星 于 2009-4-9 09:20 发表
快排的时候确实是这样就行了，不用中间交换

呵呵，看错了，是不用！晚上有点困！

只是在一次交换后把temp放进去就好了！哈哈，不好意思！