contributed by < LIAO-JIAN-PENG
>
/* shuffle array, only work if n < RAND_MAX */
void shuffle(int *array, size_t n)
{
if (n <= 0)
return;
for (size_t i = 0; i < n - 1; i++) {
size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
int t = array[j];
array[j] = array[i];
array[i] = t;
}
}
在 rand() 函式中,它生成的隨機數的範圍是 0 到 RAND_MAX。然而,我們需要的是一個介於 i 到 n-1 之間的隨機整數。
一種方法是將 rand() 函式生成的隨機數除以 (RAND_MAX / (n - i) + 1)。這樣可以得到一個介於 0 到 (n - i) - 1 之間的隨機整數。然後,我們將這個值加上 i,這樣就可以得到介於 i 到 n-1 之間的隨機整數。添加 1 的目的是確保 (n - i) 不為 0,以避免除法計算可能導致的錯誤。
C 語言規格書 7.22.2.1
The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX.
這段程式碼使用了 Optimized QuickSort — C Implementation (Non-Recursive) 非遞迴快速排序法。在這個算法中,我們使用 L
和 R
來記錄待排序部分的起始和結束位置。首先,我們將 L
設置為 pivot
,然後通過 n
和 p
遍歷後面的節點。將小於 pivot->value
的節點放入 left
,將大於 pivot->value
的節點放入 right
。這些節點以後進先出(LIFO)的方式被存入,以相反的順序記錄著節點。以 3, 1, 2, 4, 5
做舉例
在這個過程中,我們使用 begin[i]
和 end[i]
來分別記錄 left
部分的開始和結束位置,使用 begin[i+1]
和 end[i+1]
來記錄 pivot
,以及使用 begin[i+2]
和 end[i+2]
來記錄 right
部分的開始和結束位置。每次循環中 i+=2
表示我們下一次迭代將針對 right
部分進行排序。
當 L
等於 R
時,這表示我們只剩下一個節點,我們將排序結果放入 result
中。
當 L
不等於 R
時,我們仍然可以將其分成 left
和 right
兩部分進行操作。