STLsort源码解析

2024年5月11日发(作者：)

template

inline void sort(RandomAccessIterator first,

RandomAccessIterator last)

{

if (!(first == last))

{

__quick_sort_loop(first, last);

__final_insertion_sort(first, last);

}

}

template

inline void __quick_soort_loop(RandomAccessIterator first,

RandomAccessIterator last)

{

__quick_soort_loop_aux(first, last, _RWSTD_VALUE_TYPE(first));

}

template

void __quick_sort_loop_aux(RandomAccessIterator first,

RandomAccessIterator last,

T*)

{

while (last - first > __stl_threshold)

{

//median-of-3 partitioning

RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first + (last - first) / 2), *(last - 1)));

if (cut - first >= last - cut)

{

__quick_soort_loop(cut, last);//对右段递归处理

last = cut;

}

else

{

__quick_sort_loop(first,cut);

first = cut;

}

}

}