partiton
1.在數(shù)組a[]找到一個(gè)樞紐元(pivot)唯袄，pivot與第一個(gè)元素交換
2.a[low]為第二個(gè)元素，a[high]為倒數(shù)第一個(gè)元素
3.當(dāng)low元素小于pivot,low++,當(dāng)high元素大于pivot,high++,當(dāng)i,j都停止自增時(shí)匀们，若a[i]在a[j]左側(cè)，則交換元素
4.當(dāng)a[low]在a[high]右側(cè)准给，停止
5.當(dāng)high>first且A[high]>=pivot時(shí)泄朴，high--
6.當(dāng)a[high] < pivot,交換重抖，返回high，否則返回first
partition代碼
public int partition(int[] A, int first, int last){
//確定一個(gè)pivot祖灰，左邊小于钟沛，右邊大于
//區(qū)間第一個(gè)元素為pivot
int pivot = A[first];
int low = first + 1;
int high = last;
while (low < high){
if(low < high && A[low] <= pivot){
low++;
}
if(low < high && A[high] > pivot){
high--;
}
if(low < high){
int temp = A[high];
A[high] = A[low];
A[low] = temp;
}
}
while (high > first && A[high] >= pivot){
//查找結(jié)束時(shí)A[high]等于主元或查找不執(zhí)行時(shí)只有兩個(gè)元素
high--;
}
if(pivot > A[high]){
A[first] = A[high];
A[high] = pivot;
return high;
}
return first;
}
整體代碼
public int[] quickSort(int[] A, int n){
sort(A, 0, n - 1);
return A;
}
public void sort(int[] A, int first, int last){
if (first < last){
int partition = partition(A, first, last);
sort(A, first, partition - 1);
sort(A, partition+1, last);
}
}
public int partition(int[] A, int first, int last){
//確定一個(gè)pivot，左邊小于局扶，右邊大于
//區(qū)間第一個(gè)元素為pivot
int pivot = A[first];
int low = first + 1;
int high = last;
while (low < high){
if(low < high && A[low] <= pivot){
low++;
}
if(low < high && A[high] > pivot){
high--;
}
if(low < high){
int temp = A[high];
A[high] = A[low];
A[low] = temp;
}
}
while (high > first && A[high] >= pivot){
//查找結(jié)束時(shí)A[high]等于主元或查找不執(zhí)行時(shí)只有兩個(gè)元素
high--;
}
if(pivot > A[high]){
A[first] = A[high];
A[high] = pivot;
return high;
}
return first;
}
emmm,影響性能的主要是partition代碼恨统，等慢慢學(xué)習(xí)后會(huì)繼續(xù)修改
