快速选择算法理解

Question

我一直在阅读各种教程和文章，讨论快速排序和快速选择算法，但是我的理解仍然不够稳固。

鉴于这个代码结构，我需要能够掌握并解释快速选择算法的工作原理。

// 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
    }
}

- Edge

---

我可能对我的需求过于具体 - 对快速选择算法的一般理解将是最有帮助的，我提供的代码只是一个例子。 - Edge

那来自MIT的信息是关于排序而不是选择。就我所看到的。 - Edge

为什么我们需要这些：pivot-first+1和k-pivot？ - Anil Kumar K K

Answer 1

在快速选择算法中，最重要的部分是划分。因此，让我先解释一下。

快速选择算法中的划分操作会选择一个 pivot（可以是随机选择或者第一个/最后一个元素）。然后，它会按照那个元素重新排列列表，使得所有小于 pivot 的元素都在 pivot 左侧，其他元素都在右侧。然后返回 pivot 元素的索引。

现在我们正在寻找第 k 小元素。进行划分之后有以下几种情况：

1. k == pivot。那么你已经找到了第 k 小的元素。这是因为划分的方式使得恰好有 k-1 个元素小于第 k 个元素。
2. k < pivot。那么第 k 小的元素在 pivot 左侧。
3. k > pivot。那么第 k 小的元素在 pivot 右侧。实际上，你需要在右侧找到第 k-pivot 小的数来找到它。

- Vikas

---

我提供的代码示例是否对k执行了这3个检查？ - Edge

我发现我没有检查 k 是否等于 pivot。 - Edge

@Andrew，你代码中最后一个else块中已经包含了k==pivot的情况。 - Vikas

@Andrew，另外请注意，k < pivot - first是根据传递的first索引进行比较的。 - Vikas

Answer 2

顺便说一下，你的代码有一些bug。

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
    }
}

- Haitao

---

你的代码也有一个错误。第二个 quickSelect 应该是 quickSelect(items, pivot+1, last, k- (pivot-first+1));。 - UmNyobe

Answer 3

分区很简单：它重新排列元素，使得小于选定枢轴的元素在数组中的索引低于枢轴，而大于枢轴的元素在数组中的索引高于枢轴。

我在之前的回答中讨论了其余部分。

- Jerry Coffin

Answer 4

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);

}

// partition function同QuickSort一样

- ron davis

Answer 5

我正在阅读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

- Kousik Mandal

---

我仍然认为你可以在你的代码中添加一些解释。 - mate00

我已经添加了有意义的描述。 - Kousik Mandal

Answer 6

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;
}

- london_utku

---

这是不正确的，当 pivotIndex == k 时，返回该索引上的值，而在其他情况下调用 partition 并返回分区的索引。不知道为什么会被投票支持。 - Samer Tufail