快速排序(QuickSort) 演算法思路詳解
摘要：
最近在學演算法，學到快速排序心得就和大家分享一下。以下程式碼為c做演示，看不懂程式碼不要緊，做參考就好了，主要為了明白快速排序思路。希望能幫助到大家。
快速排序分為4個步驟
找一個基準數（參照數）
從右往左找比基準數小的數與左座標交換
從左往右找比基準數大的數...
最近在學演算法，學到快速排序心得就和大家分享一下。以下程式碼為c做演示，看不懂程式碼不要緊，做參考就好了，主要為了明白快速排序思路。希望能幫助到大家。
快速排序分為4個步驟
- 找一個基準數（參照數）
- 從右往左找比基準數小的數與左座標交換
- 從左往右找比基準數大的數與右座標交換
- 左、右座標相遇時，基準數與相遇座標交換
文字描述已講述完，接下來草稿演示，也可以直接向下翻看程式碼，可能程式碼更有說服力
國足有6名隊員從左到右身高排序球號為： 5號 9號 12號 3號 7號 8號
教練規定左邊第一個最高的為隊長（基準數）：5號
教練要拆分兩個隊：
右邊的球號要小於隊長球號並且左邊球號不能大於右邊找到後和左邊交換位置
-
找到了3號比5號小，與左隊當前座標交換位置
新順序為：3號 9號 12號5號 7號 8號
座標定在第4個人
左邊的球號要大於隊長球號並且左邊球號不能大於右邊
-
找到了9號比5號大，與右隊當前座標交換位置
新順序為：3號5號 12號9號 7號 8號
座標定在第2個人
然後右邊繼續走找比5小的，最後走到了左隊座標位置，兩個相遇相等的座標讓隊長（基準數）放到相遇的位置。排隊完成。最終得到的順序為：
- 3號5號 12號 9號 7號 8號
左隊都是比隊長（5號）球號小的，右邊都是比隊長大的
接下來就要從隊長開始繼續拆分左、右邊和上面教練說的一樣直到不能拆分為止
整個思路基本就這樣，接下來程式碼實現：
#include <stdio.h>
#include <stdlib.h>
int a[101],n;
/**
* 快速排序：
*1.以左邊第一位作為基準數，
*2.先右邊找一個比基準數小的數與左指標所在的位置進行交換
*3.從左邊找一個比基準數大的數與右指標所在的位置進行交換
*4.相遇後則把基準數和左、右指標重合的位置進行交換
*5.重複1/2/3/4操作
* 注意：
*如果左座標大於右座標位置則無法計算，必須左座標小於右座標。
*/
void quicksort(int left, int right){
int i,j,base;
i = left;
j = right;
if (left>right) return ;
// 1.第一步，定義基準數
base = a[left];
// 4.左座標不等於右座標時繼續迭代，等於則相遇
while(left != right){
// 2.如果右邊大於基準數則繼續遞減迭代至小於基準數停止
while(left<right && a[right]>=base)
right--;
// 2.1 與左指標所在位置進行交換
a[left] = a[right];
// 3.如果左邊小於基準數則繼續遞增迭代至大於基準數停止
while(left<right && a[left]<=base)
left++;
// 3.1 與右指標所在位置進行交換
a[right] = a[left];
}
// 4.1 左右座標相遇替換基準數
a[left] = base;
// 5.重複1.2.3.4 遞迴
quicksort(i, left-1); // 重複基準數左邊
quicksort(left+1, j);
return;
}
int main()
{
int i,j;
printf("=============快速排序==============\r\n");
printf("請輸入數量：");
scanf("%d", &n);
for (i=1; i<=n; i++){
scanf("%d", &a[i]);
}
quicksort(1, n);
printf("快速排序結果：\r\n");
for (i=1; i<=n; i++)
printf("%d ", a[i]);
getchar(); getchar();
system("pause");
return 0;
}
本文做為技術參考，也歡迎大神們指導和批評，希望對大家有幫助。