代码之家 › 专栏 › 技术社区 › William Machado

C语言中只用一个向量作为输入参数的快速排序方法++

quicksort c++

William Machado · 技术社区 · 7 年前

我正在尝试用C++编写一个快速排序方法。我认为我的问题在于:

if( i <= j )

因为这不是比较向量中的值,而是我的索引。我试图使用括号操作符[]访问该值,但代码会消耗内存,不会自行结束。

此外,我更愿意将其保留为一个方法,而不是将其拆分为一个要分区的方法和一个要排序的方法。

排序与其他排序方法一起在其他地方实现。我只是写这篇文章有点困难;我的输入被限制为一个向量。

这就是我所拥有的

vector<double> QuickSort(vector<double> & vec1){

    double i = 0;
    double j = vec1.size()-1;
    int size = vec1.size();
    double tmp;

    double pivot = vec1[(i + j) / 2];

//   partition 

    while (i <= j) {
        while (vec1[i] < pivot)
            i++;
        while (vec1[j] > pivot)
            j--;
        if (vec1[j] <= vec1[j-1]) {
            tmp = vec1[j-1];
            vec1[j-1] = vec1[j];
            vec1[j] = tmp;
            i++;
            j--;
        }
    }

//    recursion 

    if (vec1[i] > vec1[i+1]) {
        QuickSort(vec1);
    }

    if (vec1[j] <vec1[j-1]) {
        QuickSort(vec1);
    }

    return vec1;
}

请提供建议和建议。

3 回复 | 直到 7 年前

Caleth 7 年前

这个 第一条规则 编写递归函数的目的是定义无需执行任何操作的情况。您的代码不会执行此操作,并且假设它永远无法到达。大小为<=1进行真空分拣,并进行测试 vec1[i] > vec1[i+1] 在这样一个向量上是未定义的行为。

这个 第二条规则 编写递归函数的目的是确保在每次内部调用时减少问题的大小。您的代码不会这样做,它会将整个向量传递给自身( 两次 ,如果第一个会回来的话)。

向量不按索引 double s、但是 size_t s(或 int s的符号转换)。

您正在接受 vec1 通过引用,对其进行变异,然后在返回中复制它。做一其中,并非两者都有。

实施自 here

namespace detail {    
    template<class FwdIt, class Compare = std::less<>>
    void QuickSortImpl(FwdIt first, FwdIt last, Compare cmp = Compare{})
    {
        auto const N = std::distance(first, last);
        if (N <= 1) return;
        auto const pivot = *std::next(first, N / 2);
        auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
            return cmp(elem, pivot); 
        });
        auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
            return !cmp(pivot, elem);
        });
        QuickSortImpl(first, middle1, cmp);
        QuickSortImpl(middle2, last, cmp);
    }   
}

void QuickSort(vector<double>& vec1)
{
    detail::QuickSortImpl(vec1.begin(), vec1.end());
}

如果你真的 坚决要求 只有一个函数参数时,可以使用范围库来完成( boost::range 或 range v3 )

template<class Range>
void QuickSort(Range& range)
{
    auto const N = std::distance(range.begin(), range.end());
    if (N <= 1) return;
    auto const pivot = *std::next(range.begin(), N / 2);
    auto left_range = boost::partition<boost::return_begin_found>(
        range.begin(), 
        range.end(), 
        [=](auto const& elem){ 
            return elem < pivot; 
        }
    );
    auto right_range = boost::partition<boost::return_found_end>(
        left_range.end(), 
        range.end(), 
        [=](auto const& elem){ 
            return !(pivot < elem);
        }
    );
    QuickSort(left_range);
    QuickSort(right_range);
}

Junhee Shin 7 年前

我这样修改了你的代码。我决定将透视索引作为最后一项。并添加了一些测试代码。它工作正常。我认为,如果快速排序函数有from、to索引参数,则可以更简单地实现。

#include <iostream>
#include <vector>
#include <chrono>


using namespace std ;

void printvector(vector<double> v) {
cout << "vector : " ;
for (double n : v) {
cout << n << " " ;
}
cout << endl ;
}

