如何在C++中实现快速排序算法

Question

这里是来自MITOcw（算法导论）讲座的快速排序算法。

QUICKSORT(A,p,q)
if(p < q)
then r = PARTITION(A,p,q)
     QUICKSORT(A,p,r-1)
     QUICKSORT(A,r+1,q)

PARTITION(A,p,q)
x = A[p]
i=p
for j = p+1 to q
    if A[j] <= x
       then i = i+1
            swap A[i] with A[j]
swap A[p] with A[i]
return i

以下是针对一个整数数组的C++实现：

#include <iostream>

using namespace std;

void quickSort(int *,int,int);

int partition(int *, int,int);

int main()
{
    int A[10]={6,10,13,5,8,3,2,25,4,11};
    int p=0,q=10;

    cout<<"======Original======="<<endl;
    for(int f=0; f<10; f++)
        cout<<A[f]<<endl;

    quickSort(A,p,q);

    cout<<"======Sorted======="<<endl;
    for(int f=0; f<10; f++)
        cout<<A[f]<<endl;
}


void quickSort(int *A, int p,int q)
{
    int r;
    if(p<q)
    {
        r=partition(A, p,q);
        quickSort(A,p,(r-1)); //I think the problem is here this first quickSort call
                              // is reducing the value of r and hence value of q becomes
                              // less than p recursively. How can I separate both calls
                              // one for left and one for right sub array of the pivot. 
        quickSort(A,(r+1),q);
    }
}


int partition(int *A, int p,int q)
{
    int x= A[p];
    int i=p;
    int temp;
    int j;

    for(j=p+1; j<q; j++)
    {
        if(A[j]<=x)
        {
            i=i+1;
            temp= A[j];
            A[j]=A[i];
            A[i]=temp;
        }

    }

    temp= A[p];
    A[p]=A[i];
    A[i]=temp;

    return i;
}

尽管quickSort函数的前两次运行输出符合预期，但代码并没有生成已排序的数组。这是因为它将第一个枢轴元素放置到其正确的位置。

- Udit Bhardwaj

Answer 1

您的考虑是错误的。由于r作为值传递给快速排序函数（而不是引用），因此其值不会改变。

您使用p和q来处理范围，其中p是范围内的第一个索引，而q是范围内不是的第一个索引。

因此，您的调用是错误的：

r=partition(A, p,q);
quickSort(A,p,r); //range is from A[p] to A[r-1] 
quickSort(A,(r+1),q); //range is from A[r+1] to A[q-1]

以下是完整的示例。我使用了std::swap来更改元素，并使用ans std::vector代替数组。

#include <iostream>
#include <vector>

using namespace std;

void quickSort(vector<int>&,int,int);

int partition(vector<int>&, int,int);

int main()
{
    vector<int> A = {6,10,13,5,8,3,2,25,4,11};
    int p=0;
    int q=10;

    cout<<"======Original======="<<endl;
    for(auto e: A)
        cout<< e <<" ";
    cout<< endl;    

    quickSort(A,p,q);

    cout<<"======Sorted======="<<endl;
    for(auto e: A)
        cout<< e <<" ";
    cout<< endl;   
}


void quickSort(vector<int>& A, int p,int q)
{
    int r;
    if(p<q)
    {
        r=partition(A, p,q);
        quickSort(A,p,r);  
        quickSort(A,r+1,q);
    }
}


int partition(vector<int>& A, int p,int q)
{
    int x= A[p];
    int i=p;
    int j;

    for(j=p+1; j<q; j++)
    {
        if(A[j]<=x)
        {
            i=i+1;
            swap(A[i],A[j]);
        }

    }

    swap(A[i],A[p]);
    return i;
}

Live example: ideone

- tgmath

---

嗨，我正在尝试理解这个算法，什么是枢轴？如果我更改p或q的值，算法就无法对整个数组进行排序。 - D1X

@D1X A[p] 是轴元素。由于 p 是需要排序的数组部分的左边界，因此轴元素始终是第一个元素。只有索引在 p 和 q 之间的数组部分会被排序。 - tgmath

为什么 q=10，而 p 仍然等于0？ - Abhinav Gauniyal

@AbhinavGauniyal 数组有10个元素，我们想要完全排序它。p是范围内的第一个索引，而q则不在范围内。因此，值为p=0和q=10。 - tgmath

@tgmath，我在不同的上下文中使用了p和q，谢谢您的解释 :) - Abhinav Gauniyal

Answer 2

这是一种基于模板的解决方案。然而，目前它仅适用于元素数组。如果有人能将其改进为通用于数组和STL容器，请做出贡献。

