快速排序的原理：選擇一個關(guān)鍵值作為基準(zhǔn)值。比基準(zhǔn)值小的都在左邊序列（一般是無序的），比基準(zhǔn)值大的都在右邊（一般是無序的）。一般選擇序列的第一個元素。
一次循環(huán)：從后往前比較，用基準(zhǔn)值和最后一個值比較，如果比基準(zhǔn)值小的交換位置，如果沒有繼續(xù)比較下一個，直到找到第一個比基準(zhǔn)值小的值才交換。找到這個值之后，又從前往后開始比較，如果有比基準(zhǔn)值大的，交換位置，如果沒有繼續(xù)比較下一個，直到找到第一個比基準(zhǔn)值大的值才交換。直到從前往后的比較索引>從后往前比較的索引，結(jié)束第一次循環(huán)，此時，對于基準(zhǔn)值來說，左右兩邊就是有序的了。
接著分別比較左右兩邊的序列，重復(fù)上述的循環(huán)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
public class fastsort{ public static void main(string []args){ system.out.println("hello world"); int[] a = {12,20,5,16,15,1,30,45,23,9}; int start = 0; int end = a.length-1; sort(a,start,end); for (int i = 0; i<a.length; i++){ system.out.println(a[i]); } } public void sort(int[] a,int low,int high){ int start = low; int end = high; int key = a[low]; while(end>start){ //從后往前比較 while(end>start&&a[end]>=key) //如果沒有比關(guān)鍵值小的，比較下一個，直到有比關(guān)鍵值小的交換位置，然后又從前往后比較 end--; if(a[end]<=key){ int temp = a[end]; a[end] = a[start]; a[start] = temp; } //從前往后比較 while(end>start&&a[start]<=key)//如果沒有比關(guān)鍵值大的，比較下一個，直到有比關(guān)鍵值大的交換位置 start++; if(a[start]>=key){ int temp = a[start]; a[start] = a[end]; a[end] = temp; } //此時第一次循環(huán)比較結(jié)束，關(guān)鍵值的位置已經(jīng)確定了。左邊的值都比關(guān)鍵值小，右邊的值都比關(guān)鍵值大，但是兩邊的順序還有可能是不一樣的，進(jìn)行下面的遞歸調(diào)用 } //遞歸 if(start>low) sort(a,low,start-1); //左邊序列。第一個索引位置到關(guān)鍵值索引-1 if(end<high) sort(a,end+1,high); //右邊序列。從關(guān)鍵值索引+1到最后一個 }} |
上面最后一句不是基準(zhǔn)值的意思是，不是直接用基準(zhǔn)值交換，是用基準(zhǔn)值所在的索引交換。
下面我們看看另一種實現(xiàn)方式。
一趟快速排序的過程如下
（1）先從序列中選取一個數(shù)作為基準(zhǔn)數(shù)
（2）將比這個數(shù)大的數(shù)全部放到它的右邊，把小于或者等于它的數(shù)全部放到它的左邊
一趟快速排序也叫做partion，即將序列劃分為兩部分，一部分比基準(zhǔn)數(shù)小，另一部分比基準(zhǔn)數(shù)大，然后
再進(jìn)行分治過程，因為每一次partion不一定都能保證劃分得很均勻，所以最壞情況下的時間復(fù)雜度不能
保證總是為
。
對于partion過程，通常有兩種方法
（1）兩個指針從首尾向中間掃描（雙向掃描）
這種方法可以用挖坑填數(shù)來形容，比如
初始化：i=0;j=9;pivot=a[0];
現(xiàn)在a[0]保存到了變量pivot中了，相當(dāng)于在數(shù)組a[0]處挖了個坑，那么可以將其它的數(shù)填到這里來。從j開始向前找一個小于或者等于pivot的數(shù)，即將a[8]填入a[0]，但a[8]又形成了一個新坑，再從i開始向后找一個大于pivot的數(shù)，即a[3]填入a[8]，那么a[3]又形成了一個新坑......
就這樣，直到i==j才停止，最終得到結(jié)果如下
上述過程就是一趟快速排序。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
/** * 功能描述: 快速排序，雙向掃描 * * @date 2017-09-12 10:17 * @since v1.0.0 */public class quicksort { public static void main(string[] args){ integer[] arr = {8, 2, 9, 1, 5, 10, 12, 3, 18, 6}; system.out.println(arrays.aslist(arr)); quicksort(arr, 0, arr.length - 1); system.out.println(arrays.aslist(arr)); } public static void quicksort(integer[] arr, int left, int right) { if(left < right) { int partition = partition(arr, left, right); quicksort(arr, left, partition - 1); quicksort(arr, partition + 1, right); } } public static int partition(integer[] arr, int left, int right) { integer pivot = arr[left]; int i = left, j = right; while (i < j) { while (arr[j] >= pivot && i < j) { j--; } arr[i] = arr[j]; while (arr[i] <= pivot && i < j) { i++; } arr[j] = arr[i]; } arr[i] = pivot; return i; }} |
總結(jié)
以上就是本文關(guān)于快速排序算法在java中的實現(xiàn)的全部內(nèi)容，希望對大家有所幫助。如有不足之處，歡迎留言指出。
原文鏈接：https://www.cnblogs.com/hjy9420/p/5032309.html
