【0】README

0）本文旨在給出?快速排序 的 源碼實現和源碼分析（分析它的坑）；

2）要知道 在 元素個數小于10的時候，快速排序不如插入排序；注意快速排序選取樞紐元 時 所使用的方法是 三數中值分割法，截止范圍為10（也就是，如果排序的數組個數小于10， 就不選擇快速排序， 而是選擇其他排序方法， 如希爾排序或插入排序）；（不能再干貨）

3）因為 快速排序是基于分治的，這里通過遞歸實現了分治，每次遞歸后，待排序的元素個數都會減少，所以最后都是通過插入排序來完成排序的；

4）快速排序基礎 參見http://blog.csdn.net/pacosonswjtu/article/details/48879419， 插入排序基礎參見?http://blog.csdn.net/pacosonswjtu/article/details/48879263

Attention）小生的插入排序以 本文中的 插入排序為準，以前寫的都不算數（哈哈），因為我發現這個 版本的插入排序太 tm 靈活了，僅此而已；

5）快速選擇算法（從n個數中選擇第k個最大（小）數），代碼實現在文末；快速選擇算法 基礎知識 參見?http://blog.csdn.net/pacosonswjtu/article/details/48915197

【1】上源碼

#include <stdio.h> #include <malloc.h>#define ElementType intvoid swap(ElementType* a, ElementType* b); ElementType median3(ElementType* array, int left, int right); void quicksort(ElementType* array, int left, int right); void printArray(ElementType* array, int N); void insertionSort(ElementType* array, int left, int right);// swap array arraynd b. void swap(ElementType* array, ElementType* b) {ElementType t;t=*array;*array=*b;*b=t; }// 3數中值分割法 選出 left center right 分別存儲最小，中間，最大值 // 然后 將中位數隱藏到倒數第2個元素 ElementType median3(ElementType* array, int left, int right) { int center = (left+right)/2;if(array[left]>array[center]){swap(&array[left], &array[center]); }if(array[left]>array[right]){swap(&array[left], &array[right]); }if(array[center]>array[right]){swap(&array[center], &array[right]); }/* 將中位數隱藏到倒數第2個元素 */swap(&array[center], &array[right-1]);return array[right-1]; }/* 快速排序 */ void quicksort(ElementType array[], int left, int right) {int i, j;ElementType pivot; // 樞軸.// if(right-left >= 10) { also you can let lower limit be 10.if(right-left >= 3) { /* rihgt-left>=3,才有三數中值分割法的應用 *//* 三數分割 median3 把最大元放入array[right]了，樞紐元放入array[right-1]，最小元放入array[left] */pivot = median3(array, left, right); i = left; //i 指向最小元.j = right-1; // j 指向樞紐元.for(;;) {while(array[++i] < pivot); /* (這里必須++i, 不能i++)找大元素，i停在那里,i起始從 left+1 */while(array[--j] > pivot); /* (這里必須--j, 不能j--)找小元素，j停在那里,j起始從 right-2 */if(i<j){swap(&array[i], &array[j]); /* 分割結束 */}else{break;}}//key: array[i]最后指向大元素，array[right-1]指向樞紐元，將它們交換； swap(&array[i], &array[right-1]); // 交換后, array[i]=樞紐元, 前面的元素小于它, 后面的元素大于它.quicksort(array, left, i-1); /* 遞歸進行快速排序 */quicksort(array, i+1, right); /* 遞歸進行快速排序 */} else /* 當數組長度小于cutoff-隔斷距離的話，那么就采用插入排序，因為這樣效率高些*/{insertionSort(array, left, right);} }// 插入排序 void insertionSort(ElementType* array, int left, int right) {int i, j;ElementType temp; for(i=left+1; i<=right; i++) // 下標i 存儲無序部分的第一個元素，即下標i-1 存儲有序的最后一個元素.{temp = array[i];for(j=i-1; j>=left; j--) // 下標j 初始存儲有序部分的最后一個元素，并在有序部分逆向滑動.{if(temp < array[j]){array[j+1] = array[j];}else{break;}}array[j+1] = temp; // who not array[j]? 因為j--執行后 才推出了循環，所以要加回去.} }/* 打印數組數據 */ void printArray(int* array, int size) {int i;for(i=0; i<size; i++){printf("%d ", array[i]);}printf("\n"); }

#include "p177_quick_sort.h"int main() {ElementType array[] = {34, 8, 64, 51, 32, 21, 64, 8};ElementType array2[] = {34, 8, 64, 51, 32, 21, 64, 8};ElementType array3[] = {34, 8, 64, 51, 32, 21, 64, 8};int size=8; // test for quicksort.printf("\ntest for quicksort towards {34, 8, 64, 51, 32, 21, 64, 8}\n");quicksort(array, 0, size-1);printArray(array, size); // test for median3printf("\ntest for median3 towards {34, 8, 64, 51, 32, 21, 64, 8}\n");median3(array2, 0, size-1);printArray(array2, size);// test for insertionSortprintf("\ntest for insertionSort towards {34, 8, 64, 51, 32, 21, 64, 8}\n");insertionSort(array3, 0, size-1);printArray(array3, size); }

【2】review 插入排序代碼實現（注意我的輸入參數，可能和他家的不一樣）

1）參數分析：這個插入排序的源碼荔枝 比較靈活，因為輸入參數可變，不一定非得認為 left==0，還可以對其子數組進行插入排序；

