SuzumiyaSAMA
2017-01-26 02:32
采纳率: 92.3%
浏览 1.2k

一个快排的测试程序,但是没办法实现,求解答

代码:

 #include <iostream>
#include <vector>
#include <cstdbool>
using namespace std;

bool SwitchInt (int& a, int &b){
    if (a == b) return true;
    a += b;
    b = a - b;
    a -= b;
    return true;
}

bool QuickSort (vector<int> &ivec, vector<int>::iterator small, vector<int>::iterator big){
    if (small == big) return true;
    vector<int>::iterator start = small;
    vector<int>::iterator end = big;
    vector<int>::iterator flag = small;
    while (small != big){
        if (*small > *flag){
            SwitchInt(*small, *flag);
            flag = small;
            small++;
            continue;
        }
        if (*big < *flag){
            SwitchInt(*big, *flag);
            flag = big;
            big--;
            continue;
        }
    }
    QuickSort(ivec, start, small);
    QuickSort(ivec, big, end);
    return true;
}

int main (void){
    vector<int> ivec;
    int num = 0;
    while (cin >> num){
        ivec.push_back(num);}
    QuickSort(ivec, ivec.begin(), ivec.end());
    for (int num: ivec)
        cout << num;
    return 0;
}

运行时有指针超界的错误,但是我检查不出来

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • GKatHere 2017-02-08 10:21
    已采纳
    
    //
    //  bool SwitchInt (int& a, int &b){
    //      if (a == b) return true;
    //      a += b;
    //      b = a - b;
    //      a -= b;
    //      return true;
    //  }
    //  标准SWAP方法, 比上面的更快
    void SwitchInt (int& a, int &b){
        int t =a;
        a=b;
        b=t;
    }
    
    //  vector<int> &ivec 参数无用,去掉
    //  bool 返回值无用,去掉
    //  big 使用标准库end语法
    /*bool*/ void QuickSort (/*vector<int> &ivec,*/ vector<int>::iterator small, vector<int>::iterator big)
    {
        if (small == big) return /*true*/;
        vector<int>::iterator start = small;
        vector<int>::iterator end = big;
        vector<int>::iterator flag = small;
        //随机选取flag, 将小于等于此值的放在左边,大于此值的放于右边
        for (small++; small != big; small++){
            if (*small <= *flag){
                SwitchInt(*small, *flag);
                flag++;
                SwitchInt(*small, *flag);
    
                //           flag = small;
                //           small++;
                //           continue;
            }
            //       if (*big < *flag){
            //           SwitchInt(*big, *flag);
            //           flag = big;
            //           big--; 
            //           continue;
            //       }
    
        };
    
    
        cout  << &*start << ' ' << &*flag << ' ' <<  '\n';
        //QuickSort(/*ivec,*/ start, small);
        QuickSort(/*ivec,*/ start, flag);
        // QuickSort(/*ivec,*/ big, end);
        QuickSort(/*ivec,*/ ++flag, end);
    
    
        return /*true*/;
    }
    
    
    
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
        srand(time(0));
    
        vector<int> ivec;
        int num = 0;
        //     while (cin >> num){
        //         ivec.push_back(num);}
        for (int n=0; n<10; n++)
        {
            cout << (num = rand()) << " ";
            ivec.push_back(num);
        }
        cout << "\n";
    
        QuickSort(/*ivec,*/ ivec.begin(), ivec.end());
        for_each(ivec.begin(), ivec.end(),
            [](int num){ cout << num << " ";});
    
    
        getchar();
        return 0;
    }
    
    
    已采纳该答案
    打赏 评论
  • Houchaoqun_XMU 2017-01-26 07:19

    博主你好,首先建议你详细的看看C++中Vector的用法哈,本文中一个严重的错误是,“QuickSort(ivec, ivec.begin(), ivec.end());”这个语句中,ivec.end()并不是指向用户输入的最后一个数字,而是“数组的最后一个单元+1的指针”。所以,此处你应该改为“QuickSort(ivec, ivec.begin(), ivec.end()-1);”。这个可以解决指针越界,程序不知道还有没有其他错误,有的话再提出看看。

    打赏 评论
  • Houchaoqun_XMU 2017-01-26 07:23

    再者,你的程序逻辑可能也有问题。你输入“4 2 1 3”(再随便以一个不是数字的字符作为结束),你的程序会陷入死循环。

    打赏 评论
  • Eleven 2017-02-03 06:27
     #include <iostream>
    #include <vector>
    #include <cstdbool>
    using namespace std;
    
    bool SwitchInt(int& a, int &b) {
        if (a == b) return true;
        a += b;
        b = a - b;
        a -= b;
        return true;
    }
    
    int Partition(vector<int> &vi, int low, int up)
    {
        int pivot = vi[up];
        int i = low - 1;
        for (int j = low; j < up; j++)
        {
            if (vi[j] <= pivot)
            {
                i++;
                SwitchInt(vi[i], vi[j]);
            }
        }
        SwitchInt(vi[i + 1], vi[up]);
        return i + 1;
    }
    
    void QuickSort(vector<int> &vi, int low, int up)
    {
        if (low < up)
        {
            int mid = Partition(vi, low, up);
            QuickSort(vi, low, mid - 1);
            QuickSort(vi, mid + 1, up);
        }
    }
    
    int main(void) {
        vector<int> ivec;
        int num = 0;
        while (cin >> num){
            ivec.push_back(num); 
        }
        cout << ivec.size() << endl;
        QuickSort(ivec, 0, ivec.size() - 1);
        for (auto num : ivec)
            cout << num <<"," ;
        cout << endl;
        return 0;
    }
    
    打赏 评论

相关推荐 更多相似问题