|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
10.10.2012, 21:15 | #1 |
Пользователь
Регистрация: 19.10.2011
Сообщений: 51
|
алгоритм Шелла
как увеличить скорость этого алгоритма Шелла в 2 раза ....
Где-то читал про Сортировку методом Шелла-Кнута. Кнут просто подобрал номера h для увеличения скорости сортровкы. Но я не знаю сделать методом Шелла-Кнута. / * Метод Кнута h (k-1) = 3 * h (k) +1, h (t) = 1, где h (i) - шаг сортировки, t = ln (n) / ln (3) -1 - число шагов сортировки, n - длина списка * / void sort_Shell(int *mass, int SIZE) { int step = SIZE / 2;//инициализируем шаг. while (step > 0)//пока шаг не 0 { for (int i = 0; i < (SIZE - step); i++) { int j = i; while (j >= 0 && mass[j] > mass[j + step]) { int temp = mass[j]; mass[j] = mass[j + step]; mass[j + step] = temp; j--; } } step = step / 2; } } Последний раз редактировалось rostik123; 10.10.2012 в 21:19. |
10.10.2012, 22:19 | #2 |
Пользователь
Регистрация: 19.10.2011
Сообщений: 51
|
void ShellSort(int *a, int n)
{ int h; for(h=1; h<(n-1)/9; h=3*h+1); for(... ; h>0; h/=3) //а что здесь написать не знаю for(int s=0; s<h; s++) { for(int i=s; i<n-h; i+=h) { int z=i; for(int j=i+h; j<n; j+=h) if(a[j]<a[z]) z=j; int r=a[i]; a[i]=a[z]; a[z]=r; } } } |
11.10.2012, 00:30 | #3 |
Пользователь
Регистрация: 19.10.2011
Сообщений: 51
|
сделал, сортирует быстрее, но надо еще быстрее ...
void sort_Shell(int *mass, int SIZE) { int step = SIZE / 2, i, j, tmp; while (step > 0) { for(i = step; i < SIZE; ++i) { tmp = mass[i]; for(j = i - step; j >= 0 && mass[j] > tmp; j -= step) { mass[j+step] = mass[j]; } mass[j+step] = tmp; } step /= 2; } } |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Метод Шелла | <<оля>> | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 14.11.2011 21:04 |
Метод Шелла | gennadii | Помощь студентам | 4 | 15.06.2011 11:00 |
Сортировка Шелла | QuadroX | Фриланс | 1 | 29.05.2010 03:52 |