我一直在仔细研究各种讨论快速排序和快速选择的教程和文章，但是，我对它们的理解仍然不稳定。
鉴于此代码结构，我需要能够掌握并解释快速选择的工作原理。
// return the kth smallest item
int quickSelect(int items[], int first, int last, int k) {
int pivot = partition(items, first, last);
if (k < pivot-first) {
return quickSelect(items, first, pivot, k);
} else if (k > pivot) {
return quickSelect(items, pivot+1, last, k-pivot);
} else {
return items[k];
}
}
我需要一些帮助来分解为伪代码，虽然我没有获得分区函数代码，但我想了解在提供的快速选择函数下它会做什么。
我知道快速排序的工作原理，只是不是快速选择。我刚刚提供的代码是我们关于如何格式化快速选择的示例。
编辑：更正后的代码是
int quickSelect(int items[], int first, int last, int k)
{
int pivot = partition(items, first, last);
if (k < pivot-first+1)
{ //boundary was wrong
return quickSelect(items, first, pivot, k);
}
else if (k > pivot-first+1)
{//boundary was wrong
return quickSelect(items, pivot+1, last, k-pivot);
}
else
{
return items[pivot];//index was wrong
}
}
快速选择中的重要部分是分区。因此，让我先解释一下。
快速选择中的分区会选取一个pivot（随机或第一个/最后一个元素）。然后，它重新排列列表，使所有小于 pivot 的元素都位于透视的左侧，其他元素位于右侧。然后，它返回pivot元素的索引。
现在我们在这里找到第 k 个最小元素。分区后的情况是：
-
k == pivot.那么你已经找到了最小的k个。这是因为分区的工作方式。正好有k - 1元素小于kth元素。 -
k < pivot.那么最小的k个在pivot的左侧。 -
k > pivot.那么最小的第 k 个在枢轴的右侧。要找到它，你实际上必须在右边找到k-pivot最小的数字。
顺便说一句，你的代码有一些错误。
int quickSelect(int items[], int first, int last, int k) {
int pivot = partition(items, first, last);
if (k < pivot-first+1) { //boundary was wrong
return quickSelect(items, first, pivot, k);
} else if (k > pivot-first+1) {//boundary was wrong
return quickSelect(items, pivot+1, last, k-pivot);
} else {
return items[pivot];//index was wrong
}
}
分区非常简单：它重新排列元素，以便小于选定枢轴的元素在数组中的索引低于枢轴，而大于枢轴的元素在数组中的索引较高。
我在之前的回答中谈到了其余的。
int quickSelect(int A[], int l, int h,int k)
{
int p = partition(A, l, h);
if(p==(k-1)) return A[p];
else if(p>(k-1)) return quickSelect(A, l, p - 1,k);
else return quickSelect(A, p + 1, h,k);
}
分区功能与快速排序相同
我正在阅读CLRS算法一书来学习快速选择算法，我们可以以简单的方式实现算法。
package selection;
import java.util.Random;
/**
* This class will calculate and print Nth ascending order element
* from an unsorted array in expected time complexity O(N), where N is the
* number of elements in the array.
*
* The important part of this algorithm the randomizedPartition() method.
*
* @author kmandal
*
*/
public class QuickSelect {
public static void main(String[] args) {
int[] A = { 7, 1, 2, 6, 0, 1, 96, -1, -100, 10000 };
for (int i = 0; i < A.length; i++) {
System.out.println("The " + i + "th ascending order element is "
+ quickSelect(A, 0, A.length - 1, i));
}
}
/**
* Similar to Quick sort algorithm partitioning approach works, but after
* that instead of recursively work on both halves here will be recursing
* into desired half. This step ensure to the expected running time to be
* O(N).
*
* @param A
* @param p
* @param r
* @param i
* @return
*/
private static int quickSelect(int[] A, int p, int r, int i) {
if (p == r) {
return A[p];
}
int partitionIndex = randomizedPartition(A, p, r);
if (i == partitionIndex) {
return A[i];
} else if (i < partitionIndex) {// element is present in left side of
// partition
return quickSelect(A, p, partitionIndex - 1, i);
} else {
return quickSelect(A, partitionIndex + 1, r, i);// element is
// present in right
// side of partition
}
}
/**
*
* Similar to Quick sort algorithm this method is randomly select pivot
* element index. Then it swap the random pivot element index with right
* most element. This random selection step is expecting to make the
* partitioning balanced. Then in-place rearranging the array to make all
* elements in the left side of the pivot element are less than pivot
* element and the right side elements are equals or grater than the pivot
* element. Finally return partition index.
*
* @param A
* @param p
* @param r
* @return
*/
private static int randomizedPartition(int[] A, int p, int r) {
int partitionIndex = p;
int random = p + new Random().nextInt(r - p + 1);// select
// pseudo random
// element
swap(A, random, r);// swap with right most element
int pivot = A[r];// select the pivot element
for (int i = p; i < A.length - 1; i++) {
if (A[i] < pivot) {
swap(A, i, partitionIndex);
partitionIndex++;
}
}
swap(A, partitionIndex, r);
return partitionIndex;
}
/**
* Swapping 2 elements in an array.
*
* @param A
* @param i
* @param j
*/
private static void swap(int[] A, int i, int j) {
if (i != j && A[i] != A[j]) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
Output:
The 0th ascending order element is -100
The 1th ascending order element is -1
The 2th ascending order element is 0
The 3th ascending order element is 1
The 4th ascending order element is 1
The 5th ascending order element is 2
The 6th ascending order element is 6
The 7th ascending order element is 7
The 8th ascending order element is 96
The 9th ascending order element is 10000
int partition(vector<int> &vec, int left, int right, int pivotIndex)
{
int pivot = vec[pivotIndex];
int partitionIndex = left;
swap(vec[pivotIndex],vec[right]);
for(int i=left; i < right; i++) {
if(vec[i]<pivot) {
swap(vec[i],vec[partitionIndex]);
partitionIndex++;
}
}
swap(vec[partitionIndex], vec[right]);
return partitionIndex;
}
int select(vector<int> &vec, int left, int right, int k)
{
int pivotIndex;
if (right == left) {
return vec[left];
}
pivotIndex = left + rand() % (right-left);
pivotIndex = partition(vec,left,right,pivotIndex);
if (pivotIndex == k) {
return vec[k];
} else if(k<pivotIndex) {
/*k is present on the left size of pivotIndex*/
return partition(vec,left,pivotIndex-1, k);
} else {
/*k occurs on the right size of pivotIndex*/
return partition(vec, pivotIndex+1, right, k);
}
return 0;
}