Схема разделов Hoare возвращает неверный индекс [дубликат]
Сохраните переменные в сеансе PHP.
session_start();
$_SESSION['images'] = $images;
Затем на следующей (или любой другой) странице вы можете получить значения как:
session_start();
$images = $_SESSION['images'];
1 ответ
Вам нужно использовать правильную процедуру quicksort, так как Hoare разбивает массив на левую часть и правую часть, в отличие от Lomuto, которая разбивает массив на левую часть, поворот, правую часть.
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p) // not quicksort(A, lo, p-1)
quicksort(A, p + 1, hi)
также выбирая точку опоры в середине означает, что уже отсортированы или обратный отсортированный массив отсортирован быстро в противоположность худшему:
pivot := A[lo+(hi-lo)/2] // or := A[(lo+hi)/2] if overflow not an issue
Там все равно будет хуже моделей случае, но, по крайней мере, простые из них являются обрабатываются. Медиана 3 немного медленнее, но уменьшает количество наихудших шаблонов:
md = lo + (hi-lo)/2
if (A[lo] > A[hi])
swap(A[lo], A[hi])
if (A[lo] > A[md])
swap(A[lo], A[md])
if (A[md] > A[hi])
swap(A[md], A[hi])
pivot := a[md]
Возможно, то, что вы ищете, - это быстрый выбор, чтобы найти k-й элемент, где k = размер массива / 2. Он похож на быстрый вид, но он рекурсивно ищет только левую или правую часть массива, содержащего k-ый элемент. Статья в вики:
-
1Спасибо за ваш ответ, но я хотел бы, чтобы функция не зависела от другой функции (в данном случае quicksort). Я хочу, чтобы он вернул правильный индекс поворота и создал правильный раздел (как метод Ломуто). Моя цель - не сортировать массив через Quicksort. – Toma Radu-Petrescu 19 December 2015 в 23:15
-
2@rptoma - Я не уверен, как функция разделения Hoare должна быть изменена, чтобы работать так же, как Ломуто. Вы можете просто использовать функцию разделения Lomuto. – rcgldr 19 December 2015 в 23:36
-
3да, Ломуто будет работать, но я читал, что Хоар делает в 3 раза больше свопов, чем Хоар. Мне очень любопытно узнать, как реализовать Хоар. – Toma Radu-Petrescu 19 December 2015 в 23:52
-
4@rptoma - я добавил комментарий к исходному вопросу, возвращаемый опорный элемент равен 1, а не 2. Hoare разбивает массив на левую часть и правую часть. Ломуто разбивает массив на левую часть, поворот, правую часть. – rcgldr 20 December 2015 в 00:42