這是基本都一樣的部分。 [cpp] void print_arr(int *arr, int n) { int i; for (i = 0; i < n; i++) { if (!i) { printf("%d", arr[i]); } else { printf(" %d", arr[i]); } } printf("\n"); } void sort(int * arr, int start, int end){ if(end < start) return; int index = quik_sort(arr, start, end); sort(arr, start, index-1); sort(arr,index +1,end); } int main() { //cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!! int n = 6; int max = 10; int * arr = (int *) malloc(sizeof(int) * n); srand(time(0)); //cout << time(0) << endl; for (int i = 0; i < n; i++) { arr[i] = rand() % max; } print_arr(arr, n); sort(arr, 0, n-1); print_arr(arr, n); return 0; } 先說非隨機化算法： 方法1： 從兩邊向中間，不符合要求就交換。 [cpp] int quik_sort(int * arr, int start, int end) { int i = start; int j = end + 1; int x = arr[start]; while(true){ //這裡是 "++i" while(arr[++i] < x);//從後向前找到第一個比 基准（x）小的數。 i指向該數 //--j 所以要在前面 j=end+1 while(arr[--j] > x);//從前到後 第一個比 基准（x）大的數。 j指向該數 if(i >= j) break; //進行交換操作 int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } arr[start] = arr[j]; arr[j] = x; //print_arr(arr, 6); //cout << start << " - " << end << " j=" << j << endl; return j; } 方法2： 第一次交換：swap(arr,index,end); 是交換最後一個值和最後一個值。（遍歷樹從start -> end-1），也可以說是讓arr[end]暫存基准值，循環結束後在交換過來。 第二次交換：swap(arr,index++,i); 保證較小的值在前面 地三次交換：swap(arr, end, index); 當期循環結束的時候，index指向的中間的某個位置（值的是基准值應該在的位置），此時arr[index] 是大於或等於基准值的，可以和arr[end]（基准值進行交換） 這個算法可以從前向後遍歷，也可以從後向前遍歷。 index指向的數可以理解為一個待與後面比基准（pivot）交換的數（i指向的數始終比pivot小，要交換到前面），可以比pivot小（就是index==i,就和自身交換，index++）或大（不交換，index不變）。 [cpp] int quik_sort(int * arr, int start, int end) { int index = start; int pivot = arr[index]; swap(arr,index,end); for(int i=start; i<end ; i++){ if(arr[i] < pivot){ swap(arr,index++,i); } } swap(arr, end, index); return index; } 方法3：只有一個quick_sort方法，遞歸調用自身。其實也就是從兩邊向中間靠攏。 但是這裡每次不是進行兩個值的交換，而是把一個值賦值給另一個。 （key始終保存著基准值，即空出來一個位置，可以原地排序。） 這個是我認為相對前兩種較好的！因為不會太多的交換操作。 [cpp] void quick_sort(int * arr, int start, int end){ if(end < start) return; int i,j,key; i = start; j = end; key = arr[i]; while(i < j){ while (i < j && arr[j] > key) j--; if (i < j) arr[i++] = arr[j]; while (i < j && arr[i] < key) i++; if (i < j) arr[j--] = arr[i]; } arr[i] = key; if(start < i-1) quick_sort(arr, start, i-1); if(end > i+1) quick_sort(arr, i+1, end); } 隨機化算法： 隨機化的好處就是防止出現最壞的情況。 Java版的，其實很簡單，就是取一個隨機數。 [java] www.2cto.com private static <E> int partition(E[] array, int begin, int end, Comparator<? super E> cmp) { int index = begin + RND.nextInt(end - begin + 1); E pivot = array[index]; swap(array, index, end); for (int i = index = begin; i < end; ++ i) { if (cmp.compare(array[i], pivot) <= 0) { swap(array, index++, i); } } swap(array, index, end); return (index); }
