[已解决]快速排序（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

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

#include <iostream>
#define n 5
using namespace std;

//快排函数
void quicksort(int * a ,  int left, int right); 

int main(void)
{
        int a[n] = 0;
        for(int i=0; i<n; i++)
        {//输入数据
                cin >> a[i];
        }

        int left = 0;
        int right = n-1;
        //递归排序
        quicksort(a, left, right);

        for(int j=0; j<n; j++)
        {//输出结果
                cout << a[j] <<" ";
        }
        cout << endl;

        return 0;
}

void quicksort(int * a ,  int left, int right)
{
        int temp = a[left]; //基准数据//将左边第一个作为基准数据
        int i = left;
        int j = right;

        if(left > right)
                return ;
        while(i != j)
        {//一直进行直到ij相遇
                while(a[j] >= temp && i < j)
                {//从最右边开始比较//必须的//如果大于基准数据，那么j--，否则，开始左边的比较
                        j--;
                }
                while(a[i] <= temp && i < j)
                {//如果小于基准数据，i++, 否则交换a[i], a[j]
                        i++;
                }

                if(i < j)
                {//交换
                        int t = 0;
                        t = a[i];
                        a[i] = a[j];
                        a[j] = t;
                }
                
        }

        //当i和j相遇时候，将基准数据和相遇点的数据交换
        a[left] = a[i];
        a[i] = temp;

        //递归排列相遇点左边和右边的数据
        quicksort(a, left, i-1);
        quicksort(a, i+1, right);
}

跳转到最佳答案楼层

tailor_long

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

#include <iostream>
#define n 5
using namespace std;

//快排函数
void quicksort(int * a ,  int left, int right); 

int main(void)
{
        int a[n] = 0;
        for(int i=0; i<n; i++)
        {//输入数据
                cin >> a[i];
        }

        int left = 0;
        int right = n-1;
        //递归排序
        quicksort(a, left, right);

        for(int j=0; j<n; j++)
        {//输出结果
                cout << a[j] <<" ";
        }
        cout << endl;

        return 0;
}

void quicksort(int * a ,  int left, int right)
{
        int temp = a[left]; //基准数据//将左边第一个作为基准数据
        int i = left;
        int j = right;

        if(left > right)
                return ;
        while(i != j)
        {//一直进行直到ij相遇
                while(a[j] >= temp && i < j)
                {//从最右边开始比较//必须的//如果大于基准数据，那么j--，否则，开始左边的比较
                        j--;
                }
                while(a[i] <= temp && i < j)
                {//如果小于基准数据，i++, 否则交换a[i], a[j]
                        i++;
                }

                if(i < j)
                {//交换
                        int t = 0;
                        t = a[i];
                        a[i] = a[j];
                        a[j] = t;
                }
                
        }

        //当i和j相遇时候，将基准数据和相遇点的数据交换
        a[left] = a[i];
        a[i] = temp;

        //递归排列相遇点左边和右边的数据
        quicksort(a, left, i-1);
        quicksort(a, i+1, right);
}

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
就是这个东西

原来如此，再次感谢