【基础算法】排序-复杂排序之二（找出第K大的数）
切割的思想是高速排序最精髓的地方。每一次切割出来的元素K一个排在第K位，所以利用这样的思想我们至少知道3点1. 被切割出来的元素K最后一定排在第K位。
2. 在K左边的元素一定比K小或者相等。
3. 在K右边的元素一定比K大或者相等。
所以我们能够通过这些性质定位到随意一个元素。
比方我们partition完一个数组后，得到A={5,3,4,2,6,8,10,12,11,9}
A=8，所以我们知道排好序后的A=8, A一定在8左边，A一定在8右边
所以，我们一定知道8这个数是数组里第5+1小的数。第10-5大的数
所以我们得出 假设切割出来的数A=X, 那么X一定是数组里的第K+1位，也就是第K+1小的数
假设数组的长度为N，那么X就是数组里第N-K大的数
以下是切割的代码
public static int partition(int[] array, int left, int right) {
int i = left;
int j = right + 1;
while (true) {
while (more(array, array[++i]))
if (i == right)
break;
while (more(array[--j], array))
if (j == left)
break;
if (i >= j)
break;
exchange(array, i, j);
}
exchange(array, left, j);
return j;
}
接下来就是怎样在切割后定位其它的元素了？ 假设我们定位了A=X，发现目标元素O比X大，那么就在右边找，left=K+1,假设比X小，那么就在左边找。right=K-1，否则定位成功
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;
}
return array;
}
以下给出完整代码，仅供大家參考// 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;
array = array;
array = temp;
}
public static int partition(int[] array, int left, int right) {
int i = left;
int j = right + 1;
while (true) {
while (more(array, array[++i]))
if (i == right)
break;
while (more(array[--j], array))
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;
}
return array;
}
页:
[1]