Быстрая сортировка часто применяется, поскольку её эффективность сортировки относительно высока среди нескольких методов сортировки, имеющих сложность O(N*logN). Кроме того, идея быстрой сортировки — метод разделяй и властвуй — действительно практична. Поэтому многие софтверные компании любят проверять это в письменных тестах и на собеседованиях, включая известные IT-компании, такие как Tencent и Microsoft. Также быстрая сортировка часто встречается на экзаменах, связанных с программированием, разного уровня, например на экзамене на квалификацию в сфере программного обеспечения и вступительном экзамене в аспирантуру.

=a

Быстрая сортировка — это сортировка с разделением-обменом, предложенная Ч. Р. А. Хоаром в 1962 году. В ней используется стратегия «разделяй и властвуй», обычно называемая методом разделяй и властвуй (Divide-and-Conquer Method).

Основная идея этого метода заключается в следующем:

• 1. Сначала возьмите одно число из последовательности в качестве опорного элемента.
• 2. В процессе разбиения поместите все числа, большие этого числа, справа от него, а все числа, меньшие или равные ему, — слева от него.
• 3. Повторите шаг 2 для левого и правого интервалов, пока в каждом интервале не останется только одно число.

Хотя быстрая сортировка называется методом разделяй и властвуй, эти три слова, очевидно, не могут полностью охватить все шаги быстрой сортировки. Поэтому я привёл дополнительное объяснение быстрой сортировки: рытьё ям и заполнение чисел + разделяй и властвуй.

Сначала рассмотрим пример. Определение дано ниже (лучше пересказать определение своими словами, так как это поможет при реализации кода).

 

Возьмём массив в качестве примера и возьмём первое число в интервале в качестве опорного элемента.

0	1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

Изначально i = 0; j = 9; X = a[i] = 72

Поскольку число в a

Начиная с j, ищем влево число, меньшее или равное X. Когда j=8, условие выполнено. Выкапываем a

 

Массив становится:

0	1	2	3	4	5	6	7	8	9
48	6	57	88	60	42	83	73	88	85

 

i = 3;   j = 7;   X=72

Повторите вышеуказанные шаги: сначала поиск с конца к началу, затем с начала к концу.

Ищем влево, начиная с j. Когда j=5, условие выполнено. Выкапываем a

Ищем вправо, начиная с i. Когда i=5, выходим, потому что i==j.

На этом этапе i = j = 5, и a

Массив становится:

0	1	2	3	4	5	6	7	8	9
48	6	57	42	60	72	83	73	88	85

Видно, что числа перед a

 

Подведём итог по выкапыванию ям и заполнению числами:

• 1. i = L; j = R; выкопать опорный элемент, чтобы образовать первую яму a[i].
• 2. j--, искать с конца к началу число, меньшее него. Найдя его, выкопать это число и заполнить им предыдущую яму a[i].
• 3. i++, искать с начала к концу число, большее него. Найдя его, также выкопать это число и заполнить им предыдущую яму a[j].
• 4. Повторять шаги 2 и 3, пока не выполнится i==j, затем поместить опорный элемент в a[i].

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

int AdjustArray(int s[], int l, int r) //Возвращает позицию скорректированного опорного элемента { int i = l, j = r; int x = s[l]; //s[l], то есть s[i], — это первая яма while (i < j) { // Найти число меньше x справа налево, чтобы заполнить s[i] while(i < j && s[j] >= x) j--; if(i < j) { s[i] = s[j]; //Заполнить s[i] значением s[j], тогда s[j] образует новую яму i++; } // Найти число большее или равное x слева направо, чтобы заполнить s[j] while(i < j && s[i] < x) i++; if(i < j) { s[j] = s[i]; //Заполнить s[j] значением s[i], тогда s[i] образует новую яму j--; } } //При выходе i равно j. Заполнить эту яму значением x. s[i] = x; return i; }

Затем напишите код для метода «разделяй и властвуй»:

void quick_sort1(int s[], int l, int r) { if (l < r) { int i = AdjustArray(s, l, r);//Сначала используйте метод выкапывания ямок и заполнения чисел, чтобы скорректировать s[] quick_sort1(s, l, i - 1); // Рекурсивный вызов quick_sort1(s, i + 1, r); } }

Такой код явно недостаточно лаконичен, поэтому объедините и приведите его в порядок:

//Быстрая сортировка void quick_sort(int s[], int l, int r) { if (l < r) { //Swap(s[l], s[(l + r) / 2]); // Поменяйте среднее число с первым. См. примечание 1 int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x) //Найдите первое число, меньшее x, справа налево j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) //Найдите первое число, большее или равное x, слева направо i++; if(i < j) s[j--] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); // Рекурсивный вызов quick_sort(s, i + 1, r); } }

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

Примечание 1: в некоторых книгах в качестве опорного элемента используется средний элемент. Чтобы реализовать это, очень просто — просто поменяйте средний элемент с первым.

Автор: MoreWindows

Оригинальная статья: https://blog.csdn.net/morewindows/article/details/6684558