詳解比較排序之快速排序

　　快速排序（簡稱快排）因為其效率較高（平均O(nlogn)）經常在筆試題中對其考查。

　　對於快排的第一步是選取一個“基數”，將會用這個“基數”與其它數進行比較交換。 而這個「基數」的選擇將影響到快排的效率如何，但如果為了選擇基數而選擇基數則會本末倒置。例如為了找到最佳基數，則需要在整個待排序列中找到中位數，但尋找中位數實際上代價又會很高。基數的選擇通常來說就是待排序序列中的第一個物件或中間的物件或最後一個物件。本文以選取第一個元素為例對快排做一個簡要分析實作。

　　以待排序列{6, 5, 3, 1, 7, 2, 4}為例，選取第一個元素6為基數。

　　選擇了基數過後則需要進行和陣列元素進行比較交換，如何進行比較和誰進行比較？ 快排第二步在陣列的第一個元素和最後元素各設定一個「哨兵」。

　　選好基數，設定好哨兵過後，接下來則是開始比較，將基數先與最後一個哨兵j進行比較，如果大於哨兵j則與其進行交換同時哨兵i+1。

　　此時基數不再與哨兵j進行比較，而是與哨兵i進行比較，如果基數大於哨兵i，則哨兵一直向後移，直到大於基數為止交換同時哨兵j-1。

　　重複上面的步驟，基底數再與哨兵j比較。

　　最終結果可見哨兵i的位置=哨兵j的位置，此時將基數賦值給這個位置。

　　這樣就達到了基數6左邊的數字均小於它，右邊的數字均大於它，再利用遞歸對其左右數組進行同樣的步驟選取基數，設置哨兵，最後即可完成排序。

　　Java

#

 1 package com.algorithm.sort.quick; 2  3 import java.util.Arrays; 4  5 /** 6  * 快速排序 7  * Created by yulinfeng on 2017/6/26. 8  */ 9 public class Quick {10     public static void main(String[] args) {11         int[] nums = {6, 5, 3, 1, 7, 2, 4};12         nums = quickSort(nums, 0, nums.length - 1);13         System.out.println(Arrays.toString(nums));14     }15     16     /**17      * 快速排序18      * @param nums 待排序数组序列19      * @param left 数组第一个元素索引20      * @param right 数组最后一个元素索引21      * @return 排好序的数组序列22      */23     private static int[] quickSort(int[] nums, int left, int right) {24         if (left < right) {25             int temp = nums[left];    //基数26             int i = left;    //哨兵i27             int j = right;    //哨兵j28             while (i < j) {29                 while (i < j && nums[j] >= temp) {30                     j--;31                 }32                 if (i < j) {33                     nums[i] = nums[j];34                     i++;35                 }36                 while (i < j && nums[i] < temp) {37                     i++;38                 }39                 while (i < j) {40                     nums[j] = nums[i];41                     j--;42                 }43             }44             nums[i] = temp;45             quickSort(nums, left, i - 1);46             quickSort(nums, i + 1, right);47         }48         return nums;49     }50 }

　　Python3

#

 1 #快速排序 2 def quick_sort(nums, left, right): 3     if left < right: 4         temp = nums[left]    #基数 5         i = left    #哨兵i 6         j = right    #哨兵j 7         while i < j: 8             while i < j and nums[j] >= temp: 9                 j -= 110             if i < j:11                 nums[i] = nums[j]12                 i += 113             while i < j and nums[i] < temp:14                 i += 115             if i < j:16                 nums[j] = nums[i]17                 j -= 118         nums[i] = temp19         quick_sort(nums, left, i - 1)20         quick_sort(nums, i + 1, right)21     22     return nums23 24 nums = [6, 5, 3, 1, 7, 2, 4]25 nums = quick_sort(nums, 0, len(nums) - 1)26 print(nums)

以上是詳解比較排序之快速排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！