Код: Выделить всё
#include <iostream>
using namespace std;
//создается шаблнная функция
template<class T>
// функция принимает аргументы:
// массив (так как функция шаблонная, то любого типа массив), и кол-во элементов массива.
void quickSortR(T* a, long N)
{
long i = 0, j = N;
// T - это тип передаваемого массива
// создаем две перменных этого типа
T temp, p;
p = a[ N>>1 ];
// процедура разделения (разделяет массив на подмассивы)
do {
while ( a[i] < p ) i++;
while ( a[j] > p ) j--;
if (i <= j)
{
// обмен местами элементов a[i] с a[j]
// то есть, то что было в a[i] станет в a[j]
// а то, что было в a[j] станет в a[i]
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while ( i<=j );
// рекурсивные вызовы, если есть, что сортировать
if ( j > 0 ) quickSortR(a, j); // рекурсивно вызываем функцию
if ( N > i ) quickSortR(a+i, N-i); // рекурсивно вызываем функцию
}
// ------------------------------------------------------------------------------
int main()
{
setlocale(LC_ALL, "Russian"); // создаем массив символов
char str[] = "бвгда";
// сортируем массив символов
quickSortR(str, strlen(str));
// выводим на экран отсортированный массив симовлов
cout << str << endl;
// создаем целочисленный массив
int a[] = {50, 7, 3, 9, 25, 33, -5};
// сортируем целочисленный массив
quickSortR(a, 6);
// выводим на экран отсортированный целочисленный массив
for(int i = 0; i < 7; i++)
cout << a[i] << " ";
cout << endl;
system("pause");
return 0; // функция main ДОЛЖНА возвращать число
}
Сейчас растолкую часть шаблонной функции, которую я понимаю, а то что не ясно,я спрошу. Начну, сначала:
Создаётся шаблонная функция с 2 параметрами, 1 - парметр указатель на масив, 2 - ой - количество элементов масива. Создаём 2 переменные шаблонного типа temp, p. Переменной p присваиваем центральный элемент масива. Далее, начинается сам алгоритм:
Возьмём числа какие мы имеем в масиве.
Код: Выделить всё
[B] 50, 7, 3, 9, 25, 33, -5 [/B]p = 9, i = 0, j = 6
Код: Выделить всё
1) while(a[i]<p) i++;
50<p? НЕТ i осталось 0;
while(a[i]>p) j--;
-5>p? Нет j осталось 6.
Код: Выделить всё
2)if (i <= j)
{
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
Если i меньше чем j(тоесть если мы нашли такие элементы,которые заставили предыдущие циклы остановится, то меняем местами a[i], a[j] ;
i = 0; j = 6;
Меняем a[0] = 50, a[6] = -5/
-5 7 3 9 25 33 50
Увеличиваем i на один, j уменьшаем на один.
Код: Выделить всё
3) i = 1, j = 5;
while(a[i]<p) i++;
7<9? Да. i стаёт равно = 2;
while(a[j]>p) j--;
33>9? Да. j стаёт равно 4
Результат счётчиков i = 2, j = 4;
Код: Выделить всё
4)while(a[i]<p) i++;
3<9? Да i = 3;
5) while(a[j]>p) j--;
25>9? Да. j = 3;
Результат i = 3; j = 3; Как заканчивается цикл do ..while ?
Меня интересует место: while(i < = j) От куда подставляется в i и j?
ДАльше после этого идёт рекурсия, объясните пожалуйста,каким образом идёт подсчёт? Не ясны полностью вот эти 2 строки,на примере с теми числами:
Код: Выделить всё
if ( j > 0 ) quickSortR(a, j);
if ( N > i ) quickSortR(a+i, N-i);