要求找出第几名的元素是什么（找出B[i]的值）？ 找出第k名的元素的值。
先从A中随机一个下标index1， 然后进行一趟快速排序等到新数组A1，排完了就知道index1对应的元素在A1中的新下标index2. 如果k等于index2,则A1[index2]就是要找的值。
如果 k小于index2 ,则在A1的以index2为分界的左部分去找。
如果 k大于index2 ,则在A1的以index2为分界的右部分去找。
===========测试用的代码=================
package test;
import org.junit.Test;
public class RankKthTest
{
@Test
public void test1()
{
RankKth rk = new RankKth();
// 0,1,2,3,4,5,6,07,08,09,10,011,012
// 0,1,2,2,3,3,5,35,61,75,75,324,513
int[] arr = { 3, 2, 35, 1, 2, 3, 5, 61, 324, 513, 75, 0, 75 };
int value;
value = rk.searchKthEle(arr, 12);// ?找出最大数
System.out.println(value);
value = rk.searchKthEle(arr, 0);// ?找出最小数
System.out.println(value);
value = rk.searchKthEle(arr, 6);// ?找出第6名的数
System.out.println(value);
}
}
测试结果:
找出最大数
head=0, rear=12, index=6
3,2,35,1,2,3,5,61,324,513,75,0,75,
index=6, value=5
3,2,0,1,2,3,5,61,324,513,75,35,75,
=========
head=7, rear=12, index=9
3,2,0,1,2,3,5,61,324,513,75,35,75,
index=12, value=513
3,2,0,1,2,3,5,61,324,75,75,35,513,
=========
513
$$$$$$$$$$$$$$$$$$
找出最小数
head=0, rear=12, index=6
3,2,0,1,2,3,5,61,324,75,75,35,513,
index=6, value=5
3,2,0,1,2,3,5,61,324,75,75,35,513,
=========
head=0, rear=5, index=2
3,2,0,1,2,3,5,61,324,75,75,35,513,
index=0, value=0
0,2,3,1,2,3,5,61,324,75,75,35,513,
=========
0
$$$$$$$$$$$$$$$$$$
找出第6大的数
head=0, rear=12, index=6
0,2,3,1,2,3,5,61,324,75,75,35,513,
index=6, value=5
0,2,3,1,2,3,5,61,324,75,75,35,513,
=========
5
===========================================================
package test;
public class RankKth
{
/**
* invokes this method to allow array containing duplicate elements
*
* @param index
* @param direction
* @return
*/
private int moveBound(int index, String direction)
{
if (direction.equals("left"))
{
while (true)
{
if (index - 1 >= 0)
{
if (intArr[index] == intArr[index - 1])
index--;
else break;
}
else break;
}
}
else
{
while (true)
{
if (index + 1 < intArr.length)
{
if (intArr[index] == intArr[index + 1])
index++;
else break;
}
else break;
}
}
return index;
}
private int[] intArr;
/**
* get the k'th element's value
*
* @param intArr
* @return value of k'th element
*/
public int searchKthEle(int[] intArr, int k)
{
if (k < 0 || k > intArr.length - 1) return Integer.MAX_VALUE;
this.intArr = intArr;
int retIndex, head, rear;
head = 0;
rear = intArr.length - 1;
retIndex = swapAccrodingToIndex(head, rear);
for (;;)
{
if (retIndex == k || head >= rear)
return intArr[retIndex];
else if (retIndex < k)
{
head = retIndex + 1;
head = moveBound(head, "right");
retIndex = swapAccrodingToIndex(head, rear);
}
else
{
rear = retIndex - 1;
rear = moveBound(rear, "left");
retIndex = swapAccrodingToIndex(head, rear);
}
}
}
/**
* find out element's index in a array when the array is sorted.
*
* @param intArr
* a array sorted or not sorted
* @param element
* a element in the array.
* @return index
*/
private int swapAccrodingToIndex(int head, int rear)
{
int index = (rear - head) / 2 + head;
System.out.println(String.format("head=%d, rear=%d, index=%d", head,
rear, index));
disp();
/*
* head=0, rear=1, index=0 1,2,2,35,3,3,5,61,324,513, index=1, value=2
* 1,2,2,35,3,3,5,61,324,513,
*/
int splitEle = intArr[index];
int i, j;
i = head;
j = rear;
while (i < j)
{
while (i < index)
{
if (intArr[i] > splitEle)
{
intArr[index] = intArr[i];
index = i;
break;
}
i++;
}
while (j > index)
{
if (intArr[j] < splitEle)
{
intArr[index] = intArr[j];
index = j;
break;
}
j--;
}
}
intArr[index] = splitEle;
System.out.println(String.format("index=%d, value=%d", index,
intArr[index]));
disp();
System.out.println("=========");
return index;// element's index in a sorted arr
}
private void disp()
{
for (int i = 0; i < intArr.length; i++)
{
System.out.print(intArr[i] + ",");
}
System.out.println();
}
}