2

基本的なクイック ソート アルゴリズムを実装しようとしましたが、正しく実装できたと思います。ただし、関数は配列にはまったく影響しません。考えられる理由は何ですか？何が問題なのかわからなかったので、ここで仲間のプログラマーに相談することにしました。

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int> A,int low,int high)
{
    int pivot=A[high-1];
    int boundryForLowerArray=low-1;
    for(int i=low;i<high-2;i++)
    {
        if(A[i]<=pivot)
        {
            boundryForLowerArray++;
            swap(A[i],A[boundryForLowerArray]);
        }
    }
    swap(pivot,A[boundryForLowerArray+1]);
    return boundryForLowerArray+1;
}
void quickSort(vector<int>A,int low,int high)
{
    if(low<high)
    {
        int q=partition(A,low,high);
        quickSort(A, low, q-1);
        quickSort(A, q+1, high);
    }
}


int main(int argc, const char * argv[])
{

    vector<int>A,sorted;
    A.push_back(2);
    A.push_back(8);
    A.push_back(7);
    A.push_back(1);
    A.push_back(3);
    A.push_back(5);
    A.push_back(6);
    A.push_back(4);
    quickSort(A, 0, A.size());
    for(int i=0;i<A.size();i++)
        cout<<A[i]<<" ";
    return 0;
}
4

2 に答える 2

5

A を参照ではなく値で渡しているためquickSort、A のコピーを作成して並べ替えています。代わりに、ベクトルを参照渡ししてみてください。

int partition(vector<int>& A,int low,int high)

... と

void quickSort(vector<int>& A,int low,int high)
于 2012-04-25T17:58:14.083 に答える
0

参照ではなく値でパラメータを渡すためです。実際には、配列の開始と終了のイテレーター（vec.begin（）、vec.end（））をパラメーターとして持つ関数が必要です。さらに、アルゴリズムはあらゆる種類のイテレータを受け入れる必要があります。したがって、テンプレートを使用する必要があります。

template<class Iterator>
void quick_sort(Iterator begin, Iterator end) { 
   for(auto iter = begin;iter != end;iter++) 
      *iter; // access to the value of the iterator
于 2012-04-25T18:04:27.783 に答える