кодесурса
«PHP

Алгоритм поиска и сортировки PHP: Shell sort

script1adsense2code
script1adsense3code

Алгоритм поиска и сортировки PHP: упражнение 5 с решением

Напишите программу PHP для сортировки списка элементов, используя сортировку Shell.

Согласно Википедии «Сортировка оболочки или метод Shell является сортировкой сравнения на месте. Это можно рассматривать как обобщение сортировки по обмену (пузырьковая сортировка) или сортировку по вставке (вставка сортировки). Метод начинается с сортировки пар элементы находятся далеко друг от друга, а затем постепенно сокращается разрыв между сравниваемыми элементами. Начиная с далеко расположенных элементов, можно перемещать некоторые неуместные элементы в положение быстрее, чем простой обмен ближайшими соседями ».

Пример запуска Shellsort с пробелами 5, 3 и 1 показан ниже.

«

Первый проход, 5-сортировка, выполняет сортировку вставки на отдельных подмассивах (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). Например, он изменяет подмассив (a1, a6, a11) с (62, 17, 25) на (17, 25, 62). Следующий проход, сортировка 3, выполняет сортировку вставки для подмассивов (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12). Последний проход, 1-сортировка, является обычной сортировкой вставки всего массива (a1, ..., a12). Как показано в примере, подмассивы, на которых работает Shellsort, изначально короткие; позже они длиннее но почти заказаны. В обоих случаях сортировка вставок работает эффективно. Сортировка оболочки нестабильна: она может изменить относительный порядок элементов с равными значениями. Это адаптивный алгоритм сортировки, который выполняется быстрее при частичной сортировке входных данных.

Shell Sort

«ShellSort

Shellsort с пробелами 23, 10, 4, 1 в действии .

Пример решения:

PHP-код:

<?php
function shell_Sort($my_array)
{
	$x = round(count($my_array)/2);
	while($x > 0)
	{
		for($i = $x; $i < count($my_array);$i++){
			$temp = $my_array[$i];
			$j = $i;
			while($j >= $x && $my_array[$j-$x] > $temp)
			{
				$my_array[$j] = $my_array[$j - $x];
				$j -= $x;
			}
			$my_array[$j] = $temp;
		}
		$x = round($x/2.2);
	}
	return $my_array;
}
 
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "Original Array :\n";
echo implode(', ',$test_array );
echo "\nSorted Array\n:";
echo implode(', ',shell_Sort($test_array)). PHP_EOL;
?>

Пример вывода:

 Оригинальный массив:                                                    
3, 0, 2, 5, -1, 4, 1                                                
Сортированный массив:                                                      
-1, 0, 1, 2, 3, 4, 5 

Блок-схема:

«Блок-схема:

Редактор кода PHP:


Есть другой способ решить это решение? Внесите свой код (и комментарии) через Disqus.

Предыдущий: Напишите программу PHP для сортировки списка элементов, используя сортировку Selection.
Далее: Напишите программу PHP для сортировки списка элементов, используя Bubble sort.

Каков уровень сложности этого упражнения?

Новый контент: Composer: менеджер зависимостей для PHP , R программирования


script1adsense4code
script1adsense5code
disqus2code
script1adsense6code
script1adsense7code
script1adsense8code
buysellads2code