Задача: Простая быстрая сортировка
Исходник: Быстрая сортировка, выбор середины отрезка, язык: C++ [code #13, hits: 17726]
автор: - [добавлен: 24.01.2006]
  1. template<class T>
  2. void QuickSortCenter(T* x, long N) {
  3. long i = 0, j = N; // начальные значения
  4. T temp, p;
  5.  
  6. p = x[ N>>1 ]; // выбираем середину
  7.  
  8. // процедура разделения
  9. do {
  10. while (x[i] < p) i++;
  11. while (x[j] > p) j--;
  12.  
  13. if (i <= j) {
  14. temp = x[i]; x[i] = x[j]; x[j] = temp;
  15. i++; j--;
  16. }
  17. } while (i <= j);
  18.  
  19.  
  20. // рекурсивные вызовы, если есть, что сортировать
  21. if ( j > 0 ) QuickSortCenter(x, j);
  22. if ( N > i ) QuickSortCenter(x+i, N-i);
  23. }
Перед каждым перераспределением выбирается элемент, находящийся в центре последовательности.
Обратите внимание на рекурсивный вызов в строке 22:

QuickSortCenter(<b>x+i</b>, N-i);

Это означает сдвинутый указатель на массив. Т.е. получим указатель на массив, который начинается с i-го элемента первоначального массива x. То, что и требуется.

Глубина реккурсии в среднем - (log n).

Производительность, в среднем: ~ O(n*log n)
Расход памяти: ~ O(log n)
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

+добавить реализацию