Алгоритм быстрой сортировки - это алгоритм сортировки на месте со временем выполнения O (n log n) (с редким наихудшим случаем O (n²)). Написание быстрой сортировки включает в себя написание двух методов: метода разбиения и метода быстрой сортировки. В методе разделения мы выбираем один элемент из списка, это может быть любой элемент. Выбранный номер мы будем называть сводным. Затем вы переупорядочиваете список так, чтобы все элементы, меньшие, чем точка поворота, находились слева от нее, а все элементы справа от нее были справа от нее. Наконец, как только pIndex возвращается из метода разделения, вы можете рекурсивно вызвать метод быстрой сортировки как для левой, так и для правой половины массива, непрерывно сортируя, пока каждая «половина» не будет состоять только из одного элемента.
Я собираюсь работать с массивом myArray, [3, 4, 1, 5, 7, 1, 4].
Я написал метод разделения и выбрал последний элемент в качестве стержня, 4. Чтобы визуализировать, как работает метод разделения, я написал, что должно происходить при каждом вызове. Необходимо учитывать три части данных: сводную таблицу, индекс раздела и текущий элемент. Если текущий элемент меньше, чем точка поворота, то мы заменим его индексом раздела и увеличим индекс раздела на 1.
Отсюда мы можем рекурсивно решить эту проблему, запустив быструю сортировку для себя с элементами от begin - p_index - 1, а затем p_index + 1 - end. Наш базовый случай для этого цикла должен гарантировать, что список, который мы сортируем, больше одного элемента (в противном случае он уже отсортирован).
Ниже представлена моя реализация алгоритма быстрой сортировки в Ruby:
