Детали быстрой сортировки

В основном он вводит быструю сортировку и оптимизацию трех быстрых сортировок и, наконец, приводит к быстрой сортировке по трем направлениям.

Оригинальный текст можно найти в моем техническом блоге.Томатная технологическая станция

Определение (Энциклопедия Baidu)

Быстрая сортировка была предложена К. А. Р. Хоаром в 1962 году. Его основная идея заключается в следующем: разделить данные для сортировки на две независимые части с помощью одной сортировки, все данные в одной части меньше, чем все данные в другой части, а затем использовать этот метод для быстрого выполнения двух частей данных. соответственно Сортировка, весь процесс сортировки может выполняться рекурсивно, так что все данные становятся упорядоченной последовательностью.

Шаги алгоритма (вики)

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

Реализация кода быстрой сортировки (базовая)

анализировать

• Сначала найдите элемент данных;
• Раздел: все элементы, размер которых меньше эталонного значения, помещаются перед эталоном, а все элементы, размер которых превышает эталонное значение, помещаются за эталоном;
• Рекурсивно сортировать левый и правый подмассивы рекурсивно

Диаграмма (важны начальные условия)

partitionв какой-то момент

• Когда e>v, я сразу i++

• Когда e e поменять местами, j++, i++

• Конечное состояние: (возврат j)

  

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

Самое главное — реализовать функцию разбиения, а самое главное для реализации функции разбиения — инициализировать значение состояния (l,l+1)

//对arr[l...r]部分进行partition操作
// 返回p,使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
function partition(&$arr, $l, $r){
	$v = $arr[$l];
	$j = $l;

	for ($i=$l+1; $i <= $r ; $i++) { 
		if ($arr[$i] < $v) {
			swap($arr, $j+1, $i);
			$j++;
		}
	}
	swap($arr, $l, $j);
	return $j;
}

/**
 * [__quickSort 对数组arr[l...r]进行快速排序]
 * @param  [type] &$arr [description]
 * @param  [type] $l    [description]
 * @param  [type] $r    [description]
 * @return [type]       [description]
 */
function __quickSort(&$arr, $l, $r){
	if ($l >= $r) {
		return;
	}

	//优化点1
	// if($r - $l <= 15){
	// 	insertSortCom($arr, $l, $r);
	// 	return;
	// }

	$p = partition($arr, $l, $r);

	__quickSort($arr, $l, $p-1);
	__quickSort($arr, $p+1, $r);
}

function quickSort(&$arr, $n){
	__quickSort($arr, 0, $n-1);
}

время исполнения

mergeSort运行的时间为：0.031744003295898s
quickSort运行的时间为：0.02904486656189s

Точка оптимизации 1

Или выполните сортировку вставками непосредственно в массиве, если массив меньше 16.

function __quickSort(&$arr, $l, $r){
	// if ($l >= $r) {
	// 	return;
	// }

	//优化点1
	if($r - $l <= 15){
		insertSortCom($arr, $l, $r);
		return;
	}

	$p = partition($arr, $l, $r);

	__quickSort($arr, $l, $p-1);
	__quickSort($arr, $p+1, $r);
}

Точка оптимизации 2

Для случая, когда последовательность в основном упорядочена

// //main
$n = 100000;
// $arr = generateRandomArray($n, 0, $n);
$arr = generateNearlyOrderedArray($n, 100);
$copy_arr = $arr;
testSort("mergeSort", "mergeSort", $copy_arr, $n);
testSort("quickSort", "quickSort", $arr, $n);

Сравнение времени алгоритмов сортировки слиянием и быстрой сортировки

mergeSort运行的时间为：0.32358503341675s
quickSort运行的时间为：18.838504076004s

анализировать

Когда массив почти упорядочен, последовательность каждого деления быстрой сортировки крайне несбалансирована и почти вырождается в алгоритм с временной сложностью O(N*N).

Нет решения, да! Просто случайным образом выберите «базовый номер» каждый раз.

Решение проблем (внедрение кода)

Просто добавьте его в код разделаswap($arr, $l, rand($l, $r));

function partition(&$arr, $l, $r){

	swap($arr, $l, rand($l, $r));

	$v = $arr[$l];
	$j = $l;

	for ($i=$l+1; $i <= $r ; $i++) { 
		if ($arr[$i] < $v) {
			swap($arr, $j+1, $i);
			$j++;
		}
	}
	swap($arr, $l, $j);
	return $j;
}

время исполнения

mergeSort运行的时间为：0.21585202217102s
quickSort运行的时间为：0.34276294708252s

Оптимизация точки 3

В случае большого количества повторяющихся элементов в последовательности

$n = 100000;
$arr = generateRandomArray($n, 0, 10);
$copy_arr = $arr;
testSort("mergeSort", "mergeSort", $copy_arr, $n);
testSort("quickSort", "quickSort", $arr, $n);

