6.比較排序之快速排序

　　快速排序（簡稱快排）因為其效率較高（平均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;    //哨兵i
27             int j = right;    //哨兵j
28             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 -= 1
10             if i < j:
11                 nums[i] = nums[j]
12                 i += 1
13             while i < j and nums[i] < temp:
14                 i += 1
15             if i < j:
16                 nums[j] = nums[i]
17                 j -= 1
18         nums[i] = temp
19         quick_sort(nums, left, i - 1)
20         quick_sort(nums, i + 1, right)
21     
22     return nums
23 
24 nums = [6, 5, 3, 1, 7, 2, 4]
25 nums = quick_sort(nums, 0, len(nums) - 1)
26 print(nums)