[已解决]快速排序（Quick Sort),递归方法，请帮忙找下错，非常感谢

Hermione

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define MAX 5
using namespace std;

void QuickSort (int v[], int start, int end)
{
    if (start >= end)
        return ;
    int pivot = v[start];
    int i = start + 1, j = end;
    while(i < j)
    {
        while(v[j] > pivot && i < j)
            j--;
        while(v[i] < pivot && j > i)
            i++;

        swap(v[i], v[j]);
        cout << "j = " << j<< endl;
    }
    for (int k = 0; k < MAX; k++)
        cout << v[k] << ' ';
    cout << endl;
    if (v[start] >= v[j])                                第26行
    swap(v[j], v[start]);
    if (j)
    QuickSort(v, 0, j - 1);
    if (j < end)
    QuickSort(v, j + 1, end);
}

int main()
{
    int v[MAX] = {0};

    for (int i = 0; i < MAX; i++)
        cin >> v[i];
    QuickSort(v, 0, MAX - 1);
    for (int i = 0; i < MAX; i++)
        cout << v[i] << ' ';
    return 0;
}
问题集合：
1.错误？
情况是：我把MAX 改成3， 输入1 12 2，结果没有改动，还是输出1 12 2
2.当i = j时，如何确定这个数要不要和pivot交换，我26行那个位置，原来是没有那句话的，可是输入1 12 2，就会输出12 1 2
3.会不会出现中间有两个数都等于pivot,结果第一个while陷入死循环的情况？如果出现，又该如何解决？
谢谢大家的帮助，新手（大一学生）

最佳答案

月排行榜 / 总排行榜

tailor_long

2017-12-4 20:55:12

楼主，你的代码，在下实在看不懂！！！
所以在下重新写了一个，

1. #include <iostream>
   
2. #define n 5
   
3. using namespace std;
   
4. 
   
5. //快排函数
   
6. void quicksort(int * a ,  int left, int right);
   
7. 
   
8. int main(void)
   
9. {
   
10.         int a[n] = 0;
    
11.         for(int i=0; i<n; i++)
    
12.         {//输入数据
    
13.                 cin >> a[i];
    
14.         }
    
15. 
    
16.         int left = 0;
    
17.         int right = n-1;
    
18.         //递归排序
    
19.         quicksort(a, left, right);
    
20. 
    
21.         for(int j=0; j<n; j++)
    
22.         {//输出结果
    
23.                 cout << a[j] <<" ";
    
24.         }
    
25.         cout << endl;
    
26. 
    
27.         return 0;
    
28. }
    
29. 
    
30. void quicksort(int * a ,  int left, int right)
    
31. {
    
32.         int temp = a[left]; //基准数据//将左边第一个作为基准数据
    
33.         int i = left;
    
34.         int j = right;
    
35. 
    
36.         if(left > right)
    
37.                 return ;
    
38.         while(i != j)
    
39.         {//一直进行直到ij相遇
    
40.                 while(a[j] >= temp && i < j)
    
41.                 {//从最右边开始比较//必须的//如果大于基准数据，那么j--，否则，开始左边的比较
    
42.                         j--;
    
43.                 }
    
44.                 while(a[i] <= temp && i < j)
    
45.                 {//如果小于基准数据，i++, 否则交换a[i], a[j]
    
46.                         i++;
    
47.                 }
    
48. 
    
49.                 if(i < j)
    
50.                 {//交换
    
51.                         int t = 0;
    
52.                         t = a[i];
    
53.                         a[i] = a[j];
    
54.                         a[j] = t;
    
55.                 }
    
56.                
    
57.         }
    
58. 
    
59.         //当i和j相遇时候，将基准数据和相遇点的数据交换
    
60.         a[left] = a[i];
    
61.         a[i] = temp;
    
62. 
    
63.         //递归排列相遇点左边和右边的数据
    
64.         quicksort(a, left, i-1);
    
65.         quicksort(a, i+1, right);
    
66. }

复制代码

跳转到最佳答案楼层

tailor_long

楼主，你的代码，在下实在看不懂！！！
所以在下重新写了一个，

1. #include <iostream>
   
2. #define n 5
   
3. using namespace std;
   
4. 
   
5. //快排函数
   
6. void quicksort(int * a ,  int left, int right);
   
7. 
   
8. int main(void)
   
9. {
   
10.         int a[n] = 0;
    
11.         for(int i=0; i<n; i++)
    
12.         {//输入数据
    
13.                 cin >> a[i];
    
14.         }
    
15. 
    
16.         int left = 0;
    
17.         int right = n-1;
    
18.         //递归排序
    
19.         quicksort(a, left, right);
    
20. 
    
21.         for(int j=0; j<n; j++)
    
22.         {//输出结果
    
23.                 cout << a[j] <<" ";
    
24.         }
    
25.         cout << endl;
    
26. 
    
27.         return 0;
    
28. }
    
29. 
    
30. void quicksort(int * a ,  int left, int right)
    
31. {
    
32.         int temp = a[left]; //基准数据//将左边第一个作为基准数据
    
33.         int i = left;
    
34.         int j = right;
    
35. 
    
36.         if(left > right)
    
37.                 return ;
    
38.         while(i != j)
    
39.         {//一直进行直到ij相遇
    
40.                 while(a[j] >= temp && i < j)
    
41.                 {//从最右边开始比较//必须的//如果大于基准数据，那么j--，否则，开始左边的比较
    
42.                         j--;
    
43.                 }
    
44.                 while(a[i] <= temp && i < j)
    
45.                 {//如果小于基准数据，i++, 否则交换a[i], a[j]
    
46.                         i++;
    
47.                 }
    
48. 
    
49.                 if(i < j)
    
50.                 {//交换
    
51.                         int t = 0;
    
52.                         t = a[i];
    
53.                         a[i] = a[j];
    
54.                         a[j] = t;
    
55.                 }
    
56.                
    
57.         }
    
58. 
    
59.         //当i和j相遇时候，将基准数据和相遇点的数据交换
    
60.         a[left] = a[i];
    
61.         a[i] = temp;
    
62. 
    
63.         //递归排列相遇点左边和右边的数据
    
64.         quicksort(a, left, i-1);
    
65.         quicksort(a, i+1, right);
    
66. }

