我的任務是使用指向陣列第一個和最后一個元素的指標對結構陣列進行快速排序。這是結構
typedef struct Bus {
int number, distance, time; } Bus;
在程式的某個時刻，我有一個用戶定義數量的這些結構的陣列。我的目標是按時間（從最低到最高）對陣列進行排序。我需要填寫的功能是-
void swap(Bus *a, Bus *b)
void quick_sort (Bus *start, Bus *end)
Bus *partition (Bus *start, Bus *end)
那是我的實作-
void swap(Bus *a, Bus *b)
{
Bus tmp = *a;
*a = *b;
*b = tmp;
}
void quick_sort (Bus *start, Bus *end)
{
long long n = end - start;
if (n > 2)
{
Bus * pivot = partition (start, end);
quick_sort (start, (end-1));
quick_sort ((start 1), end);
}
}
Bus *partition (Bus *start, Bus *end)
{
long long n = end - start;
int pivot = (end -1)->time;
int i = start->time;
int j = (end - 1)->time;
for(;;)
{
}
}
我走到這一步，不知道如何繼續。我會感謝你的幫助。
quick_sort(arr, (arr num_of_lines))編輯-當 num_of_lines 是陣列的大小時，這就是我從 main- 呼叫函式的方式。
uj5u.com熱心網友回復：
首先，你quick_sort錯了。它應該如下所示：
void quick_sort(Bus *start, Bus *end)
{
long long n = end - start;
if (n >= 2)
{
Bus *pivot = partition(start, end);
quick_sort(start, pivot );
quick_sort(pivot, end);
}
}
注意長度條件。您應該只跳過長度為 0 或 1，而不是 2 的磁區。并注意在第一次遞回呼叫中對樞軸索引的后增量調整。這可確保后續遞回不包含您不想包含在遞回中的一個元素：樞軸索引值。
就磁區函式而言，也是錯誤的。它應該看起來像這樣（我假設您使用的是Lomuto 磁區方案：
int *partition(Bus *beg, Bus *end)
{
long len = end - beg;
if (len < 2)
return beg;
Bus *last = end-1;
Bus *pvt = beg;
for (;beg != last; beg)
{
if (beg->time < last->time)
swap(pvt , beg);
}
swap(pvt, last);
return pvt;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/454847.html
下一篇：兩個指標的差