作者superme7 (Bonbodi)
看板C_and_CPP
标题[问题] Quicksort选mid为pivot出现问题
时间Sun Apr 18 14:57:41 2021
开发平台(Platform): Win10
编译器: GCC
额外使用到的函数库(Library Used): 无
问题(Question)：试着优化Quicksort，选mid为pivot和选end结果不同
，选end结果正确，mid却无法sort，请各位帮我看看程式哪里有错
P.S. 注解处为选end为pivot
喂入的资料(Input)：9 4 1 6 7 3 8 2 5
预期的正确结果(Expected Output)：1 2 3 4 5 6 7 8 9
错误结果(Wrong Output)： 未显示
程式码(Code):
#include <iostream>
using namespace std;
const int n = 9;
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
int Partition(int *list, int front, int end)
{
int pivot = (front + end) / 2;
int i = front - 1;
int j = end + 1;
while (i < j)
{
do
i++;
while (list[i] <= list[pivot]);
do
j--;
while (list[j] >= list[pivot]);
swap(list[i], list[j]);
}
swap(list[pivot], list[i]);
return i;
}
/*int Partition(int *list, int front, int end)
{
int i = front - 1;
for (int j = front; j < end; j++)
{
if (list[j] < list[end])
{
swap(list[++i], list[j]);
}
}
swap(list[++i], list[end]);
return i;
}*/
void Quicksort(int *list, int front, int end)
{
if (front < end)
{
int pivot = Partition(list, front, end);
Quicksort(list, front, pivot - 1);
Quicksort(list, pivot + 1, end);
}
}
void Print(int *list)
{
for (int i = 0; i < n; i++)
cout << list[i] << " ";
cout << endl;
}
int main()
{
int a[] = {9, 4, 1, 6, 7, 3, 8, 2, 5};
cout << "Unsorted: \n";
Print(a);
cout << "Sorted: \n";
Quicksort(a, 0, n - 1);
Print(a);
return 0;
}
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.136.218 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1618729063.A.8D4.html
1F：推 LPH66: 你知道 Partition 是怎麽运作的吗? 04/18 15:42
2F：→ LPH66: 我是指, 每一行做了什麽事使得最後得到什麽结果这些细节 04/18 15:42
3F：推 ucrxzero: 不是就是 枢点右边都比他大 左边都比他小 04/18 15:47
4F：→ ucrxzero: 然後递回下去 若找到越中间的枢点越好 04/18 15:48
5F：→ superme7: tace过code了用pivot = end实作过，但是不知道pivot = m 04/18 15:55
6F：→ superme7: 为甚麽跑不出来 04/18 15:56
7F：推 ucrxzero: 你是不是在写作业 04/18 15:57
8F：→ superme7: 不是，这是我上网学的 04/18 16:01
9F：推 ucrxzero: 我帮你看一夏 04/18 16:01
10F：→ superme7: 感谢U大 04/18 16:06
11F：推 ucrxzero: 找到了改一下条件 04/18 16:22
12F：→ ucrxzero: while (i<j &&list[i] <= list[pivot]); 04/18 16:22
13F：→ ucrxzero: while (i<j &&list[j] >= list[pivot]); 04/18 16:22
14F：→ ucrxzero: 但还是不对 04/18 16:25
15F：→ ucrxzero: 等等= = 04/18 16:25
16F：推 ucrxzero: www.algolist.net/Algorithms/Sorting/Quicksort 04/18 17:22
17F：推 ko27tye: 你要这样做的话 partition function内的 最外层swap不要 04/18 19:38
18F：→ ko27tye: 做 然後把i和j传出去给quickSort当pivot 04/18 19:38
19F：推 ucrxzero: 对 ko27跟我查到的是一样的方式 04/18 19:42
20F：→ superme7: 感谢各位大大 我知道原因了 04/18 22:06
21F：推 ro9956882: pivot在end可行的话 多一行swap(list[mid],list[end]) 04/24 02:42