快速排序算法和快速选择算法有什么区别?

Question

除了仅搜索数组的一侧，快速排序和快速选择之间是否有区别？

Answer 1

一个区别是，由于在每个级别上仅搜索一个分区，因此可以使用迭代代替递归。使用Lomuto分区方案示例代码。更好的枢轴选择(而不是[HI](将根据数据模式有助于。

int QuickSelect(int a[], int sz, int k)
{
    int lo = 0;
    int hi = sz-1;              // (no check for empty array)
    while (lo < hi){
        int p = a[hi];          // Lomuto partition
        int i = lo;
        for (int j = lo; j < hi; ++j){
            if (a[j] < p){
                std::swap(a[j], a[i]);
                ++i;
            }
        }
        std::swap(a[i], a[hi]);
        if (k == i)             // if pivot == kth element, return it
            return a[k];
        if (k < i)              // loop on partition with kth element
            hi = i - 1;
        else
            lo = i + 1;
    }
    return a[k];                // sorted to kth elemement, return it
}

Answer 2

两种算法都是划分的，并征服了托尼·霍尔(Tony Hoare(创建的任何算法。

在机器人算法中，我们将枢轴元素的数组分为两个数组。

[el-1,el-2,....el-pivot,.......,el-last]

我们知道" el-pivot"左侧的元素。小于" el-pivot"但是他们没有分类。因此，我们将快速排序以快速排序算法应用于两个子阵列

在快速选择中，我们不会对数组进行排序。快速选择算法专门用于查找数组中的kth最小元素。我们知道，El-Pivot左侧的所有元素都比El-Pivot小，因此我们不在乎对左侧进行排序，因此我们不划分左侧。这将复杂性从O(NLOG2(n((降低到O(n(