Я нашел этот статья на среде и пытаюсь понять, что на самом деле делает код.
это код:
помощник
const defaultComparator = (a, b) => {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
};
функция сортировки
const quickSort = (
unsortedArray,
comparator = defaultComparator
) => {
// Create a sortable array to return.
const sortedArray = [ ...unsortedArray ];
// Recursively sort sub-arrays.
const recursiveSort = (start, end) => {
// If this sub-array is empty, it's sorted.
if (end - start < 1) {
return;
}
const pivotValue = sortedArray[end];
let splitIndex = start;
for (let i = start; i < end; i++) {
const sort = comparator(sortedArray[i], pivotValue);
// This value is less than the pivot value.
if (sort === -1) {
// If the element just to the right of the split index,
// isn't this element, swap them.
if (splitIndex !== i) {
const temp = sortedArray[splitIndex];
sortedArray[splitIndex] = sortedArray[i];
sortedArray[i] = temp;
}
// Move the split index to the right by one,
// denoting an increase in the less-than sub-array size.
splitIndex++;
}
// Leave values that are greater than or equal to
// the pivot value where they are.
}
// Move the pivot value to between the split.
sortedArray[end] = sortedArray[splitIndex];
sortedArray[splitIndex] = pivotValue;
// Recursively sort the less-than and greater-than arrays.
recursiveSort(start, splitIndex - 1);
recursiveSort(splitIndex + 1, end);
};
// Sort the entire array.
recursiveSort(0, unsortedArray.length - 1);
return sortedArray;
};
Итак, я потратил некоторое время, чтобы понять, как работает splitIndex
. Он начинается с 0 и увеличивается на 1, только если текущий элемент в цикле for меньше, чем точка поворота. Когда мы сталкиваемся с числом, превышающим опорное значение, splitIndex остается на своем значении, а i
увеличивается. На следующем шаге, если число также меньше, чем пивот, мы меняем их местами.
Так, например, с этим массивом: [2,4,65,1,15]
splitIndex и i равны во время цикла for, пока мы не получим число 65. Здесь splitIndex не увеличивается, и когда мы достигаем числа 1, мы меняем местами 1 и 65.
Я не носитель английского языка, поэтому я не совсем понимаю, что автор имеет в виду:
// If the element just to the right of the split index,
// isn't this element, swap them.
Мне еще предстоит полностью понять, как работает код, но, по-вашему, правильно ли я сказал?
Спасибо
Это в основном Схема разбиения Ломуто . Проверка splitIndex != i, вероятно, займет больше времени, чем избегание ненужных свопов.
Переменная splitIndex
отслеживает (в той части массива, которую вы сейчас сортируете) разделитель между элементами, которые «меньше» и «равны или больше», чем опорная точка. Ваше описание того, как это работает, кажется в основном правильным.
В общем, если мы сталкиваемся с элементом, который меньше опорного элемента, мы меняем его на элемент в splitIndex
, чтобы поместить его в раздел «меньше, чем опорный», а затем увеличиваем splitIndex
, чтобы указать, что раздел вырос. Если мы встречаем тот, который равен или больше, мы оставляем его там, где он есть, и не увеличиваем раздел.
Это имеет смысл предполагая, что элемент в splitIndex
не меньше, чем стержень. Это верно, если i
больше, чем splitIndex
, потому что тогда мы уже встретили хотя бы один такой элемент и пропустили его.
Исключением является случай, когда мы В настоящее время проверяем элемент в splitIndex
(что будет иметь место, пока все элементы до сих пор были меньше, чем опорная точка). В этом случае мы бы заменяли элемент самим собой. Это лишнее, так что это причина проверки splitIndex !== i
.
Что касается
// If the element just to the right of the split index,
// isn't this element, swap them.
Я подозреваю, что автор допустил ошибку в комментарии. Он должен говорить «элемент в индексе разделения», а не «элемент справа от индекса разделения».
Взгляните на этот вопрос: stackoverflow.com/questions/39665299/…