关于StackOverflow有很多信息，但我无法准确地找到我需要的方式。
我正在尝试用中值实现一个quickSelect算法，但并没有完全使其发挥作用。
该算法假定在输入n>1元素使用这些步骤：
-
如果n＝＝1，则返回数组中的元素。
-
将阵列中的n个元素分成"n"的组；groupSize"；以及另一组"；groupSize"-最多1个元素。最初的算法是5组，但我希望它是模块化的。
-
通过使用插入排序并拾取排序子数组的中值，找到n/groupSize的每个(上限值(的中值。
-
递归调用Select以找到中值"；x〃；在步骤3中找到的上限值n/groupSize中值。给定中值的数目是偶数-"0"；x〃；将是最底层的中位数。
-
这是我发现最棘手的部分——将输入数组划分为中值"；x〃；使用分区(可能囤积平价(。在k中放置在分区的下部区域中的元素的数量so"；x〃；将是第k个最小的元素，并且分区的上部将保持n-k个元素。
-
如果i＝k返回"k"；x〃，如果i<k调用递归地选择以查找下部子数组中的第i个最小元素，如果i>k调用select以查找上部子数组中最小的(i-k(。
我不知道如何执行第5节，我觉得这是的全部内容
这是我的精选
if(right-left+1==1) return array[left];
// full steps are the count of full groups in size of groupSize(left of decimal point)
int fullSteps = array.length/groupSize;
int semiSteps = (int)((double)(array.length)%groupSize);
int i;
//array of medians is the size of number of groups needed
int medianArraySize = (int) Math.ceil (((double)(array.length))/groupSize);
int [] medianArray = new int [medianArraySize];
print(medianArray);
// sort the entire array by cutting it to chunks of defined size
for(i=0;i<medianArraySize;i++){
insertionSort(array, i*groupSize,i*groupSize+groupSize);
//place the median of sorted sub-array into median array in place i
medianArray[i]=findMidean(array, i*groupSize, i*groupSize+groupSize);
//implement insertion sort on full groups to find median - ceilling value
}
int medianOfMedians = select(medianArray,0,medianArraySize-1,groupSize,medianArray[(medianArraySize-1)/2]);
//find median of medians without using recursion
// int medianOfMedians = medianArray[(medianArraySize-1)/2];
// System.out.println("median of medians is :" +medianOfMedians);
int pivot = hoarePartition(array,left,right,medianOfMedians);
int k = left-pivot +1;
if (pivot==k-1) return array[pivot];
else
if (pivot<k-1) return select(array,pivot +1,right,groupSize,ithSmallest);
else return select(array,left,pivot-1,groupSize,ithSmallest-k);
}
辅助函数-查找中值
*
* returns the median value for the desginated range in given array.
*/
private static int findMidean(int [] array, double start,int end){
int stopper = Math.min(array.length,end);
int index =(int)(Math.ceil(start+stopper-1)/2.0);
return array[index];
}
分区算法
public static int hoarePartition(int[] arr, int low, int high,int pivot)
{
int i = low, j = high;
while (true) {
// Find leftmost element greater
// than or equal to pivot
while (i<j && arr[i] < pivot){
i++;
}
// Find rightmost element smaller
// than or equal to pivot
while (j>i && arr[j] > pivot){
j--;
}
// If two pointers met.
if (i >= j)
return j;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// swap(arr[i], arr[j]);
}
}
和插入排序
public static void insertionSort(int [] arr,int placeHolder,int end)
{
int stopper = Math.min(arr.length,end);
for (int i = placeHolder; i < stopper; ++i) {
int key = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
如果使用Hoare分区方案，那么pivot和所有等于pivot的元素都可以到达任何地方。这意味着不能使用i == k的情况，相反，quickselect将不得不递归地调用自己，直到达到单个元素的基本情况。
如果使用Lomuto分区方案，则将pivot放置到位，并返回pivot的索引，因此可以使用i == k情况。