快速排序（Quick Sort),递归方法，请帮忙找下错，非常感谢
#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;
int i = start + 1, j = end;
while(i < j)
{
while(v > pivot && i < j)
j--;
while(v < pivot && j > i)
i++;
swap(v, v);
cout << "j = " << j<< endl;
}
for (int k = 0; k < MAX; k++)
cout << v << ' ';
cout << endl;
if (v >= v) 第26行
swap(v, v);
if (j)
QuickSort(v, 0, j - 1);
if (j < end)
QuickSort(v, j + 1, end);
}
int main()
{
int v = {0};
for (int i = 0; i < MAX; i++)
cin >> v;
QuickSort(v, 0, MAX - 1);
for (int i = 0; i < MAX; i++)
cout << v << ' ';
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陷入死循环的情况？如果出现，又该如何解决？
谢谢大家的帮助，新手（大一学生） 楼主，你的代码，在下实在看不懂！！！
所以在下重新写了一个，
#include <iostream>
#define n 5
using namespace std;
//快排函数
void quicksort(int * a ,int left, int right);
int main(void)
{
int a = 0;
for(int i=0; i<n; i++)
{//输入数据
cin >> a;
}
int left = 0;
int right = n-1;
//递归排序
quicksort(a, left, right);
for(int j=0; j<n; j++)
{//输出结果
cout << a <<" ";
}
cout << endl;
return 0;
}
void quicksort(int * a ,int left, int right)
{
int temp = a; //基准数据//将左边第一个作为基准数据
int i = left;
int j = right;
if(left > right)
return ;
while(i != j)
{//一直进行直到ij相遇
while(a >= temp && i < j)
{//从最右边开始比较//必须的//如果大于基准数据，那么j--，否则，开始左边的比较
j--;
}
while(a <= temp && i < j)
{//如果小于基准数据，i++, 否则交换a, a
i++;
}
if(i < j)
{//交换
int t = 0;
t = a;
a = a;
a = t;
}
}
//当i和j相遇时候，将基准数据和相遇点的数据交换
a = a;
a = temp;
//递归排列相遇点左边和右边的数据
quicksort(a, left, i-1);
quicksort(a, i+1, right);
}
tailor_long 发表于 2017-12-4 20:55
楼主，你的代码，在下实在看不懂！！！
所以在下重新写了一个，
哈哈，谢谢，容我看会儿 Hermione 发表于 2017-12-4 22:06
哈哈，谢谢，容我看会儿
真的可以了，但是让我再思考下我另外两个问题 Hermione 发表于 2017-12-4 22:16
真的可以了，但是让我再思考下我另外两个问题
楼主大人，针对您的第二个问题，我的想法是这样的：
快排的基本原则是：每次选取最左边的为基准数据，然后将其余的数据，小于基准数据的放在基准数据的左边，大于基准数据的放在基准数据右边，所以我们每一轮排序完成之后，也就是当i==j的时候，我们必须要把基准数据和 i == j 位置处的数据交换，这也解释了为什么我们判断的时候先从这堆数据的最右边开始判断！
对于您的第三个问题，在下的想法是这样的：
当中间出现两个数都等于pivot的时候，因为你里面的while的循环条件并不是“ >= ”,而是大于号或者小于号，所以当出现两个数都等于pivot的时候，程序并不会出现死循环，j和i还是会继续分别向左向右移动
{:5_91:} tailor_long 发表于 2017-12-4 23:43
楼主大人，针对您的第二个问题，我的想法是这样的：
快排的基本原则是：每次选取最左边的为基准数 ...
对第三个问题，我发现，像我那样写，的确是死循环了，这是我的bug，应当像你那样写>=,<=才对，谢谢。
Hermione 发表于 2017-12-5 10:03
对第三个问题，我发现，像我那样写，的确是死循环了，这是我的bug，应当像你那样写>=,
不客气啦{:10_243:} tailor_long 发表于 2017-12-4 23:43
楼主大人，针对您的第二个问题，我的想法是这样的：
快排的基本原则是：每次选取最左边的为基准数 ...
但是对第二个问题，我也明白了，因为在进入最后一次循环，说明j > i是成立的，则里面的第一个的while会结束，有两种情况，j = i，这样，由于前一次交换，必定是小于pivot的，另一种情况，v <= pivot,也说明应该交换的。
谢谢，这下，我再审视下我的代码，我看完了，如果没新问题了，就采纳，非常感谢您的耐心帮助 Hermione 发表于 2017-12-5 10:07
但是对第二个问题，我也明白了，因为在进入最后一次循环，说明j > i是成立的，则里面的第一个的while会结 ...
哇！为楼主大人的认真细致点赞
{:10_257:} tailor_long 发表于 2017-12-4 23:43
楼主大人，针对您的第二个问题，我的想法是这样的：
快排的基本原则是：每次选取最左边的为基准数 ...
我还有最后一个问题，就是为何您的代码第16行，将left设为0，而不是设为1，设为1原理上有什么硬伤？我试过了，设为1，根本排序就是错的，但是从道理上我没看出问题。谢谢。 本帖最后由 tailor_long 于 2017-12-5 10:32 编辑
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;
}（这代码写在这有问题，a后面还有一中括号，里面有个i）
顺便还要改一下a数组的大小
不知楼主大人能不能明白小的所说的{:10_269:} tailor_long 发表于 2017-12-5 10:29
楼主大人，您好：
因为对于要排序的数组，下标自然是从零开始的，这也解释了为什么我的第17行将right ...
这下我明白了，(其实我不用发，但是为了加深印象我就发下）：
如果将left设为，那么相遇的地点至少都会是1，这样如果第一个数最小就一定是错的，我输出了中间输出结果，果然是这样。
这样我终于解决了多日的问题（没错，多日，昨天我才想起可以在论坛上问），非常感谢您 Hermione 发表于 2017-12-5 10:54
这下我明白了，(其实我不用发，但是为了加深印象我就发下）：
如果将left设为，那么相遇的地点至少都会 ...
{:10_297:} tailor_long 发表于 2017-12-5 10:56
哈哈，再问您个与主题无关的问题，您是怎么把代码能够发得那么清晰的（就是弄得可以显示行数什么的） 就是这个东西
tailor_long 发表于 2017-12-5 11:13
就是这个东西
原来如此，再次感谢
页:
[1]