開發平台(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;
}
--
