快速排序(英語：Quicksort)，又稱劃分交換排序，簡稱快排，一種排序演算法，最早由東尼·霍爾提出。在平均狀況下，排序 n 個項目要 O(n log n) 次比較。在最壞狀況下則需要O(n2) 次比較，但這種狀況並不常見。事實上，快速排序O(n log n) 通常明顯比其他演算法更快，因為它的內部循環可以在大部分的架構上很有效率地達成。
快速排序步驟為：
1.從數列中挑出一個元素，稱為"基準"。
2.重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面(相同的數可以到任何一邊)。在這個分區結束之後，該基準就處於數列的中間位置。這個稱為分區操作。
3.遞歸地把小於基準值元素的子數列和大於基準值元素的子數列排序。
4.遞歸到最底部時，數列的大小是零或一，也就是已經排序好了。這個演算法一定會結束，因為在每次的迭代中，它至少會把一個元素擺到它最後的位置去。
從上面的過程中可以看到:
①先從隊尾開始向前掃描且當low < high時,如果a[high] > tmp,則high–,但如果a[high] < tmp,則將high的值賦值給low,即arr[low] = a[high],同時要轉換數組掃描的方式,即需要從隊首開始向隊尾進行掃描了。 ②同理,當從隊首開始向隊尾進行掃描時,如果a[low] < tmp,則low++,但如果a[low] > tmp了,則就需要將low位置的值賦值給high位置,即arr[low] = arr[high],同時將數組掃描方式換為由隊尾向隊首進行掃描。
③不斷重複①和②,知道low>=high時(其實是low=high),low或high的位置就是該基準數據在數組中的正確索引位置。
按照上訴理論的代碼如下:
package com.nrsc.sort;
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
quickSort(arr, 0, arr.length - 1);
System.out.println("排序後:");
for (int i : arr) {
System.out.println(i);
}
}
private static void quickSort(int[] arr, int low, int high) {
if (low < high) { // 找尋基準數據的正確索引 int index = getIndex(arr, low, high); // 進行迭代對index之前和之後的數組進行相同的操作使整個數組變成有序 quickSort(arr, 0, index - 1); quickSort(arr, index + 1, high); } } private static int getIndex(int[] arr, int low, int high) { // 基準數據 int tmp = arr[low]; while (low < high) { // 當隊尾的元素大於等於基準數據時,向前挪動high指針 while (low < high && arr[high] >= tmp) {
high--;
}
// 如果隊尾元素小於tmp了,需要將其賦值給low
arr[low] = arr[high];
// 當隊首元素小於等於tmp時,向前挪動low指針
while (low < high && arr[low] <= tmp) { low++; } // 當隊首元素大於tmp時,需要將其賦值給high arr[high] = arr[low]; } // 跳出循環時low和high相等,此時的low或high就是tmp的正確索引位置 // 由原理部分可以很清楚的知道low位置的值並不是tmp,所以需要將tmp賦值給arr[low] arr[low] = tmp; return low; // 返回tmp的正確位置 } } 以上就是有關快速排序的相關介紹，如要了解更多排序知識，請關注學步園。