• 快排

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

實現(xiàn)方式

1. 快排的邏輯其實很簡單，

   

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

   • 代碼如下：

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

2. 重點是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;
        }

3. 基準值的選擇
   • 兩邊取其一（左或者右）
   • 隨機選擇
   • 幾數(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，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

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

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

廣告

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