QuickSelect算法理解 [英] QuickSelect Algorithm Understanding

问题描述

我一直在钻研各种教程和讨论快速排序和quickselect的文章，但是我对他们的了解还摇摇欲坠。

I've been poring over various tutorials and articles that discuss quicksort and quickselect, however my understanding of them is still shaky.

鉴于这种code结构，我需要能够把握和解释quickselect是如何工作的。

Given this code structure, I need to be able to grasp and explain how quickselect works.

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

我需要一些帮助分解成伪code，虽然我还没有具备分区功能code，我想知道会怎样做给出的quickselect功能提供的。

I need a little help with breaking down into pseudo-code, and while I haven't been provided with the partition function code, I'd like to understand what it would do given the quickselect function provided.

我知道如何快速排序工作，只是没有quickselect。我刚才提供的code是我们如何快速格式化选择给予一个例子。

I know how quicksort works, just not quickselect. The code I just provided is an example we were given on how to format quick select.

编辑：纠正code是

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

Courtesty：@Haitao

Courtesty: @Haitao

推荐答案

在快速选择最重要的部分就是分区。因此，让我解释一下，第一。

The important part in quick select is partition. So let me explain that first.

分区快速选择纬透视（无论是随机还是第一个/最后一个元素）。然后，它重新排列的方式，小于枢轴的所有元素都在枢轴的左侧和其他人在右边的列表。然后，它返回透视元素的索引。

Partition in quick select picks a pivot (either randomly or first/last element). Then it rearranges the list in a way that all elements less than pivot are on left side of pivot and others on right. It then returns index of the pivot element.

现在我们在这里发现第k个最小元素。之后的分区情况是：

Now here we are finding kth smallest element. After partition cases are:

1. K ==透视。那么你已经找到第k个最小的。这是因为，这样的分区是工作。正好有 K - 1 元素比第k 元素小
2. K＆LT;透视。那么第k个最小的是透视的左侧。
3. K＆GT;透视。然后第k个最小的是在右侧的枢轴。而要找到它，你实际上必须要找到 K-支点最小数量的权利。

1. k == pivot. Then you have already found kth smallest. This is because the way partition is working. There are exactly k - 1 elements that are smaller than the kth element.
2. k < pivot. Then kth smallest is on the left side of pivot.
3. k > pivot. Then kth smallest is on the right side of pivot. And to find it you actually have to find k-pivot smallest number on right.

这篇关于QuickSelect算法理解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！