QuickSelect算法了解

Question

我一直在研究讨论快速排序和快速选择的各种教程和文章，但是我对它们的理解依然不稳定。

鉴于此代码结构，我需要能够掌握和解释quickselect的工作原理。

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

我需要分解成伪码一点点帮助，虽然我还没有具备分区功能代码，我想了解它会做给提供的quickselect功能。

我知道quicksort是如何工作的，只是没有快速选择。我刚刚提供的代码是我们给出的关于如何格式化快速选择的示例。

编辑：纠正代码

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

Answer 1

中快速选择是分区中的重要组成部分。所以让我先解释一下。

快速选择分区选择一个pivot（随机或第一个/最后一个元素）。然后重新排列列表，使所有小于pivot的元素位于枢轴的左侧，其他位于右侧。然后它返回pivot元素的索引。

现在我们在这里找到第k个最小的元素。分区案例如下：

1. k == pivot。那么你已经找到了第k个最小的。这是因为分区的工作方式。确切地说有k - 1元素比kth元素小。
2. k < pivot。然后第k个最小的在pivot的左侧。
3. k > pivot。然后第k个最小的是在枢轴的右侧。要找到它，你实际上必须在右边找到k-pivot最小的数字。

Answer 2

分区非常简单：它重新排列元素，使得小于所选透视的元素在数组中的位置低于透视，而那些大于透视的元素在数组中的高点处。

我谈到了其余的一个previous answer。

Answer 3

顺便说一句，你的代码有一些错误..

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

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

} 

//分区功能一样快速排序

Answer 5

可以使用3路分区找到quickSelect here。

代码是用Scala编写的。另外，我将在我掌握这个主题的旅程中添加更多的算法和数据结构。

您还可以注意到，使用quickSelect实现了奇数个元素的数组有一个中值函数。

编辑：这需要洗牌的阵列，以保证线性平均运行时间

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