申論題

#include <iostream> #include <algorithm> // 引入 std::swap

int partition(int* S, int left, int right, int pivotIndex) { int pivotValue = S[pivotIndex]; std::swap(S[pivotIndex], S[right]); // 將 pivot 移動到結尾 int storeIndex = left;

for (int i = left; i < right; i++) { if (S[i] > pivotValue) { // 這裡是大於號，因為我們要找第 K 大的數 std::swap(S[i], S[storeIndex]); storeIndex++; } }

std::swap(S[storeIndex], S[right]); // 將 pivot 移動到它的最終位置 return storeIndex; }

int quickselect(int* S, int left, int right, int K) { if (left == right) { // 只有一個元素時 return S[left]; }

// 選擇 pivot 索引 int pivotIndex = left + (right - left) / 2;

pivotIndex = partition(S, left, right, pivotIndex);

if (K == pivotIndex) { return S[K]; } else if (K < pivotIndex) { return quickselect(S, left, pivotIndex - 1, K); } else { return quickselect(S, pivotIndex + 1, right, K); } }

int SelectionK(int* S, int n, int K) { return quickselect(S, 0, n - 1, K - 1); }

int main() { int S[] = {3, 2, 1, 5, 6, 4}; int n = sizeof(S) / sizeof(S[0]); int K = 2; // 我們想找到第 2 大的數值

std::cout << "第 " << K << " 大的數值是 " << SelectionK(S, n, K) << std::endl; return 0; }