C/C++：Quick Sort

以下文章取自：這裡

先說明這個快速排序法的概念，它以最右邊的值s作比較的標準，將整個數列分為三個部份，一個是小於s的部份，一個是大於s的部份，一個是未處理的部份，如下所示 ：


在排序的過程中，i 與 j 都會不斷的往右進行比較與交換，最後數列會變為以下的狀態：


然後將s的值置於中間，接下來就以相同的步驟會左右兩邊的數列進行排序的動作，如下所示：


一個實際例子的演算如下所示：


範例程式：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}

int partition(int number[], int left, int right)
{
  int i, j, s;
  s = number[right];
  i = left - 1;

  for(j = left; j < right; j++)
  {
    if(number[j] <= s)
    {
      i++;
      SWAP(number[i], number[j]); 
    }
  }

  SWAP(number[i+1], number[right]);
  return i+1;
}

void quicksort(int number[], int left, int right)
{ 
  int q;

  if(left < right)
  {
    q = partition(number, left, right);
    quicksort(number, left, q-1);
    quicksort(number, q+1, right);
  }
}

int main(void)
{
  int number[MAX] = {0};
  int i, num;
  srand(time(NULL));  //或用srand(clock(NULL));
  printf("排序前：");
  for(i = 0; i < MAX; i++)
  {
    number[i] = rand()%100+1;  //產生1~100亂數
    printf("%d ", number[i]);
  }
  quicksort(number, 0, MAX-1);
  printf("\n排序後：");
  for(i = 0; i < MAX; i++)
    printf("%d ", number[i]);
  printf("\n");
  return 0;
}

輸出結果：
排序前：56 13 24 96 18 91 44 99 79 72
排序後：13 18 24 44 56 72 79 91 96 99