STL中nth_element的用法

nth_element函數原型有四個，詳細我就不一一累贅了，我們就用最普通的用法尋找第k位置的元素。

函數用法為：nth_element(first，kth，end)。

first，last 第一個和最後一個疊代器，也可以直接用數組的位置。

kth，要定位的第k個元素，能對它進行随機通路.

将第k_th元素放到它該放的位置上，左邊元素都小于等于它，右邊元素都大于等于它.

例如：

1     vector<int> a(9);
 2     for(int i = 0; i < 9; i++)
 3         a[i] = i+1;
 4     random_shuffle(a.begin(),a.end());
 5     for(int i = 0; i < 9; i++)
 6         cout << a[i] << " ";
 7     cout << endl;
 8 
 9     nth_element(a.begin(),a.begin()+4,a.end());
10     cout << *(a.begin()+4) << endl;
11     
12     for(int i = 0; i < 9; i++)
13         cout << a[i] << " ";
14     cout << endl;      

結果為：

可以發現函數隻是把kth的元素放在了正确位置，對其他元素并沒有排序，是以可以利用這個函數快速定位第k個元素，當然，這個函數也支援你直接寫比較函數，此處不再累贅因為ACM中基本不會用到。

那麼為什麼要選擇這個函數呢，這就和複雜度有關了，nth_element的空間複雜度為O(1)，在資料量大的時候時間複雜度為O(n)，資料少的情況最壞為O(n^2)，因為函數原理是随機通路，但實際運用過程中，基本都會是O(n)的時間複雜度。是以說是非常迅速的。