Только помните:
pivot - это первый элемент в массиве left - это элементы ниже pivotrightэто предметы выше, чем pivot
Итак, когда у вас в первый раз qsort( [7,3,28,8,9,13,1500,45] ):
left=[3] pivot=7 right=[28,8,9,13,1500,45]
Теперь qsort() рекурсивно вызывается на оба left и right Массивы.
Давайте просто посмотрим на left, поэтому qsort( [3] ):
left=[] pivot=3 right=[]
Еще раз, qsort() рекурсивно вызывается для массивов left и right.
Опять же, давайте просто посмотрим на left, поэтому qsort( [] ):
И что делает самое первое qsort()?
if (a.length == 0) return [];
Если он получил пустой массив (что он и сделал здесь), он просто возвращает пустой массив, останавливая выполнение в этой ветви.
Поскольку каждый вызов qsort() выталкивает первый элемент из массива, каждый раз, когда вызывается qsort(), полученный массив становится все короче и короче, пока пустой массив не будет отправлен на qsort().
Другой способ думатьиз этого:
Потенциально сбивающая с толку часть состоит в том, что qsort() выбивает первый элемент, а затем разделяет остальную часть массива на 2 части.
Только представьте, если не сделалt разбил массив, но просто выбил первый предмет.
Эта функция на самом деле ничего не делает, но рекурсивно вызывает себя с остатком от массива.
function recursive_test( arr ) {
if( arr.length === 0 ) { return []; } // empty Array? Just return.
var first_item = arr.shift(); // first item in the Array (the head)
// now "arr" represents the remainder (the tail)
return recursive_test( arr ); // Just send the "tail" to the same function
// so the next time through, the Array is
} // shorter by 1
Поэтому, когда вы вызываете функцию, происходит следующее:
var array = [5,2,8,3,6,9,0]; // original Array
recursive_test( array );
// the first time it gets the full Array
// [5,2,8,3,6,9,0]
// but then it pops the first item off, and calls itself with the "tail" of the Array
// [2,8,3,6,9,0]
// again it calls itself, just with the "tail"
// [8,3,6,9,0]
// and again, and again, and again...
// [3,6,9,0]
// [6,9,0]
// [9,0]
// [0]
// []
// The last time it gets an empty Array.
// The function sees that it gets an empty Array, and just returns,
// halting the recursion
В вашей функции происходит то же самое, за исключением того, что вместо "головы" и "хвоста" с рекурсивным передачей "хвоста" вы получаете "голову" (pivot) и«Хвост», который разбивается на 2 массива (left и right).
Обе части хвоста отправляются на рекурсивные вызовы, отсекая головы, разбивая остаток и делая этоснова, пока ничего не осталось.