复制代码

Hermione

tailor_long 发表于 2017-12-4 20:55
楼主，你的代码，在下实在看不懂！！！
所以在下重新写了一个，

哈哈，谢谢，容我看会儿

Hermione

Hermione 发表于 2017-12-4 22:06
哈哈，谢谢，容我看会儿

真的可以了，但是让我再思考下我另外两个问题

tailor_long

Hermione 发表于 2017-12-4 22:16
真的可以了，但是让我再思考下我另外两个问题

楼主大人，针对您的第二个问题，我的想法是这样的：
      快排的基本原则是：每次选取最左边的为基准数据，然后将其余的数据，小于基准数据的放在基准数据的左边，大于基准数据的放在基准数据右边，所以我们每一轮排序完成之后，也就是当i==j的时候，我们必须要把基准数据和 i == j 位置处的数据交换，这也解释了为什么我们判断的时候先从这堆数据的最右边开始判断！
对于您的第三个问题，在下的想法是这样的：
      当中间出现两个数都等于pivot的时候，因为你里面的while的循环条件并不是“ >= ”,而是大于号或者小于号，所以当出现两个数都等于pivot的时候，程序并不会出现死循环，j和i还是会继续分别向左向右移动

Hermione

tailor_long 发表于 2017-12-4 23:43
楼主大人，针对您的第二个问题，我的想法是这样的：
      快排的基本原则是：每次选取最左边的为基准数 ...

对第三个问题，我发现，像我那样写，的确是死循环了，这是我的bug，应当像你那样写>=,<=才对，谢谢。

tailor_long

Hermione 发表于 2017-12-5 10:03
对第三个问题，我发现，像我那样写，的确是死循环了，这是我的bug，应当像你那样写>=,

不客气啦

Hermione

tailor_long 发表于 2017-12-4 23:43
楼主大人，针对您的第二个问题，我的想法是这样的：
      快排的基本原则是：每次选取最左边的为基准数 ...

但是对第二个问题，我也明白了，因为在进入最后一次循环，说明j > i是成立的，则里面的第一个的while会结束，有两种情况，j = i，这样，由于前一次交换，必定是小于pivot的，另一种情况，v[j] <= pivot,也说明应该交换的。
谢谢，这下，我再审视下我的代码，我看完了，如果没新问题了，就采纳，非常感谢您的耐心帮助

tailor_long

Hermione 发表于 2017-12-5 10:07
但是对第二个问题，我也明白了，因为在进入最后一次循环，说明j > i是成立的，则里面的第一个的while会结 ...

哇！为楼主大人的认真细致点赞

Hermione

tailor_long 发表于 2017-12-4 23:43
楼主大人，针对您的第二个问题，我的想法是这样的：
      快排的基本原则是：每次选取最左边的为基准数 ...

我还有最后一个问题，就是为何您的代码第16行，将left设为0，而不是设为1，设为1原理上有什么硬伤？我试过了，设为1，根本排序就是错的，但是从道理上我没看出问题。谢谢。

tailor_long

Hermione 发表于 2017-12-5 10:17
我还有最后一个问题，就是为何您的代码第16行，将left设为0，而不是设为1，设为1原理上有什么硬伤？我试 ...

楼主大人，您好：
因为对于要排序的数组，下标自然是从零开始的，这也解释了为什么我的第17行将right设为n-1；
而且我将left=0；就是为了从最左边的数开始进行排序；
如果将left = 1;那么下面的程序就一塌糊涂了，因为当left=1的时候，我的基准数字temp就不再是最左边的了，而是第二个数字。
当然，如果楼主是处女座，非要将16行设置为left=1; 也是可以的，只不过你要在输入数据的时候，需要改一下输入的代码
for(int i=0; i<n; i++)
{//输入数据
cin >> a[i];
}（这代码写在这有问题，a后面还有一中括号，里面有个i）
顺便还要改一下a数组的大小
不知楼主大人能不能明白小的所说的

Hermione

tailor_long 发表于 2017-12-5 10:29
楼主大人，您好：
因为对于要排序的数组，下标自然是从零开始的，这也解释了为什么我的第17行将right ...

这下我明白了，(其实我不用发，但是为了加深印象我就发下）：
如果将left设为，那么相遇的地点至少都会是1，这样如果第一个数最小就一定是错的，我输出了中间输出结果，果然是这样。
这样我终于解决了多日的问题（没错，多日，昨天我才想起可以在论坛上问），非常感谢您

tailor_long

Hermione 发表于 2017-12-5 10:54
这下我明白了，(其实我不用发，但是为了加深印象我就发下）：
如果将left设为，那么相遇的地点至少都会 ...

Hermione

tailor_long 发表于 2017-12-5 10:56

哈哈，再问您个与主题无关的问题，您是怎么把代码能够发得那么清晰的（就是弄得可以显示行数什么的）

tailor_long

就是这个东西

Hermione

tailor_long 发表于 2017-12-5 11:13
就是这个东西

原来如此，再次感谢