1.快速排序的思想

快速排序?qū)儆诮粨Q排序，是冒泡排序的升降版。相對(duì)于冒泡排序而言，快速排序增大了記錄比較和移動(dòng)的距離，將關(guān)鍵字較大的記錄直接移動(dòng)到后面，將關(guān)鍵字較小的記錄直接移動(dòng)到前面；不再是相鄰兩個(gè)記錄依次進(jìn)行比較和交換，需要多次移動(dòng)才能將關(guān)鍵字較大的記錄移動(dòng)到后面。從而快速排序減少了總的比較次數(shù)和移動(dòng)次數(shù)。

快速排序是指，在待排序記錄中選擇一個(gè)記錄作為基準(zhǔn)記錄(通常選擇第一個(gè))，從待排序兩端開(kāi)始交替比較，使得基準(zhǔn)記錄左側(cè)的記錄的關(guān)鍵字都比基準(zhǔn)記錄的關(guān)鍵字小，右側(cè)都比基準(zhǔn)記錄大，這就是一趟快排。再將基準(zhǔn)記錄分出來(lái)的兩個(gè)區(qū)域進(jìn)行快排，以此類(lèi)推，直到每個(gè)分區(qū)只有一個(gè)元素。

快速排序采用的分冶法的策略。

2.快速排序的本質(zhì)

快速排序本質(zhì)是不斷確定所選基準(zhǔn)值的位置，當(dāng)分區(qū)中只有一個(gè)記錄時(shí)，不需要進(jìn)行移動(dòng)，排序結(jié)束。網(wǎng)上有一張圖展示的很到位：(侵刪)

3.代碼

1 public classQuickSort {2 public int[] quickSort(int[] data, int start, intend){3 if(start > end) return null;4 int pivot = data[start]; //基準(zhǔn)值

5 int i =start;6 int j =end;7 inttmp;8 while(i =i && data[j] >= pivot){ //注意這里j>=i

13 j--;14 }15 if(i start){22 tmp =data[start];23 data[start] =data[j];24 data[j] =tmp;25 }26 quickSort(data,start,j-1);27 quickSort(data,j+1,end);28 returndata;29 }30

31 public static voidmain(String[] args){32 QuickSort sort = newQuickSort();33 int[] data = {70,30,40,10,80,20,90,100,75,60,45};34 data = sort.quickSort(data,0,data.length-1);35 for(intx : data) {36 System.out.println("quickSort" +x);37 }38 }39 }

4.需要注意的地方

快排有多種實(shí)現(xiàn)方法，在一些資料上提到：每一趟排序必須右端先走，然后左端再走。這樣操作的原因是來(lái)自于代碼的寫(xiě)法，他們的代碼寫(xiě)法如下：

1 packagelearn;2 //快速排序

3 public classQuickSort {4 public int[] quickSort(int[] data, int start, intend){5 if(start > end) return null;6 int pivot = data[start]; //基準(zhǔn)值

7 int i =start;8 int j =end;9 inttmp;10 while(i =i && data[j] >= pivot){//注意這里j>=i15 //j--;16 //}

17 while(j>i && data[j] >=pivot){18 j--;19 }20 while(i start){ //當(dāng)j = start避免一趟排序，這個(gè)約束條件不是必須的

30 tmp =data[start];31 data[start] =data[j];32 data[j] =tmp;33 }34 quickSort(data,start,j-1);35 quickSort(data,j+1,end);36 returndata;37 }38

39 public static voidmain(String[] args){40 QuickSort sort = newQuickSort();41 int[] data = {70,30,40,10,80,20,90,100,75,60,45};42 data = sort.quickSort(data,0,data.length-1);43 for(intx : data) {44 System.out.println("quickSort" +x);45 }46 }47 }

區(qū)別在于第11-16行和第17-22行。按照17-22行，j 結(jié)束的條件是 j>i，我們考慮一下while( i < j)結(jié)束后 i == j，如果讓i 先出發(fā)，i 停在值大于基準(zhǔn)值的位置；因?yàn)?j>i 條件的約束，j只能也停留在i處，這個(gè)時(shí)候在while( i < j)結(jié)束后交換data[j] ，(data[j] == data[i])，就把大于基準(zhǔn)值的data[j]交換到基準(zhǔn)值左邊了。但按照17-22行，讓j先出發(fā)，總會(huì)停在小于基準(zhǔn)值的位置，這樣循環(huán)結(jié)束后和基準(zhǔn)值交換是沒(méi)有問(wèn)題的。

或者按照11-16行的寫(xiě)法，誰(shuí)先出發(fā)無(wú)所謂，只要j 結(jié)束的條件變成 j >= i，那么 j 會(huì)跑到 i 停下來(lái)的前一個(gè)位置再停下來(lái)，這時(shí)data[j] 小于基準(zhǔn)值，和基準(zhǔn)值交換是沒(méi)有問(wèn)題的。

以上就是我對(duì)這個(gè)問(wèn)題的一點(diǎn)思考了。

總結(jié)

以上是生活随笔為你收集整理的Java写一个快速排序_快速排序java实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。