[问题] Quicksort选mid为pivot出现问题

楼主: superme7 (superme)   2021-04-18 14:57:41
开发平台(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
作者: LPH66 (-6.2598534e+18f)   2021-04-18 15:42:00
你知道 Partition 是怎么运作的吗?我是指, 每一行做了什么事使得最后得到什么结果这些细节
作者: ucrxzero (RX-0)   2021-04-18 15:47:00
不是就是 枢点右边都比他大 左边都比他小然后递回下去 若找到越中间的枢点越好
楼主: superme7 (superme)   2021-04-18 15:55:00
tace过code了用pivot = end实作过,但是不知道pivot = m为什么跑不出来
作者: ucrxzero (RX-0)   2021-04-18 15:57:00
你是不是在写作业
楼主: superme7 (superme)   2021-04-18 16:01:00
不是,这是我上网学的
作者: ucrxzero (RX-0)   2021-04-18 16:01:00
我帮你看一夏
楼主: superme7 (superme)   2021-04-18 16:06:00
感谢U大
作者: ucrxzero (RX-0)   2021-04-18 16:22:00
找到了改一下条件while (i<j &&list[i] <= list[pivot]);while (i<j &&list[j] >= list[pivot]);但还是不对等等= =www.algolist.net/Algorithms/Sorting/Quicksort
作者: ko27tye (好滋好滋)   2021-04-18 19:38:00
你要这样做的话 partition function内的 最外层swap不要做 然后把i和j传出去给quickSort当pivot
作者: ucrxzero (RX-0)   2021-04-18 19:42:00
对 ko27跟我查到的是一样的方式
楼主: superme7 (superme)   2021-04-18 22:06:00
感谢各位大大 我知道原因了
作者: ro9956882 (幽灵)   2021-04-24 02:42:00
pivot在end可行的话 多一行swap(list[mid],list[end])

Links booklink

Contact Us: admin [ a t ] ucptt.com