排序原理:观谦。
①選定一個(gè)值作為分界值顷窒，將元素分為大于分界值和小于分界值兩部分谢床。
②小于分界值數(shù)據(jù)放在分界值左邊性含，大于分界值數(shù)據(jù)放在分界值右邊擂达。
③將分界值兩邊的數(shù)據(jù)重復(fù)尋找分界值分組，直到每組只有兩個(gè)數(shù)據(jù)并排序胶滋。
切分原理;
①選定一個(gè)基準(zhǔn)值板鬓，用兩個(gè)指針?lè)謩e指向數(shù)組的首部和尾部。
②先從尾部到頭部搜索一個(gè)比基準(zhǔn)值小的數(shù)值究恤，搜索到即停止俭令，并記錄其索引。
③再?gòu)氖撞康轿膊克阉饕粋€(gè)比基準(zhǔn)值大的數(shù)值部宿，搜索到即停止抄腔，并記錄其索引。
④交換兩個(gè)指針的元素理张。
⑤重復(fù)搜索赫蛇，直到左指針的索引大于等于右指針的索引。
時(shí)間復(fù)雜度：
最好情況：O(nlogn)
最壞情況：O(n^2)
平均情況：O(nlogn)
空間復(fù)雜度：
O(nlogn)
穩(wěn)定性：
不穩(wěn)定
實(shí)現(xiàn)：
API設(shè)計(jì):
①主排序算法用于排序
public static void sort(int[] a)
②對(duì)數(shù)組從low到high位置的元素進(jìn)行排序
private static void localSort（int[] a雾叭，int low,int high）
③對(duì)數(shù)組中從索引low到high處的元素按界限值進(jìn)行分組悟耘，并返回界限值的索引。
public static int partition(int[] a,int low,int high)
④ 比較API织狐，用于比較兩個(gè)元素大小
private static boolean greater(int[] a,int v,int w)
⑤交換API暂幼，用于交換兩個(gè)索引位置的值
private static void exchange(int[] a,int i,int j)
API實(shí)現(xiàn)：
//主排序算法用于排序
public static void sort(int[] a) {
int low = 0;
int high = a.length - 1;
localSort(a,low,high);
}
//對(duì)數(shù)組從low到high位置的元素進(jìn)行排序
private static void localSort(int[] a,int low,int high){
if(low >= high) {
return;
}
int partition = partition(a,low,high);
//分別讓左右分組進(jìn)行分組有序
localSort(a,low,partition-1);
localSort(a,partition+1,high);
}
//對(duì)數(shù)組中從索引low到high處的元素按界限值進(jìn)行分組筏勒，并返回界限值位置變換后的索引。
public static int partition(int[] a,int low,int high) {
//1.確定分界值
int key = a[low];
//2.設(shè)置兩個(gè)指針?lè)謩e指向第一個(gè)元素和最后一個(gè)元素的下一位置
int left = low;
int right = high +1;
//切分
while(true) {
//先從右向左移動(dòng)right指針找到一個(gè)比key小的數(shù)值
while(!greater(a,--right,key)) {
if(right == low) break;
}
//再?gòu)淖笙蛴乙苿?dòng)left指針找到一個(gè)比key大的數(shù)值
while(!greater(a,++left,key)) {
if(left == high) break;
}
if(left >= right){
break;
}else {
exchange(a,left,right);
}
}
//交換分界值位置
exchange(a,low,right);
return right;
}
//比較API旺嬉，用于比較兩個(gè)元素大小
private static boolean greater(int[] a,int v,int w) {
if(a[v]>a[w]) {
return true;
}
return false;
}
//交換API管行，用于交換兩個(gè)索引位置的值
private static void exchange(int[] a,int i,int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
