快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項(xiàng)目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來。

快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。

快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。

（1）定義

快速排序由C. A. R. Hoare在1962年提出?？焖倥判蚴菍γ芭菖判虻囊环N改進(jìn)，采用了一種分治的策略。

（2）基本思想

通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。

（3）步驟

1. 先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)。

2. 分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。

3. 再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)。

（4）動圖演示

（5）C語言代碼實(shí)現(xiàn)如下：

/*****************************************************
File name：Quicksort
Author：Zhengqijun  Version:1.0  Date: 2016/11/04
Description: 對數(shù)組進(jìn)行快速排序
Funcion List: 實(shí)現(xiàn)快速排序算法
*****************************************************/
 
#include <stdio.h>
#include <stdlib.h>
 
#define BUF_SIZE 10
 
/**************************************************
 *函數(shù)名：display
 *作用：打印數(shù)組元素
 *參數(shù)：array - 打印的數(shù)組，maxlen - 數(shù)組元素個數(shù)
 *返回值：無
 **************************************************/
void display(int array[], int maxlen)
{
  int i;
 
  for(i = 0; i < maxlen; i++)
  {
    printf("%-3d", array[i]);
  }
  printf("\n");
 
  return ;
}
 
/********************************
 *函數(shù)名：swap
 *作用：交換兩個數(shù)的值
 *參數(shù)：交換的兩個數(shù)
 *返回值：無
 ********************************/
void swap(int *a, int *b) 
{
  int temp;
 
  temp = *a;
  *a = *b;
  *b = temp;
 
  return ;
}
 
/************************************
 *函數(shù)名：quicksort
 *作用：快速排序算法
 *參數(shù)：
 *返回值：無
 ************************************/
void quicksort(int array[], int maxlen, int begin, int end)
{
  int i, j;
 
  if(begin < end)
  {
    i = begin + 1; // 將array[begin]作為基準(zhǔn)數(shù)，因此從array[begin+1]開始與基準(zhǔn)數(shù)比較！
    j = end;    // array[end]是數(shù)組的最后一位
     
    while(i < j)
    {
      if(array[i] > array[begin]) // 如果比較的數(shù)組元素大于基準(zhǔn)數(shù)，則交換位置。
      {
        swap(&array[i], &array[j]); // 交換兩個數(shù)
        j--;
      }
      else
      {
        i++; // 將數(shù)組向后移一位，繼續(xù)與基準(zhǔn)數(shù)比較。
      }
    }
 
    /* 跳出while循環(huán)后，i = j。
     * 此時數(shù)組被分割成兩個部分 --> array[begin+1] ~ array[i-1] < array[begin]
     *              --> array[i+1] ~ array[end] > array[begin]
     * 這個時候?qū)?shù)組array分成兩個部分，再將array[i]與array[begin]進(jìn)行比較，決定array[i]的位置。
     * 最后將array[i]與array[begin]交換，進(jìn)行兩個分割部分的排序！以此類推，直到最后i = j不滿足條件就退出！
     */
 
    if(array[i] >= array[begin]) // 這里必須要取等“>=”，否則數(shù)組元素由相同的值時，會出現(xiàn)錯誤！
    {
      i--;
    }
 
    swap(&array[begin], &array[i]); // 交換array[i]與array[begin]
    
    quicksort(array, maxlen, begin, i);
    quicksort(array, maxlen, j, end);
  }
}
 
// 主函數(shù)
int main()
{
  int n;
  int array[BUF_SIZE] = {12,85,25,16,34,23,49,95,17,61};
  int maxlen = BUF_SIZE;
  
  printf("排序前的數(shù)組\n");
  display(array, maxlen);
  
  quicksort(array, maxlen, 0, maxlen-1); // 快速排序
  
  printf("排序后的數(shù)組\n");
  display(array, maxlen);
  
  return 0;
}

如果我們編譯并運(yùn)行上述程序，那么它應(yīng)該產(chǎn)生以下結(jié)果：

排序前的數(shù)組
12 85 25 16 34 23 49 95 17 61 
排序后的數(shù)組
12 16 17 23 25 34 49 61 85 95