template<typename T, typename compare = std::less<T>>
void q_sort(T input[], int l_idx, int r_idx, compare comp = compare()) {

    if (l_idx >= r_idx)
        return;

    // The below is the partition block (can be made a sub function)

    int left = l_idx;
    int right = r_idx;
    {
        int pivot_idx = l_idx;
        T pivot = input[pivot_idx];

        while (left < right) {
            while (comp(input[left], pivot))
                left++;
            while (comp(pivot, input[right]))
                right--;
            swap(input[left], input[right]);
        }

        swap(pivot, input[left]);
    }

    q_sort(input, l_idx, left, comp);
    q_sort(input, left+1, r_idx, comp);

}

template<typename T, typename compare = std::less<T>>
void quick_sort(T array[], int N, compare comp = compare()) {
    // This is an improvisation on the merge sort algorithm
    // is in-place and works on the divide-and-conquer methodology
    // Choose a pivot and find its appropriate place, such that
    // All elements less than the pivot are on its left and all elements
    // greater are on its right. Once found, split the porlblem into subsets
    // of elements less than and greater than the pivot and recursively
    // follow the process.
    q_sort(array, 0, N-1, comp);

}

int main()
{

    int input[] = {11, 6, 3, 21, 9, 12};
    std::cout << "Before : ";
    for (int i=0; i < 6; i++)
        std::cout << input[i] << " ";
    std::cout << std::endl;

    quick_sort(input, 6);
    // or 
    //quick_sort(input, 6, std::greater<int>());

    std::cout << "After : ";
    for (int i=0; i < 6; i++)
        std::cout << input[i] << " ";
    std::cout << std::endl;

}

- J. Doe

---

我猜你的实现中有一个bug。我用你的代码处理了一个随机整数数组，但程序在某个地方卡住了... - HarryLeong

Answer 3

一个更简单和清晰的实现，还可以给你快速排序中最小交换次数的数量。

int quickSort(int[], int, int);

int partition(int[], int, int, int&);

int main()
{
    int array[] = {4, 2, 5};
    int size = sizeof(array)/sizeof(array[0]);

    /*
     first and last indices are passed
     idea is to move lower elements to the left of the list/pivot
     */

    int swaps = quickSort(array, 0, size-1);

    std::cout << "Minimum Swaps are: " << swaps << std::endl;

    for(int i = 0; i < size; i++)
    {
        std::cout << array[i] << " ";
    }
}

int quickSort(int array[], int start, int end)
{
    int swaps = 0;
    if(start < end)
    {
        int pIndex = partition(array, start, end, swaps);
        //after each call one number(the PIVOT) will be at its final position
        swaps += quickSort(array, start, pIndex-1);
        swaps += quickSort(array, pIndex+1, end);
    }
    return swaps;
}

int partition(int array[], int start, int end, int& swaps)
{
    int pivot = array[end];
    int pIndex = start;

    for(int i = start; i < end; i++)
    {
        if(array[i] <= pivot)
        {

            if(pIndex != i)
            {
                std::swap(array[i], array[pIndex]);
                swaps++;
            }
            pIndex++;
        }
    }
    if(pIndex != end)
    {
        std::swap(array[pIndex], array[end]);
        swaps++;
    }
    return pIndex;
}

- Rupinder Ghotra

Answer 4

鉴于我看到了各种不同的答案，你可以尝试这个：

#include <iostream>

void quickSort(int a[], int first, int last);
int pivot(int a[], int first, int last);
void swap(int& a, int& b);
void swapNoTemp(int& a, int& b);
void print(int array[], const int& N);

using namespace std;

int main()
{
    int test[] = { 7, -13, 1, 3, 10, 5, 2, 4 };
    int N = sizeof(test)/sizeof(int);

    cout << "Size of test array :"  << N << endl;

    cout << "Before sorting : " << endl;
    print(test, N);

    quickSort(test, 0, N-1);

    cout << endl << endl << "After sorting : " << endl;
    print(test, N);

    return 0;
}

/**
 * Quicksort.
 * @param a - The array to be sorted.
 * @param first - The start of the sequence to be sorted.
 * @param last - The end of the sequence to be sorted.
*/
void quickSort( int a[], int first, int last ) 
{
    int pivotElement;

    if(first < last)
    {
        pivotElement = pivot(a, first, last);
        quickSort(a, first, pivotElement-1);
        quickSort(a, pivotElement+1, last);
    }
}

/**
 * Find and return the index of pivot element.
 * @param a - The array.
 * @param first - The start of the sequence.
 * @param last - The end of the sequence.
 * @return - the pivot element
*/
int pivot(int a[], int first, int last) 
{
    int  p = first;
    int pivotElement = a[first];

    for(int i = first+1 ; i <= last ; i++)
    {
        /* If you want to sort the list in the other order, change "<=" to ">" */
        if(a[i] <= pivotElement)
        {
            p++;
            swap(a[i], a[p]);
        }
    }

    swap(a[p], a[first]);

    return p;
}

我在快速排序（C ++）中有它。

- gsamaras