внедрение сортировки Shell
мой учитель сказал эту строку for (int j = i - step; j >= 0; j = j - step) портит всю суть сортировки. он сказал, что мне нужно использовать функцию сортировки вставок и вставить ее в сортировку оболочки. Как я могу это сделать?
template < typename T >
void swap(T* arr, int j, int step)
{
T value = arr[j];
arr[j] = arr[j + step];
arr[j + step] = value;
}
template < typename T >
void shell_sort(T* arr, int length)
{
for (int step = length / 2; step > 0; step = step / 2)
{
for (int i = step; i < length; i++)
{
for (int j = i - step; j >= 0; j = j - step)
{
if (arr[j] > arr[j + step])
{
swap(arr, j, step);
}
}
}
}
}
Решение
Вы можете перейти к рекурсивной сортировке оболочки следующим образом:
template < typename T >
int shell_sort(T* arr, int length)
{
if (length <= 1) return length;
length = shell_sort(arr,length - 1);
T value = arr[length];
T i = length - 1;
while ((i >= 0) && (arr[i] > value)) {
arr[i + 1] = arr[i];
i--;
}
arr[i + 1] = value;
return length + 1;
}
Другие решения
Других решений пока нет …