人生有涯，學(xué)海無涯
今天跟大家分享一個常用的排序算法——快速排序。我想大家在日常的工作或者面試的時候肯定經(jīng)常會遇到很多排序算法，而且快速排序算法往往是這里面相對更好的排序算法，并且實現(xiàn)也非常簡單。下面我們一起看下吧。
01、快速排序
我們先看看維基百科的解釋:
快速排序（英語：QuickSort），又稱劃分交換排序（partition-exchange sort），簡稱快排，一種排序算法，最早由東尼·霍爾提出。在平均狀況下，排序 n 個項目要 O(nlogn) 次比較。在最壞狀況下則需要 O(n^2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他算法更快，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地達成。
02、算法思想
快速排序的算法思想是分而治之，將一個大的待排序列，分成兩個子序列，然后采用遞歸的方式，依次將子序列也分成更小的子序列，依次進行，最后得到排序好的序列。算法的實現(xiàn)主要分成三步
- 找到基準(zhǔn)點：
- 排列序列，將比基準(zhǔn)點小的放在左邊的子序列，將比基準(zhǔn)點大的放在右邊的子序列；
- 采用遞歸，依次重新選取基準(zhǔn)點，在重復(fù)進行 1，2 步驟，得到最終的順序序列
03、算法實現(xiàn)
/**
* <br>
* <b>Function：</b><br>
* <b>Author：</b>@author 子悠<br>
* <b>Date：</b>2019-09-23 01:07<br>
* <b>Desc：</b>無<br>
*/
public class QuickSort {
public static void main(String[] args) {
int[] array = new int[]{2, 3, 1, 4, 7, 8, 3, 5, 2, 6, 8, 9, 1};
quickSort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
/**
* 遞歸排序
*
* @param array 待排序列
* @param left 左邊起始位置
* @param right 右邊結(jié)束位置
*/
private static void quickSort(int[] array, int left, int right) {
if (left < right) {
//根據(jù)基準(zhǔn)點，找到分隔左右子序列的位置索引
int position = position(array, left, right);
//分別進行左右的遞歸
quickSort(array, left, position - 1);
quickSort(array, position + 1, right);
}
}
/**
* 找到中間
*
* @param array 待排序列
* @param left 左邊起始位置
* @param right 右邊結(jié)束位置
* @return
*/
private static int position(int[] array, int left, int right) {
//找到基準(zhǔn)點, 這里使用的是序列的第一個元素
int base = array[left];
while (left < right) {
while (right > left && array[right] >= base) {
right--;
}
//交互位置
array[left] = array[right];
while (left < right && array[left] <= base) {
left++;
}
//交互位置
array[right] = array[left];
}
//此時 left 與 right 是相等的
array[left] = base;
return left;
}
}
運行結(jié)果：
1 1 2 2 3 3 4 5 6 7 8 8 9
從運行的結(jié)果我們看到，已經(jīng)正常的排序結(jié)束了，說明這個算法已經(jīng)滿足了我們的要求，而且詳細的代碼分析也已經(jīng)加上了注釋，我想大家應(yīng)該都能看懂。只要記住核心的幾個點就可以了，這里我在重復(fù)說明一下：
- 先找基準(zhǔn)點 base；
- 比較大小，比 base 小的放在左邊序列，比 base 大的放在右邊序列；
- 遞歸左右序列。
注意上面內(nèi)部的兩個 while 循環(huán)，這里是使用類似兩個指針，分別從序列的左右兩個端點開始往中間進行遍歷，主要進行的第二步比較和賦值的操作。
