我已经实现了快速选择算法。

我有一个问题,当我在数组中使用重复项时,我的算法最终会陷入无限循环...

你能帮我使它工作吗?

预期的复杂度是O(n),最坏的情况是O(n ^ 2)?

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;

int rand_partition(vector<int> &a, int left, int right) {
    int pivotIndex = left + (rand() % (right - left));
    //int m = left + (right - left) / 2; //... to test the algo...no rand at this point
    int pivot = a[pivotIndex];
    int i = left;
    int j = right;

    do {
        while (a[i] < pivot) i++; // find left element > pivot
        while (a[j] > pivot) j--; // find right element < pivot

        // if i and j not already overlapped, we can swap
        if (i < j) {
            swap(a[i], a[j]);
        }
    } while (i < j);

    return i;
}

// Returns the n-th smallest element of list within left..right inclusive (i.e. n is zero-based).
int quick_select(vector<int> &a, int left, int right, int n) {
    if (left == right) {        // If the list contains only one element
        return a[left];  // Return that element
    }

    int pivotIndex = rand_partition(a, left, right);

    // The pivot is in its final sorted position
    if (n == pivotIndex) {
        return a[n];
    }
    else if (n < pivotIndex) {
        return quick_select(a, left, pivotIndex - 1, n);
    }
    else {
        return quick_select(a, pivotIndex + 1, right, n);
    }
}

int main() {

    vector<int> vec= {1, 0, 3, 5, 0, 8, 6, 0, 9, 0};

    cout << quick_select(vec, 0, vec.size() - 1, 5) << endl;

    return 0;
}

最佳答案

您的代码中有几个问题。

  • 首先,在函数quick_select()中,您正在直接比较pivotIndexn。由于left并不总是为0,因此应该将n与左侧部分的长度进行比较,该长度等于pivotIndex - left + 1
  • n > length时,您只是递归地调用quick_select(a, pivotIndex + 1, right, n),这意味着整个 vector 的第N个元素位于它的右侧,它是第(N-(pivotIndex-left + 1))个元素 vector 的右部分。 该代码应为quick_select(a, pivotIndex + 1, right, n - (pivotIndex - left + 1) )(n基于ONE)。
  • 似乎您正在使用Hoare的分区算法,并且未正确实现它。即使工作正常,当HOARE-PARTITION终止时,它也会返回值j,例如A[p...j] ≤ A[j+1...r],但我们需要A[p...j-1] ≤ A[j] ≤ A[j+1...r]中的quick_select()。所以我使用基于我在another post上写的Lomuto分区算法的rand_partition()

  • 这是固定的quick_select(),它返回 vector 的第N个最小元素(,注意n是基于ONE的)的最小元素:
    int quick_select(vector<int> &a, int left, int right, int n)
    {
        if ( left == right )
            return a[left];
        int pivotIndex = partition(a, left, right);
    
        int length = pivotIndex - left + 1;
        if ( length == n)
            return a[pivotIndex];
        else if ( n < length )
            return quick_select(a, left, pivotIndex - 1, n);
        else
            return quick_select(a, pivotIndex + 1, right, n - length);
    }
    

    thisrand_partition():
    int rand_partition(vector<int> &arr, int start, int end)
    {
        int pivot_index = start + rand() % (end - start + 1);
        int pivot = arr[pivot_index];
    
        swap(arr[pivot_index], arr[end]); // swap random pivot to end.
        pivot_index = end;
        int i = start -1;
    
        for(int j = start; j <= end - 1; j++)
        {
            if(arr[j] <= pivot)
            {
                i++;
                swap(arr[i], arr[j]);
            }
        }
        swap(arr[i + 1], arr[pivot_index]); // swap back the pivot
    
        return i + 1;
    }
    

    首先调用srand()初始化随机数生成器,以便在调用rand()时可以获得类似随机数的数字。
    驱动程序测试以上功能:
    int main()
    {
        int A1[] = {1, 0, 3, 5, 0, 8, 6, 0, 9, 0};
        vector<int> a(A1, A1 + 10);
        cout << "6st order element " << quick_select(a, 0, 9, 6) << endl;
        vector<int> b(A1, A1 + 10); // note that the vector is modified by quick_select()
        cout << "7nd order element " << quick_select(b, 0, 9, 7) << endl;
        vector<int> c(A1, A1 + 10);
        cout << "8rd order element " << quick_select(c, 0, 9, 8) << endl;
        vector<int> d(A1, A1 + 10);
        cout << "9th order element " << quick_select(d, 0, 9, 9) << endl;
        vector<int> e(A1, A1 + 10);
        cout << "10th order element " << quick_select(e, 0, 9, 10) << endl;
    }
    

    10-07 13:47