// 插入排序 void insertionSort(ElementType* array, int left, int right) {int i, j;ElementType temp; for(i=left+1; i<=right; i++) // 下標i 存儲無序部分的第一個元素，即下標i-1 存儲有序的最后一個元素.{temp = array[i];for(j=i-1; j>=left; j--) // 下標j 初始存儲有序部分的最后一個元素，并在有序部分逆向滑動.{if(temp < array[j]){array[j+1] = array[j];}else{break;}}array[j+1] = temp; // who not array[j]? 因為j--執行后 才推出了循環，所以要加回去.} }

【3】快速選擇算法

1）intro：快速選擇算法是從n個數中選擇第k個最大（小）數算法，且是快速排序的變體算法，因為快速排序基于遞歸的分治算法，每輪遞歸后，都可以確定樞紐元的最終下標位置；所以通過 k 次 快速排序就可以確定 第k 個 最大（小）元素了，而不用對所有 元素進行排序；

2）當元素個數小于10（官方建議取10，不過這里的測試用例取3）的時候：快速排序依然會用到插入排序；

3）快速選擇算法分析：快速選擇算法 是 快速排序的變體算法，基本的idea是一樣的，只不過 快速選擇函數 多帶了一個輸入參數 k值，且在函數末尾要比較 i（因為 array[i] 存儲著樞紐值） 和 k的大小以此來確定 該在哪個 數組范圍內遞歸進行快速選擇，代碼如下：

#include <stdio.h> #include <malloc.h>#define ElementType int #define Error(str) printf("\nerror: %s", str)void swap(ElementType* a, ElementType* b); ElementType median3(ElementType* array, int left, int right); void quickselect(ElementType* array, int left, int right, int k); void printArray(ElementType* array, int N); void insertionSort(ElementType* array, int left, int right);// swap array arraynd b. void swap(ElementType* array, ElementType* b) {ElementType t;t=*array;*array=*b;*b=t; }// 3數中值分割法 選出 left center right 分別存儲最小，中間，最大值 // 然后 將中位數隱藏到倒數第2個元素 ElementType median3(ElementType* array, int left, int right) { int center = (left+right)/2;if(array[left]>array[center]){swap(&array[left], &array[center]); }if(array[left]>array[right]){swap(&array[left], &array[right]); }if(array[center]>array[right]){swap(&array[center], &array[right]); }/* 將中位數隱藏到倒數第2個元素 */swap(&array[center], &array[right-1]);return array[right-1]; }/* 快速選擇(第k+1個最大元素), 所以如果要選擇第k個最大元素，main函數需要傳入k-1 */ void quickselect(ElementType array[], int left, int right, int k) {int i, j;ElementType pivot; // 樞軸.if(k>right){Error("failed quickselect() for k is greater than right.");return;}// if(right-left >= 10) { also you can let lower limit be 10.if(right-left >= 3) { /* rihgt-left>=3,才有三數中值分割法的應用 *//* 三數分割 median3 把最大元放入array[right]了，樞紐元放入array[right-1]，最小元放入array[left] */pivot = median3(array, left, right); i = left; //i 指向最小元.j = right-1; // j 指向樞紐元.for(;;) {while(array[++i] < pivot); /* (這里必須++i, 不能i++)找大元素，i停在那里,i起始從 left+1 */while(array[--j] > pivot); /* (這里必須--j, 不能j--)找小元素，j停在那里,j起始從 right-2 */if(i<j){swap(&array[i], &array[j]); /* 分割結束 */}else{break;}}//key: array[i]最后指向大元素，array[right-1]指向樞紐元，將它們交換； swap(&array[i], &array[right-1]); // 交換后, array[i]=樞紐元, 前面的元素小于它, 后面的元素大于它.// 上面的代碼和快速排序一樣，下面的代碼用于基于遞歸的快速選擇if(k > i) {quickselect(array, i+1, right, k); }else if(k < i){quickselect(array, left, i-1, k); }// else k == i, bingo. } else /* 當數組長度小于3(10)的話，那么就采用插入排序，因為這樣效率高些*/{insertionSort(array, left, right);} }// 插入排序 void insertionSort(ElementType* array, int left, int right) {int i, j;ElementType temp; for(i=left+1; i<=right; i++) // 下標i 存儲無序部分的第一個元素，即下標i-1 存儲有序的最后一個元素.{temp = array[i];for(j=i-1; j>=left; j--) // 下標j 初始存儲有序部分的最后一個元素，并在有序部分逆向滑動.{if(temp < array[j]){array[j+1] = array[j];}else{break;}}array[j+1] = temp; // who not array[j]? 因為j--執行后 才推出了循環，所以要加回去.} }/* 打印數組數據 */ void printArray(int* array, int size) {int i;for(i=0; i<size; i++){printf("%d ", array[i]);}printf("\n"); } #include "p185_quick_select.h"int main() {ElementType array[] = {34, 8, 64, 51, 32, 21, 64, 8,35, 9, 65, 50, 31, 20, 63, 8}; int size=16; int k = 6;// test for quickselect.printf("\ntest for quickselect towards {34, 8, 64, 51, 32, 21, 64, 8, 35, 9, 65, 50, 31, 20, 63, 8}\n");quickselect(array, 0, size-1, k-1); // pass k-1 not k, you know it.printf("\nthe %dth maximum element is %d \n", k, array[k-1]); }

總結

以上是生活随笔為你收集整理的ReviewForJob——快速排序（基于插入排序）+快速选择（快速排序变体）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。