c語言快速排序實現(xiàn)方法-創(chuàng)新互聯(lián)

快排

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

實現(xiàn)方式

快排的邏輯其實很簡單，

創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設,平桂企業(yè)網(wǎng)站建設,平桂品牌網(wǎng)站建設,網(wǎng)站定制,平桂網(wǎng)站建設報價,網(wǎng)絡營銷,網(wǎng)絡優(yōu)化,平桂網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學習、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。

遞歸分治

代碼如下：

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;

     //這里的就選擇最左邊的元素作為基準值來操作
     //index表示基準值停留的下標
     int index = partition(array, left, right);

     quickSortIternal(array, left, index - 1);
     quickSortIternal(array, index + 1, right);
}

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

代碼如下：

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);
       }
   }

重點是partition的實現(xiàn)
- 實現(xiàn)方法一： Hoare法
- 使用雙引用的的方式，一個指向區(qū)間的最左邊，一個指向區(qū)間的最右邊，兩個引用向中間遍歷的靠攏
- 如果左引用指向的值小于等于基準值就移動
- 如果右引用指向的值大于等于基準值就移動
- 當左引用遇到大于基準值的數(shù)據(jù)且右引用遇到小于基準值的數(shù)據(jù)時，交換這兩個引用處的數(shù)據(jù)
- 當兩個引用相遇時說明本次partition結束，返回基準值的下標
- 代碼如下：
```
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;
   }
```
- 實現(xiàn)方法二：填坑法
- 同樣需要雙引用，指定一個變量保存基準值，假象基準值的位置是一個“坑”
- 右引用遇到大于等于基準值的數(shù)值就向左移動，直到遇到第一個小于基準值的數(shù)值，將該數(shù)值填到“坑”中，此處的位置是一個新的“坑”
- 開始移動左引用，只有遇到一個大于基準值的數(shù)值時，填到“坑”中
- 直到左引用和右引用相遇時說明只剩最后一個坑了，將基準值填到“坑”中，返回基準值的下標，本次partition結束
- 代碼如下：
```
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;
}
```
- 實現(xiàn)方法三：前后遍歷法
- 同樣是使用雙引用slow和fast，起初同時指向基準值的后一個元素left + 1
- 引用fast向后遍歷，如果遍歷到的數(shù)值大于基準值就向后移動
- 遇到小于基準值的數(shù)值時，交換slow引用和fast引用指向的值，slow向后移動一位
- 始終保證slow之前的值都是小于基準值的數(shù)值，slow和fast之間的是大于等于基準值的數(shù)值，當fast移動到區(qū)間最右端right時，遍歷結束
- 此時show - 1處的數(shù)值為最遍歷結束后最后一個小于基準值的數(shù)值
- 交換left和slow - 1兩位置處的數(shù)值，slow - 1表示下標即是基準值的下標，返回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;
   }
```
基準值的選擇
- 兩邊取其一（左或者右）
- 隨機選擇
- 幾數(shù)取中（例三數(shù)取中：array[left], array[mid], array[right] 大小是中間的為基準值）

性能分析

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

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

分享文章：c語言快速排序實現(xiàn)方法-創(chuàng)新互聯(lián)
文章URL：http://muchs.cn/article30/dcghpo.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、響應式網(wǎng)站、網(wǎng)站收錄、品牌網(wǎng)站設計、網(wǎng)頁設計公司、微信公眾號

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容