vector<double> QuickSort(vector<double>& vec1){

    double i = 0;
    double j = vec1.size()-2;
    double tmp;
    int pivotindex = vec1.size()-1 ;
    double pivot = vec1[pivotindex];

    if ( vec1.size()<=1 )
        return vec1 ;

    cout << "QuickSort: ";
    printvector(vec1) ;

    while (i <= j) {
        while (vec1[i] < pivot) {
            i++;
        }
        while (vec1[j] > pivot)
            j--;
         if (i <= j) {
            tmp = vec1[i];
            vec1[i] = vec1[j];
            vec1[j] = tmp;
            i++;
            j--;
        }
    }
    // pivot change
    vec1[pivotindex] = vec1[i] ;
    vec1[i]=pivot ;
    pivotindex=i ;

    cout << "pivotting: ";
    printvector(vec1) ;

    if (vec1.size()<=2 )
        return vec1 ;
    // partition
    vector<double> left_vec, right_vec ;
    vector<double>::iterator pivotiter = vec1.begin()+pivotindex ;
    copy(vec1.begin(), pivotiter, back_inserter(left_vec)) ;
    copy(pivotiter+1, vec1.end(), back_inserter(right_vec)) ;

    cout << "left: ";
    printvector(left_vec) ;
    cout << "right: ";
    printvector(right_vec) ;

   if (left_vec.size()>0 ) {
        QuickSort(left_vec);
        copy(left_vec.begin(), left_vec.end(), vec1.begin()) ;
    }
   if (right_vec.size()>0 ) {
        QuickSort(right_vec);
        copy(right_vec.begin(), right_vec.end(), pivotiter+1) ;
    }
    return vec1;
}

int main()
{
//vector<double> v { 5 } ;
//vector<double> v { 5, 3 } ;
//vector<double> v { 5, 3, 1 } ;
//vector<double> v { 1, 3, 5 } ;
//vector<double> v { 9,4,8,5,1,2,7 } ;
vector<double> v  ;
//srand( time(NULL) ) ;
int64_t now = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
srand( now ) ;
for (int i=0; i<rand()%30+1; i++) {
    v.push_back( rand()%10000 ) ;
}

cout << "input values: " ;
printvector(v) ;

vector<double> ret = QuickSort(v) ;
cout << "output values: " ;
printvector(ret) ;
cout << endl << endl ;

return 0 ;
}

输出如下。

input values: vector : 1778 9400 9330 783 3148 2029 9685 
QuickSort: vector : 1778 9400 9330 783 3148 2029 9685 
pivotting: vector : 1778 9400 9330 783 3148 2029 9685 
left: vector : 1778 9400 9330 783 3148 2029 
right: vector : 
QuickSort: vector : 1778 9400 9330 783 3148 2029 
pivotting: vector : 1778 783 2029 9400 3148 9330 
left: vector : 1778 783 
right: vector : 9400 3148 9330 
QuickSort: vector : 1778 783 
pivotting: vector : 783 1778 
QuickSort: vector : 9400 3148 9330 
pivotting: vector : 3148 9330 9400 
left: vector : 3148 
right: vector : 9400 
output values: vector : 783 1778 2029 3148 9330 9400 9685

schorsch312 7 年前

我建议使用 std::sort 除非你有很好的理由不这样做。

为了使函数只接受一个参数,一个 std::排序 可能看起来像这样,但您正在复制向量。如果你不喜欢这个,你可以通过引用来传递它。

#include <iostream>   // std::cout
#include <algorithm>  // std::sort
#include <vector>     // std::vector

std::vector<double> mySort(const std::vector<double> unsorted) {
    std::vector<double> sorted = unsorted; 
    std::sort(sorted.begin(), sorted.end()); 
    return sorted;
}

int main() {
    std::vector<double> myvector{32, 71, 12, 45, 26, 80, 53, 33};

    for (const auto item : myvector) {
        std::cout << item << " ";
    }
    std::cout << std::endl;

    auto myvector_sorted = mySort(myvector);

    for (const auto item : myvector_sorted) {
        std::cout << item << " ";
    }
    std::cout << std::endl;

    return 0;
}

然而,实现的底部没有意义,因为

if (vec1[i] > vec1[i + 1]) {
    QuickSort(vec1);
}
if (vec1[j] < vec1[j - 1]) {
    QuickSort(vec1);
}

将始终启动 QuickSort 具有 vec1 。你需要通过 i 和 j 也为了有一个参数接口,您可以编写

vector<double> QuickSort(vector<double> & vec1, int i = 0, int j = vec1.size() - 1 ) {
    int size = vec1.size();
    ....