stl的sort和手寫快排的運行效率哪個比較高？
來源：程序員人生 發布時間：2016-04-05 08:11:35 閱讀次數：5507次
STL的sort必定要比你自己寫的快排要快，由于你自己手寫1個這么復雜的sort，那就太閑了。STL的sort是盡可能讓復雜度保持在O(N log N)的，因此就有了各種的Hybrid sort algorithm。題主你提到的先quicksort到1定深度以后就轉為heapsort，這類是introsort。每種STL實現使用的算法各有不同，GNU Standard C++ Library的實現就是先introsort，然后再來個insertion sort。References:- sort (C++)
- Introsort
- libstdc++: Sorting Algorithms
詳情：STL sort源碼剖析
STL的sort()算法，數據量大時采取Quick Sort，分段遞歸排序，1旦分段后的數據量小于某個門坎，為避免Quick Sort的遞歸調用帶來過大的額外負荷，就改用Insertion Sort。如果遞歸層次過深，還會改用Heap Sort。本文先分別介紹這個3個Sort，再整合分析STL sort算法(以上3種算法的綜合) -- Introspective Sorting(內省式排序)。
。。。。
VS2010版STL中的sort竟比我自己寫的快這么多？
首先，上文實現的這個Introsort是參照SGI STL寫的，因而，我大膽在VS2010中拿他與std:sort比了比快慢。因而就隨機產生兩個百萬數據的vector用來測試。結果發現，VS中sort的速度竟是我的10倍以上的效力。頓時對微軟萌發敬意，可是當我仔細翻看源碼時.....
原來，microsoft的sort并沒有比sgi的sort快。只是在排序vector時，microsoft把vector的本質數據“萃取”出來了。
即，取消了vector在++時的邊界檢查語句，把vector::iterator當指針1般使用。所以才在對vector排序時會比我自己寫的introsort算法快那末多呢。
版權聲明：本文為【借你1秒】原創文章，轉載請標明出處。
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