часы работы

mergeSort运行的时间为：0.89260506629944s
quickSort运行的时间为：19.236886024475s

анализировать

Когда в последовательности много повторяющихся элементов, мы обнаруживаем, что скорость быстрой сортировки очень низкая, и у нас есть основания подозревать, что она может выродиться в алгоритм с временной сложностью O(n*n). В нашем коде все случаи, когда arr[i] равен v, размещаются справа, поэтому раздел будет крайне несбалансированным:

Решение проблем (внедрение кода)

** Анализ сценария **

• начальная сцена

  

• arr[i++

• arr[j--

• до того какi] >= e,j] <= e, swap(arr[j]); в это время элементы, повторяющиеся с $v, равномерно распределены по обеим сторонам последовательности

• конечное состояние

Код

/*--------------------第二种算法开始-------------------*/


//对arr[l...r]部分进行partition操作
// 返回p,使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
function partition2(&$arr, $l, $r){

	swap($arr, $l, rand($l, $r));

	$v = $arr[$l];
	// arr[l+1...i) <= v; arr(j...r] >= v
	$i = $l+1;
	$j = $r;

	while (true) {
		while($arr[$i] < $v && $i <= $r){
			$i++;
		}
		while($arr[$j] > $v && $j >= $l+1){
			$j--;
		}
		if ($i > $j) {
			break;
		}
		swap($arr, $i, $j);
		$i++;
		$j--;
	}
	swap($arr, $l, $j);
	return $j;
}


function quickSort2(&$arr, $n){
	__quickSort2($arr, 0, $n-1);
}

function __quickSort2(&$arr, $l, $r){
	// if ($l >= $r) {
	// 	return;
	// }

	//优化点1
	if($r - $l <= 15){
		insertSortCom($arr, $l, $r);
		return;
	}

	$p = partition2($arr, $l, $r);

	__quickSort2($arr, $l, $p-1);
	__quickSort2($arr, $p+1, $r);
}


/*--------------------第二种算法结束-------------------*/

сравнение времени выполнения

mergeSort运行的时间为：1.1809809207916s
quickSort运行的时间为：25.186847925186s
quickSort2运行的时间为：0.20458602905273s

Видно, что временная сложность оптимизированной быстрой сортировки возвращается к O(N*logN). На самом деле трехфакторный алгоритм быстрой сортировки может быть получен из алгоритма оптимизации 2.

Трехсторонний алгоритм быстрой сортировки

определение

Трехсторонняя быстрая сортировка — это оптимизированная версия быстрой сортировки, которая делит массив на три сегмента, а именно меньше опорного элемента, равно опорному элементу и больше опорного элемента, чтобы более эффективно обрабатывать ситуацию, когда один и тот же элемент элементы существуют в массиве, и другие функции, связанные с быстрой сортировкой, в основном одинаковы.

значок

• Исходная ситуация

• если обр[i++

• если обр[arr[arr[i++, $lt++

• если обр[arr[arr[gt--, $i++

• конечное состояние

Код

/*--------------------第三种算法开始-------------------*/

//对arr[l...r]部分进行partition操作
// 返回p,使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
function partition3(&$arr, $l, $r){

	swap($arr, $l, rand($l, $r));

	$v = $arr[$l];
	$lt = $l;
	$i = $l + 1;
	$gt = $r + 1;

	while($i < $gt){
		if ($arr[$i] == $v) {
			$i++;
		}elseif ($arr[$i] < $v) {
			swap($arr, $lt+1, $i);
			$lt++;
			$i++;
		}else{
			swap($arr, $gt-1, $i);
			$gt--;
		}
	}
	swap($arr, $l, $lt);
	return array("lt" => $lt, "gt" => $gt);
}


function quickSort3(&$arr, $n){
	__quickSort3($arr, 0, $n-1);
}

function __quickSort3(&$arr, $l, $r){
	// if ($l >= $r) {
	// 	return;
	// }

	//优化点1
	if($r - $l <= 15){
		insertSortCom($arr, $l, $r);
		return;
	}


	$rt = partition3($arr, $l, $r);
	$lt = $rt['lt'];
	$gt = $rt['gt'];

	__quickSort3($arr, $l, $lt -1);
	__quickSort3($arr, $gt, $r);
}

/*--------------------第三种算法结束-------------------*/

время результат

quickSort2运行的时间为：0.43507099151611s
quickSort3运行的时间为：0.19537496566772s

Видно, что 3-сторонний алгоритм быстрой сортировки по-прежнему очень быстр.

---

------------------------- Великолепная разделительная линия --------------------

Друзья, которые прочитали это, могут лайкнуть / подписаться, ваша поддержка - самая большая поддержка для меня.

личный блогСтек томатной технологиииДомашняя страница Наггетс

Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт в WeChat: Tomato Technology Stack.