基本思想：
1）選擇一個(gè)基準(zhǔn)元素，通常選擇第一個(gè)元素或者最后一個(gè)元素。
2）通過一趟排序?qū)⒋判虻挠涗浄指畛瑟?dú)立的兩部分速妖，其中一部分記錄的元素值均比基準(zhǔn)元素值小沥匈；另一部分記錄的元素值均比基準(zhǔn)值大蔗喂。
3）此時(shí)基準(zhǔn)元素在其排好序后的正確位置
4）然后分別對這兩部分記錄用同樣的方法繼續(xù)進(jìn)行排序，直到整個(gè)序列有序高帖。
算法的實(shí)現(xiàn)：
// 輸出數(shù)組內(nèi)容
void print(int array[], int length, int i) {
printf("privot=%d:",i);
for (int j = 0; j < length; j++) {
printf(" %d ", array[j]);
}
printf("\n");
}
// 交換兩個(gè)數(shù)據(jù)的位置
void swap(int *num1, int *num2) {
int temp = *num1;
*num1 = *num2;
*num2 = temp;
}
// 將數(shù)組分割成獨(dú)立的兩部分
int partition(int array[], int low, int high) {
int privotKey = array[low]; // 基準(zhǔn)元素
while (low < high) { // 從表的兩端交替地向中間掃描
while (low < high && array[high] >= privotKey) {
-- high; // 從 high 所指位置向前搜索缰儿，至多到 low+1 位置。將比基準(zhǔn)元素小的交換到前端
}
swap(&array[low], &array[high]);
while (low < high && array[low] <= privotKey) {
++ low; // 從 low 所指位置向后搜索散址，至多到 high-1 位置乖阵。將比基準(zhǔn)元素大的交換到后端
}
swap(&array[low], &array[high]);
}
print(array, 8, low);
return low;
}
// 快速排序（Quick Sort）
void quickSort(int array[], int low, int high) {
if (low < high) {
int privotLoc = partition(array, low, high); // 將表一分為二
quickSort(array, low, privotLoc - 1); // 遞歸對低子表遞歸排序
quickSort(array, privotLoc + 1, high); // 遞歸對高子表遞歸排序
}
}
int main(int argc, const char * argv[]) {
int arrayQuickSort[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
quickSort(arrayQuickSort, 0, 7);
printf("\n");
return 0;
}
快速排序的改進(jìn)
快速排序是通常被認(rèn)為在同數(shù)量級（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時(shí)预麸，快排序反而蛻化為冒泡排序瞪浸。為改進(jìn)之，通常以“三者取中法”來選取基準(zhǔn)記錄吏祸，即將排序區(qū)間的兩個(gè)端點(diǎn)與中點(diǎn)三個(gè)記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄对蒲。快速排序是一個(gè)不穩(wěn)定的排序方法贡翘。
在本改進(jìn)算法中蹈矮，只對長度大于k的子序列遞歸調(diào)用快速排序，讓原序列基本有序鸣驱，然后再對整個(gè)基本有序序列用插入排序算法排序泛鸟。實(shí)踐證明，改進(jìn)后的算法時(shí)間復(fù)雜度有所降低踊东，且當(dāng)k取值為 8 左右時(shí)北滥，改進(jìn)算法的性能最佳刚操。
// 輸出數(shù)組內(nèi)容
void print(int array[], int length, int i) {
printf("privot=%d:",i);
for (int j = 0; j < length; j++) {
printf(" %d ", array[j]);
}
printf("\n");
}
// 交換兩個(gè)數(shù)據(jù)的位置
void swap(int *num1, int *num2) {
int temp = *num1;
*num1 = *num2;
*num2 = temp;
}
// 將數(shù)組分割成獨(dú)立的兩部分
int partition(int array[], int low, int high) {
int privotKey = array[low]; // 基準(zhǔn)元素
while (low < high) { // 從表的兩端交替地向中間掃描
while (low < high && array[high] >= privotKey) {
-- high; // 從 high 所指位置向前搜索，至多到 low+1 位置碑韵。將比基準(zhǔn)元素小的交換到前端
}
swap(&array[low], &array[high]);
while (low < high && array[low] <= privotKey) {
++ low; // 從 low 所指位置向后搜索赡茸，至多到 high-1 位置。將比基準(zhǔn)元素大的交換到后端
}
swap(&array[low], &array[high]);
}
print(array, 8, low);
return low;
}
// 快速排序改進(jìn)（Quick Sort）
void quickSortImprove(int array[], int low, int high, int k) {
if (high - low > k) { // 長度大于k時(shí)遞歸祝闻，k為指定數(shù)
int privotLoc = partition(array, low, high);
quickSortImprove(array, low, privotLoc - 1, k);
quickSortImprove(array, privotLoc + 1, high, k);
}
}
// 快速排序改進(jìn)（Quick Sort）
void quickSort(int array[], int low, int high, int k) {
quickSortImprove(array, low, high, k); // 先調(diào)用改進(jìn)算法占卧，使之基本有序
// 再用插入排序?qū)居行蛐蛄信判? for (int i = 1; i <= high; i ++) {
int j = i - 1;
int sentry = array[i]; // 復(fù)制為哨兵，即存儲待排序元素
while (j >= 0 && sentry < array[j]) { // 查找在有序表的插入位置
array[j+1] = array[j];
j--; // 元素后移
}
array[j+1] = sentry; // 插入到正確位置
}
}
int main(int argc, const char * argv[]) {
int arrayQuickSort[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
quickSort(arrayQuickSort, 0, 7, 4);
print(arrayQuickSort, 8, 0);
printf("\n");
return 0;
}
總結(jié)
快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法联喘，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)华蜒，快速排序的平均時(shí)間最短。
