Принцип и объяснение кода алгоритма быстрой сортировки PHP

Автор оригинала: David Wong.

Принцип алгоритма

Следующий график взят из пятиминутного алгоритма, который демонстрирует принцип и этапы алгоритма быстрой сортировки.

Шаг:

Выберите базовое значение из массива

Поместите большее, чем опорное значение, на ту же сторону и меньшее, чем опорное значение, на другую сторону массива, при этом опорное значение находится в средней позиции

Рекурсивно переупорядочивать массивы по обе стороны столбца

реализация кода

function quickSort($arr)

{

 $len = count($arr);

 if ($len <= 1) {

  return $arr;

 }

 

 $v = $arr[0];

 $low = $up = array();

 for ($i = 1; $i < $len; ++$i) {

  if ($arr[$i] > $v) {

   $up[] = $arr[$i];

  } else {

   $low[] = $arr[$i];

  }

 }

 $low = quickSort($low);

 $up = quickSort($up);

 

 return array_merge($low, array($v), $up);

}

Тестовый код:

$startTime = microtime(1);

 

$arr = range(1, 10);

shuffle($arr);

 

echo "before sort: ", implode(', ', $arr), "\n";

$sortArr = quickSort($arr);

echo "after sort: ", implode(', ', $sortArr), "\n";

 

echo "use time: ", microtime(1) - $startTime, "s\n";

Результаты испытаний:

before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8

after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

use time: 0.0009009838104248s

Временная сложность

В худшем случае временная сложность быстрой сортировки составляет O (N2), а средняя временная сложность составляет O (n * LGN).

Допустим, в последовательности n чисел. Временная сложность однократного обхода равна O (n). Сколько раз его нужно пройти? Не менее LG (n + 1) раз и не более N раз.

1) Почему LG (n + 1) по крайней мере раз? Быстрая сортировка выполняется методом “разделяй и властвуй”. Мы рассматриваем его как двоичное дерево. Количество раз, которое ему нужно пройти, – это глубина двоичного дерева. Согласно определению полного двоичного дерева, его глубина составляет не менее LG (n + 1). Следовательно, время прохождения быстрой сортировки составляет не менее LG (n + 1).

2) Почему не более n раз? Это должно быть очень просто или быстро сортировать как двоичное дерево, его максимальная глубина равна n. Таким образом, время прохождения быстрой сортировки чтения составляет не более n.