Быстрая сортировка на C++

Приведите пример алгоритма быстрой сортировки на C++.

Ответ

#include
template inline void swap( T & arg1, T & arg2) { T temp = arg1; arg1 = arg2; arg2 = temp; }; template inline int get_median_index( std::vector & vArray, int lower, int upper) { if ((upper-lower) < 2) return lower;
int middle = (upper+lower)/2;
if (vArray[lower] <= vArray[middle]) { if (vArray[middle] <= vArray[upper]) { return middle; } else if (vArray[upper] <= vArray[lower]) { return lower; } else { return upper; } } else { if (vArray[lower] <= vArray[upper]) { return lower; } else if(vArray[upper] <= vArray[middle]) { return middle; } else { return upper; } } return lower; }; template inline int partition( std::vector & vArray, int start, int end, int median_index) { int head = start, tail = end-1; swap( vArray[median_index], vArray[end]); while (true) { while (vArray[head] < vArray[end]) { ++head; } while (vArray[tail] > vArray[end] && tail > start) { --tail; } if ( head >= tail) { break; } swap( vArray[head++], vArray[tail--]); } swap( vArray[head], vArray[end]); return head; }; template inline void quick_sort_helper( std::vector & vArray, int head, int tail) { int median_index, diff = tail-head;
if (diff < 1) { return; } if (diff == 1) { if (vArray[head] > vArray[tail]) { swap( vArray[head], vArray[tail]); } }
median_index = get_median_index(vArray, head, tail); median_index = partition( vArray, head, tail, median_index);
quick_sort_helper( vArray, head, median_index-1); quick_sort_helper( vArray, median_index+1, tail); }; template void quick_sort( std::vector & vArray) { int head = 0, tail = vArray.size()-1; quick_sort_helper( vArray, head, tail); };