java七大排序——6_快速排序-創新互聯

一、快速排序：

在待排元素中找出一個基準元素,然后比較基準元素和其他元素，以基準元素為基準，將大于準的元素的放后邊，小于
基準的元素放前邊。然后再對分好的左右兩個小區間進行快速排序
以基準元素劃分區間的方式有以下2種：
第一種：設兩個參考變量less,great，less先從第一個元素開始往后遍歷，直到找到的當前元素大于基準元素。
然后讓great從最后一個元素開始往前遍歷，直到找到當前元素小于基準元素，交換當前less和great指向的值。
再接著從less開始，重復上述動作，遍歷結束的條件是less>=great;
遍歷結束后，交換當前less(或great)指向的值與基準元素的值。再進行下一次的小區間內的查找

成都創新互聯公司網站建設公司一直秉承“誠信做人，踏實做事”的原則，不欺瞞客戶，是我們最起碼的底線！以服務為基礎，以質量求生存，以技術求發展，成交一個客戶多一個朋友！專注中小微企業官網定制，成都做網站、成都網站設計、成都外貿網站建設，塑造企業網絡形象打造互聯網企業效應。

二、圖示

java七大排序——6_快速排序

注意：新劃分的兩個區間的范圍是：
第一段：原本的left到上一輪基準元素最終位置的前一位；即[left,pivotIndex-1]
第二段：上一輪基準元素最終位置的后一位到原本的right;即[pivotIndex+1,right]
最終結果:
java七大排序——6_快速排序

三、代碼實現

public static void quickSort ( int[] array){
int left = 0;
int right = array.length - 1;
quickSortInternal1(array, left, right);
}
public static void quickSortInternal ( int[] array, int left, int right){
if (left >= right) {
return;
}
int pivotIndex = partion1(array, left, right);//找基準值的函數
// int[] indice=partion4(array,left,right);
// quickSortInternal(array,left,indice[0]-1);
// quickSortInternal(array,indice[1]+1,right);
quickSortInternal(array, left, pivotIndex - 1);//注意區間范圍
quickSortInternal(array, pivotIndex + 1, right);

}
private static int partion1 ( int[] array, int left, int right){
int pivot = array[right];
int less = left;
int great = right;
while (less < great) {
while (less < great && array[less] <= pivot) {
less++;
}
while (less < great && array[great] >= pivot) {
great--;
}
swap(array, less, great);
}
swap(array, less, right);
return less;
}

第二種：挖坑法
找到基準元素pivot,設兩個變量less和great,less從第一個數開始向后遍歷,直到找到大于pivot的數，停下，將array[less]的值放到array[great]處。（即array[great]=array[less]）
然后讓right從當前區間最后一個數開始往前遍歷，直到找到小于pivot的數，停下，進行array[less]=array[great]的操作。再接著less++向后遍歷，重復以上操作，結束條件為left>=right;
結束后將pivot的值賦給當前less(great)的數組元素
圖示：
java七大排序——6_快速排序

注意：pivot基準元素可以任意選，但這里為了講述方便，每次選擇區間的最后一個元素
最終結果

代碼實現

private static int partion1 ( int[] array, int left, int right){
int pivot = array[right];//基準值
int less = left;
int great = right;
while (less < great) {
while (less < great && array[less] <= pivot) {
less++;
}
array[great] = array[less];
while (less < great && array[great] >= pivot) {
great--;
}
array[less] = array[great];
}
array[less] = pivot;
return less;
}

創新互聯www.cdcxhl.cn，專業提供香港、美國云服務器，動態BGP最優骨干路由自動選擇，持續穩定高效的網絡助力業務部署。公司持有工信部辦法的idc、isp許可證，機房獨有T級流量清洗系統配攻擊溯源，準確進行流量調度，確保服務器高可用性。佳節活動現已開啟，新人活動云服務器買多久送多久。

當前題目：java七大排序——6_快速排序-創新互聯
文章鏈接：http://vcdvsql.cn/article38/ieipp.html

成都網站建設公司_創新互聯，為您提供域名注冊、企業網站制作、關鍵詞優化、網站設計公司、網站導航、定制開發