【基礎(chǔ)算法】排序-復(fù)雜排序之二（找出第K大的數(shù)）
來源：程序員人生 發(fā)布時(shí)間：2014-11-05 08:54:57 閱讀次數(shù)：2710次
分割的思想是快速排序最精華的地方。每次分割出來的元素K1個排在第K位，所以利用這類思想我們最少知道3點(diǎn)
1. 被分割出來的元素K最后1定排在第K位。
2. 在K左側(cè)的元素1定比K小或相等。
3. 在K右側(cè)的元素1定比K大或相等。
所以我們可以通過這些性質(zhì)定位到任意1個元素。
比如我們partition完1個數(shù)組后，得到A={5,3,4,2,6,8,10,12,11,9}
A[K]=8，所以我們知道排好序后的A[5]=8, A[4]1定在8左側(cè)，A[6]1定在8右側(cè)
所以，我們1定知道8這個數(shù)是數(shù)組里第5+1小的數(shù)，第10⑸大的數(shù)
所以我們得出 如果分割出來的數(shù)A[K]=X, 那末X1定是數(shù)組里的第K+1位，也就是第K+1小的數(shù)
如果數(shù)組的長度為N，那末X就是數(shù)組里第N-K大的數(shù)
下面是分割的代碼
public static int partition(int[] array, int left, int right) {
int i = left;
int j = right + 1;
while (true) {
while (more(array[left], array[++i]))
if (i == right)
break;
while (more(array[--j], array[left]))
if (j == left)
break;
if (i >= j)
break;
exchange(array, i, j);
}
exchange(array, left, j);
return j;
}
接下來就是如何在分割后定位其他的元素了？
如果我們定位了A[K]=X，發(fā)現(xiàn)目標(biāo)元素O比X大，那末就在右側(cè)找，left=K+1,如果比X小，那末就在左側(cè)找，right=K⑴，否則定位成功
public static int select(int[] array, int k) {
int left = 0;
int right = array.length - 1;
while (left < right) {
int j = partition(array, left, right);
if (j < k)
left = j + 1;
else if (j > k)
right = j - 1;
else
return array[k];
}
return array[k];
}
下面給出完全代碼，僅供大家參考
// compare
public static boolean more(int v, int w) {
return v > w;
}
// exchange
public static void exchange(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static int partition(int[] array, int left, int right) {
int i = left;
int j = right + 1;
while (true) {
while (more(array[left], array[++i]))
if (i == right)
break;
while (more(array[--j], array[left]))
if (j == left)
break;
if (i >= j)
break;
exchange(array, i, j);
}
exchange(array, left, j);
return j;
}
public static int select(int[] array, int k) {
int left = 0;
int right = array.length - 1;
while (left < right) {
int j = partition(array, left, right);
if (j < k)
left = j + 1;
else if (j > k)
right = j - 1;
else
return array[k];
}
return array[k];
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
