快速排序
1.快速排序的原理
- 從如圖所示待排序區間中選擇一個數，作為基準值(pivot)，例如選擇0號下標的6作為基準值放入tmp中；
-
遍歷整個待排序的區間，將比基準值小的（可以包含相等的）放到基準值的左邊，比基準值大的（可以包含相等的）放到基準值的右邊；
-
當low與high相遇時，此時找到基準，并采用分治思想，對左右兩個小區間按照同樣的方式處理，直到小區間的長度等于1，代表已經有序，或者小區間的長度等于0，代表沒有資料；
基準值的左邊已經有序，以同樣的方式處理右邊，
2.快速排序的代碼實作
public static int pivot(int[] array,int start,int end){
int tmp = array[start];
while(start<end){
while(start < end && array[end] >= tmp){
end--;
}
array[start]=array[end];
//把資料賦值給start
while(start < end && array[end] <= tmp){
start++;
}
//把start下標的值給end
array[start] = tmp;
return start;
}
public static void quick(int[] array,int low,int high){
if(low < high){
int piv = pivot(array,low,high);
qucik(array,low,piv-1);
qucik(array,piv+1,high );
}
}
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
測驗代碼：
public static void main(String[] args){
int[] array = {13,5,22,7,14,54,65,157};
System.out.println(Arrays.toString(array));
quickSort(array);
System.out.println(Arrays.toString(array));
}
測驗結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/256363.html
標籤：java
下一篇：微信二維碼支付