c語言快速排序?qū)崿F(xiàn)方法

• 快排

• 原理：
  • 從待排序區(qū)間選擇一個(gè)數(shù)，作為基準(zhǔn)值(pivot)
  • Partition: 遍歷整個(gè)待排序區(qū)間，將比基準(zhǔn)值小的（可以包含相等的）放到基準(zhǔn)值的左邊，將比基準(zhǔn)值大的（可以包含相等的）放到基準(zhǔn)值的右邊
  • 采用分治思想，對(duì)左右兩個(gè)小區(qū)間按照同樣的方式處理，直到小區(qū)間的長度等于1，代表已經(jīng)有序，或者小區(qū)間的長度等于0，代表沒有數(shù)據(jù)。
• 快排是一個(gè)不穩(wěn)定的排序

實(shí)現(xiàn)方式

1. 快排的邏輯其實(shí)很簡(jiǎn)單，

   • 遞歸分治

   • 代碼如下：

     public static void quickSort(int[] array) {
             //待排序區(qū)間為[0, array.length - 1]
             quickSortIternal(array, 0, array.length - 1);
     }
     
     private static void quickSortIternal(int[] array, int left, int right) {
             if(left >= right)
                     return;
     
             //這里的就選擇最左邊的元素作為基準(zhǔn)值來操作
             //index表示基準(zhǔn)值停留的下標(biāo)
             int index = partition(array, left, right);
     
             quickSortIternal(array, left, index - 1);
             quickSortIternal(array, index + 1, right);
     }

   • 非遞歸分治
   • 通過使用棧實(shí)現(xiàn)，將數(shù)組的左右下標(biāo)放入棧中
   • 每次取出判斷l(xiāng)eft和right的關(guān)系，如果left >= right 表示該小區(qū)間排序完畢
   • 存入每個(gè)區(qū)間的左右兩下標(biāo)，依次循環(huán)，當(dāng)棧為空時(shí)，表示排序結(jié)束

   • 代碼如下：

     public static void quickSort2(int[] array) {
                 Stack<Integer> stack = new Stack<>();
                 stack.push(array.length - 1);
                 stack.push(0);
     
                 while(!stack.isEmpty()) {
                         int left = stack.pop();
                         int right = stack.pop();
     
                         if(left >= right) {
                                 continue;
                         }
     
                         int index = partition(array, left, right);
     
                         stack.push(right);
                         stack.push(index + 1);
     
                         stack.push(index - 1);
                         stack.push(left);
                 }
         }

2. 重點(diǎn)是partition的實(shí)現(xiàn)

   • 實(shí)現(xiàn)方法一： Hoare法
   • 使用雙引用的的方式，一個(gè)指向區(qū)間的最左邊，一個(gè)指向區(qū)間的最右邊，兩個(gè)引用向中間遍歷的靠攏
   • 如果左引用指向的值小于等于基準(zhǔn)值就移動(dòng)
   • 如果右引用指向的值大于等于基準(zhǔn)值就移動(dòng)
   • 當(dāng)左引用遇到大于基準(zhǔn)值的數(shù)據(jù)且右引用遇到小于基準(zhǔn)值的數(shù)據(jù)時(shí)，交換這兩個(gè)引用處的數(shù)據(jù)
   • 當(dāng)兩個(gè)引用相遇時(shí)說明本次partition結(jié)束，返回基準(zhǔn)值的下標(biāo)

   • 代碼如下：

     public int partition(int[] array, int left, int right) {
                 int pivot = array[left];
                 int l = left;
                 int r = right;
     
                 while(l < r) {
                         while(l < r && array[r] >= pivot) {
                                 r--;
                         }
                         while(l < r && array[l] <= pivot) {
                                 l++;
                         }
                         swap(array, l, r);
                 }
                 swap(array, left, l);
                 return l;
         }
     
         private static void swap(int[] array, int i, int j) {
                 int tmp = array[i];
                 array[i] = array[j];
                 array[j] = tmp;
         }

   • 實(shí)現(xiàn)方法二：填坑法
   • 同樣需要雙引用，指定一個(gè)變量保存基準(zhǔn)值，假象基準(zhǔn)值的位置是一個(gè)“坑”
   • 右引用遇到大于等于基準(zhǔn)值的數(shù)值就向左移動(dòng)，直到遇到第一個(gè)小于基準(zhǔn)值的數(shù)值，將該數(shù)值填到“坑”中，此處的位置是一個(gè)新的“坑”
   • 開始移動(dòng)左引用，只有遇到一個(gè)大于基準(zhǔn)值的數(shù)值時(shí)，填到“坑”中
   • 直到左引用和右引用相遇時(shí)說明只剩最后一個(gè)坑了，將基準(zhǔn)值填到“坑”中，返回基準(zhǔn)值的下標(biāo)，本次partition結(jié)束

   • 代碼如下：

     public int partition(int[] array, int left, int right) {
         int pivot = array[left];
         int l = left;
         int r = right;
     
         while(l < r) {
                 while(l < r && array[r] >= pivot) {
                         r--;
                 }
                 array[l] = array[r];
                 while(l < r && array[l] <= pivot) {
                         l++;
                 }
                 array[r] = array[l];
         }
         array[l] = pivot;
         return l;
     }

   • 實(shí)現(xiàn)方法三：前后遍歷法
   • 同樣是使用雙引用slow和fast，起初同時(shí)指向基準(zhǔn)值的后一個(gè)元素left + 1
   • 引用fast向后遍歷，如果遍歷到的數(shù)值大于基準(zhǔn)值就向后移動(dòng)
   • 遇到小于基準(zhǔn)值的數(shù)值時(shí)，交換slow引用和fast引用指向的值，slow向后移動(dòng)一位
   • 始終保證slow之前的值都是小于基準(zhǔn)值的數(shù)值，slow和fast之間的是大于等于基準(zhǔn)值的數(shù)值，當(dāng)fast移動(dòng)到區(qū)間最右端right時(shí)，遍歷結(jié)束
   • 此時(shí)show - 1處的數(shù)值為最遍歷結(jié)束后最后一個(gè)小于基準(zhǔn)值的數(shù)值
   • 交換left和slow - 1兩位置處的數(shù)值，slow - 1表示下標(biāo)即是基準(zhǔn)值的下標(biāo)，返回slow - 1

   • 代碼如下：

     private int partition(int[] array, int left, int right) {
                 int pivot = array[left];
                 int slow = left + 1;
                 int fast = left + 1;
     
                 while(fast <= right) {
                         if(array[fast] < pivot) {
                                 swap(array, slow, fast);
                                 slow++;
                         }
                         fast++;
                 }
                 swap(array, left, slow - 1);
                 return slow - 1;
         }

3. 基準(zhǔn)值的選擇
   • 兩邊取其一（左或者右）
   • 隨機(jī)選擇
   • 幾數(shù)取中（例三數(shù)取中：array[left], array[mid], array[right] 大小是中間的為基準(zhǔn)值 ）

性能分析

• 時(shí)間復(fù)雜度：
  • 最好的情況：O(N*logN)
  • 平均情況：O(N*logN)
  • 最壞的情況：O(N^2)
• 空間復(fù)雜度：O(1)
  • 最好的情況：O(logN)
  • 平均情況：O(logN)
  • 最壞的情況：O(N)
• 穩(wěn)定性：不穩(wěn)定