快速排序的簡單理解

優質資源分享

詳細描述

快速排序通過一趟排序將待排序列分割成獨立的兩部分，其中一部分序列的關鍵字均比另一部分序列的關鍵字小，則可分別對這兩部分序列繼續進行排序，以達到整個序列有序的目的。

快速排序詳細的執行步驟如下：

1. 從序列中挑出一個元素，稱為 “基准”（pivot）；
2. 重新排序序列，所有比基准值小的元素擺放在基准前面，所有比基准值大的元素擺在基准的後面（相同的數可以到任一邊）。在這個分區退出之後，該基准就處於序列的中間比特置。這個稱為分區（partition）操作；
3. 遞歸地（recursive）把小於基准值元素的子序列和大於基准值元素的子序列排序。

算法圖解

問題解疑

快速排序可以怎樣選擇基准值？

第一種方式：固定比特置選擇基准值；在整個序列已經趨於有序的情况下，效率很低。

第二種方式：隨機選取待排序列中任意一個數作為基准值；當該序列趨於有序時，能够讓效率提高，但在整個序列數全部相等的時候，隨機快排的效率依然很低。

第三種方式：從區間的首、尾、中間，分別取出一個數，然後對比大小，取這 3 個數的中間值作為基准值；這種方式解决了很多特殊的問題，但對於有很多重複值的序列，效果依然不好。

快速排序有什麼好的優化方法？

首先，合理選擇基准值，將固定比特置選擇基准值改成三點取中法，可以解决很多特殊的情况，實現更快地分區。

其次，當待排序序列的長度分割到一定大小後，使用插入排序。對於待排序的序列長度很小或基本趨於有序時，插入排序的效率更好。

在排序後，可以將與基准值相等的數放在一起，在下次分割時可以不考慮這些數。對於解决重複數據較多的情况非常有用。

在實現上，遞歸實現的快速排序在函數尾部有兩次遞歸操作，可以對其使用尾遞歸優化（簡單地說，就是尾比特置調用自身）。

代碼實現

| | package cn.fatedeity.algorithm.sort; |
| | |
| | import java.util.Random; |
| | |
| | /** |
| | * 快速排序算法 |
| | */ |
| | public class QuickSort { |
| | private static void swap(int[] numbers, int src, int target) { |
| | int temp = numbers[src]; |
| | numbers[src] = numbers[target]; |
| | numbers[target] = temp; |
| | } |
| | |
| | private static int[] sort(int[] numbers, int low, int high) { |
| | if (low > high) { |
| | return numbers; |
| | } |
| | // 隨機數取基准值 |
| | Random random = new Random(); |
| | int pivotIndex = random.nextInt(low, high + 1); |
| | int pivot = numbers[pivotIndex]; |
| | swap(numbers, pivotIndex, low); |
| | |
| | int mid = low + 1; |
| | for (int i = low + 1; i <= high; i++) { |
| | if (numbers[i] < pivot) { |
| | swap(numbers, i, mid); |
| | mid++; |
| | } |
| | } |
| | swap(numbers, low, --mid); |
| | sort(numbers, low, mid - 1); |
| | sort(numbers, mid + 1, high); |
| | return numbers; |
| | } |
| | |
| | public static int[] sort(int[] numbers) { |
| | return sort(numbers, 0, numbers.length - 1); |
| | } |
| | } |