Быстрая сортировка, придуманная Ч. А Р. Хоаром (Charles Antony Richard Hoare) и названная его именем, является одним из самых лучших методов сортировок. В ее основе лежит сортировка обменами.
Быстрая сортировка построена на идее деления. Общая процедура заключается в том, чтобы выбрать некоторое значение, называемое компарандом (comparand – операнд в операции сравнения), а затем разбить массив на две части. Все элементы, большие или равные компаранду, перемещаются на одну сторону, а меньшие — на другую. Потом этот процесс повторяется для каждой части до тех пор, пока массив не будет отсортирован. Например, если исходный массив состоит из символов fedacb, а в качестве компаранда используется символ d, первый проход быстрой сортировки переупорядочит массив следующим образом:
Начало
fedacb
Проход 1
b с a d e f
Затем сортировка повторяется для обеих половин массива, то есть bса и def. Этот процесс по своей сути рекурсивный, и, действительно, в чистом виде быстрая сортировка реализуется как рекурсивная функция.
Значение компаранда можно выбирать двумя способами — случайным образом либо усреднив небольшое количество значений из массива. Для оптимальной сортировки необходимо выбирать значение, которое расположено точно в середине диапазона всех значений. Однако для большинства наборов данных это сделать непросто. В худшем случае выбранное значение оказывается одним из крайних. Тем не менее, даже в этом случае быстрая сортировка работает правильно. В приведенной ниже версии быстрой сортировки в качестве компаранда выбирается средний элемент массива
/* Функция, вызывающая функцию быстрой сортировки.*/ 
void quick(char *items, int count)
{
qs(items, 0, count-1);
}
/* Быстрая сортировка. */
void qs(char *items, int left, int right)
{
register int i, j;
char x, y;
i = left; j = right;
x = items[(left+right)/2]; /* выбор компаранда */
do {
while((items[i] < x) && (i < right)) i++;
 while ((x < items [j]) && (j > left)) j -- ;
if(i <= j) {
у = items[i];
items[i] = items[j];
items[j] = y;
i ++; j--;
}
}   
while(i  <=  j);
if (left  <  j)   qs(items,   left,   j);
if'(i <  right) qs (items,   I,   right) ;      
}

В этой версии функция quick() готовит вызов главной сортирующей функции qs(). Это обеспечивает общий интерфейс с параметрами items и count, но несущественно, так как можно вызывать непосредственно функцию qs() с тремя аргументами.
Среднее количество сравнений равно n log n, а среднее количество обменов примерно равно n/6 log n.
Эти величины намного меньше соответствующих характеристик рассмотренных ранее алгоритмов сортировки.
Необходимо упомянуть об одном особенно проблематичном аспекте быстрой сортировки. Если значение компаранда в каждом делении равно наибольшему значению, быстрая сортировка становится "медленной сортировкой" со временем выполнения порядка n2. Поэтому необходимо внимательно выбирать метод определения компаранда. Этот метод часто определяется природой сортируемых данных. Например, в очень больших списках почтовой рассылки, в которых сортировка происходит по почтовому индексу, выбор прост, потому что почтовые индексы довольно равномерно распределены и компаранд можно определить с помощью простой алгебраической функции. Однако в других базах данных зачастую лучшим выбором является случайное значение. Популярный и довольно эффективный метод — выбрать три элемента из сортируемой части массива и взять в качестве компаранда значение, расположенное между двумя другими.

Быстрая сортировка состоит в том, что список В=< K1,K2,...,Kn> реорганизуется в список B',< K1 >,B", где В' — подсписок В с элементами, не большими К1, а В" — подсписок В с элементами, большими К1. В списке B',< K1 >,B" элемент К1 расположен на месте, на котором он должен быть в результирующем отсортированном списке. Далее к спискам B' и В" снова применяется упорядочивание быстрой сортировкой. Приведем в качестве примера сортировку списка, отделяя упорядоченные элементы косой чертой, а элементы Ki знаками < и >.
9, 7, 18, 3, 52, 4, 6, 8, 5, 13, 42, 30, 35, 26
7, 3, 4, 6, 8, 5/ <9>/ 18, 52, 13, 42, 30, 35, 26
3, 4, 6, 5/<7>/ 8/ 9/ 13/ <18>/ 52, 42, 30, 35, 26
<3>/ 4, 6, 5/ 7/ 8/ 9/ 13/ 18/ 42, 30, 35, 26/ <52>
3/ <4>/ 6, 5/ 7/ 8/ 9/ 13/ 18/ 30, 35, 26/ <42>/ 52
3/ 4/ 5/ <6>/ 7/ 8/ 9/ 13/ 18/ 26/ <30>/ 35/ 42/ 52
Время работы по сортировке списка методом быстрой сортировки зависит от упорядоченности списка. Оно будет минимальным, если на каждом шаге разбиения получаются подсписки B' и В" приблизительно равной длины, и тогда требуется около N*log2(N) шагов. Если список близок к упорядоченному, то требуется около (N*N)/2 шагов. Рекурсивная функция quick упорядочивает участок массива s быстрой сортировкой.
/*   быстрая сортировка     */
double * quick(double *s,int low,int hi)
{ double cnt,aux;
  int i,j;
  if (hi>low)
    { i=low;
      j=hi;
      cnt=s[i];
      while(i < j)
         { if (s[i+1]<=cnt)
            {  s[i]=s[i+1];
               s[i+1]=cnt;
               i++;
             }
           else
            {  if (s[j]<=cnt)
                {  aux=s[j];
                   s[j]=s[i+1];
                   s[i+1]=aux;
                }
                j--;
            }
         }
      quick(s,low,i-1);
      quick(s,i+1,hi);
    }
  return(s);
}
Здесь используются два индекса i и j, проходящие части массива навстречу друг другу (см. рис.). При этом i всегда фиксирует разделяющий элемент cnt=s[low], слева от которого находятся числа, не большие cnt, а справа от i — числа, большие cnt. Возможны три случая: при s[i+1]<=cnt; при s[i+1]>cnt и s[j]<=cnt; при s[i+1]>cnt и s[j]>cnt. По окончании работы i=j, и cnt=s[i] устанавливается на своем месте.
Рис. 1.  Схема быстрой сортировки.
Быстрая сортировка требует дополнительной памяти порядка log2(N) для выполнения рекурсивной функции quick (неявный стек).
Оценка среднего количества действий, необходимых для выполнения быстрой сортировки списка из N различных чисел, получена как оценка отношения числа различных возможных последовательностей из N различных чисел, равного N!, и общего количества действий C(N), необходимых для выполнения быстрой сортировки всех различных последовательностей. Доказано, что C(N)/N! < 2*N*ln(N).