基礎的快排演算法是很常用且效率高的排序演算法，而且在一些面試和考試中也用得到，故在嘗試實作基礎的快排演算法后寫下此文，
1、整體代碼（主要根據演算法導論的快排章節的思想）：
#include <stdio.h>
#include <stdlib.h>
#define M 15
void QuickSort(int A[],int p,int r);//遞回實作的主程式
int PARTITION(int A[],int p,int r);//區域排序的函式
int main(){
int i = 0;
int a[M] = {3,9,1,6,5,98,15,47,11,24,35,12,4,78,36};
printf("start: ");
for(i = 0;i<M;i++){
printf("%3d",a[i]);
}
printf("\n");
QuickSort(a,0,M-1);
printf("end : ");
for(i = 0;i<M;i++){
printf("%3d",a[i]);
}
return 0;
}
void QuickSort(int A[],int p,int r){
int q = 0;
if(p < r){
q = PARTITION(A,p,r);
//遞回實作子串排序
QuickSort(A,p,q-1);
QuickSort(A,q+1,r);
}
}
int PARTITION(int A[],int p,int r){
int x = A[r];//選定標記位（這邊是選定了需要排序的最后一位）
int i = p-1,j=p,temp;
for(j = p;j < r;j++){
//將小于標記位的數字與前面的數字進行交換，這樣使得陣列前面變成小于標記位的數字
if(A[j] <= x){
i++;
temp = A[j];
A[j] = A[i];
A[i] = temp;
}
}
//最后把標記位數字（這里是選定了最后一位）與前面大于標記位的數字進行交換（不存在大于的話就是和自己交換）
temp = A[r];
A[r] = A[i+1];
A[i+1] = temp;
return i+1;//回傳當前標記位數字的位置
}
執行結果：
start: 3 9 1 6 5 98 15 47 11 24 35 12 4 78 36
end : 1 3 4 5 6 9 11 12 15 24 35 36 47 78 98
2、主要思路
快速排序（Quicksort）是對冒泡排序的一種改進，大多通過遞回實作，是一種不穩定的排序演算法，
主要思路是根據分治法的原則，把一整串資料拆分多次，實作大事化小從而進行排序，
具體的思想為，從一串資料中選定一個標志資料，在一次排序之中，使其前面的數字都比起小，后面的數字都比其大，并對前面的數字串和后面的數字串執行程式，反復直至確定所有元素的位置，
3、不穩定性的理解
從思想中可以看出，每呼叫一次區域排序的函式，就有一個元素確定位置，因為遞回的緣故，所以平均時間復雜度O(nlogn)，且是一種不穩定的演算法
因為對于相同的數字，如果把后面的數字作為標記，前面的數字判定為<=,后面的數字就應該與前面的數字交換位置，導致數字順序顛倒成為不穩定的排序，（這里可能有人會想，如果相等不交換不就是變成穩定的了? 很遺憾，并不可以，如果相等的值不觸發交換，那么就可能出現標記數前后都有與標記數等值的數字，那么排序就失敗了）
一個例子（標紅的6本來在后面）
3 9 1 6 6
經過排序后
3 1 6 9 6
4、對遞回的理解
我給區域函式加了一個輸出，就是每次呼叫函式時輸出排序的數字在陣列的位置，這樣便于理解遞回的呼叫，
void QuickSort(int A[],int p,int r){ int q = 0; if(p < r){ q = PARTITION(A,p,r); QuickSort(A,p,q-1); QuickSort(A,q+1,r); } }int PARTITION(int A[],int p,int r){
int x = A[r];
int i = p-1,j=p,temp;
for(j = p;j < r;j++){
if(A[j] <= x){
i++;
temp = A[j];
A[j] = A[i];
A[i] = temp;
}
}
temp = A[r];
A[r] = A[i+1];
A[i+1] = temp;
//添加的簡單輸出
printf("(%2d-%2d)",p,r);
for(j = p;j<=r;j++){
printf("%3d",A[j]);
}
printf("\n");
return i+1;
}
輸出：
start: 3 9 1 6 5 98 15 47 11 24 35 12 4 78 36
( 0-14) 3 9 1 6 5 15 11 24 35 12 4 36 98 78 47
( 0-10) 3 1 4 6 5 15 11 24 35 12 9
( 0- 1) 1 3
( 3-10) 6 5 9 11 24 35 12 15
( 3- 4) 5 6
( 6-10) 11 12 15 24 35
( 6- 7) 11 12
( 9-10) 24 35
(12-14) 47 78 98
(13-14) 78 98
end : 1 3 4 5 6 9 11 12 15 24 35 36 47 78 98
遞回的呼叫就是呼叫一個函式的時候，又再次呼叫自己，函式并未結束，再次呼叫的函式又會呼叫自己，直到達到結束標記，
以第一次排序為例子，先選定36位標記數，排序后再對左邊0-10進行排序
選定4為標記數，排序再對左邊0-1進行排序，此時左邊結束，進行右邊3-10排序，以此類推，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/53371.html
標籤：其他
上一篇：Untiy 打包LightMap 報錯:Inconsistent asset when sorting preload assets: '' fileID: 0