خوارزمية لـ nth_element [مغلق

Question

لقد اكتشفت مؤخرًا أن هناك طريقة تسمى nth_element في STL. على حد تعبير الوصف:

يشبه nth_element partial_sort ، حيث أنه يطلب جزئيًا مجموعة من العناصر: إنه يرتب النطاق [أولاً ، أخيرًا) بحيث يكون العنصر الذي أشار إليه التكرار هو نفسه العنصر الذي سيكون في هذا الموضع إذا النطاق [الأول ، الأخير) تم فرزه. بالإضافة إلى ذلك ، لا يوجد أي من العناصر في النطاق [nth ، الأخير) أقل من أي من العناصر في النطاق [الأول ، nth).

تدعي أن لديها التعقيد O (n) في المتوسط. كيف تعمل الخوارزمية؟ لم أتمكن من العثور على أي تفسير لذلك.

Answer 1

يطلق عليه خوارزمية الاختيار ، ويحتوي ويكيبيديا على صفحة لائقة: http://en.wikipedia.org/wiki/selection_algorithm

اقرأ أيضًا عن إحصائيات الطلب: http://en.wikipedia.org/wiki/order_statistic

Answer 2

على الأرجح وسيط الوسطاء.

http://en.wikipedia.org/wiki/selection_algorithm#linear_general_gelection_algorithm_-_.22median_of_algorithm.22