快速排序的问题 - 编程论坛

#2

pangding2012-10-12 13:28

选好参考点之后怎么扫都无所谓吧，不知楼主是觉得那里不好处理。
只要递归到下次之前可以把数组弄成前边的都比支点元素小，后面都大就行了。

#3

senpujituan2012-10-12 16:06

我开始选的是第一个作为参考点，然后从左往右扫，排是排出来了，但是数值很多都相同的。但是从右往左时是ok的。思路嘛也是想
小的放左边，大的放右边。错误代码如下

程序代码：

void Quicksort(int b[], int low, int high)
{
    int i,j;
    int t;
    if(low<=high)
    {
        t=b[low];
        i=low;
        j=high;
        while(i!=j)
        {
                while(i<j&&b[i]<=t)
                i++;
                if(j>i)
                {
                    b[j]=b[i];
                    j--;
                }

                while(i<j&&b[j]>=t)
                j--;
                if(j>i)
                {
                    b[i]=b[j];
                    i++;
                }
        }
        b[i]=t;
        Quicksort(b,low,i-1);
        Quicksort(b,i+1,high);
    }
}

：

#4

寒风中的细雨2012-10-12 21:28

程序代码：

     1    //bccn.cpp
     2    #include <iostream>
     3    #include <algorithm>
     4    #include <iterator>
     5    #include <fstream>
     6    #include <vector>
     7    using namespace std;
     8
     9    void swap(int &a, int &b)
    10    {
    11        a += b;
    12        b = a - b;
    13        a = a - b;
    14    }
    15
    16    void qsort(vector<int> &ivec, size_t low, size_t high)
    17    {//保证参数的合法性
    18        if (low >= high)
    19        {
    20            return;
    21        }
    22
    23        size_t i = low, j = high;
    24        size_t comp = ivec[low];
    25
    26        while (i<j)
    27        {
    28            while (i<j && comp<ivec[j])
    29            {//找到第一小于的数
    30                --j;
    31            }
    32            if (i < j)
    33            {
    34                swap(ivec[i], ivec[j]);
    35                ++i;
    36            }
    37            while (i<j && comp>ivec[i])
    38            {//找到第一大于的数
    39                ++i;
    40            }
    41            if (i < j)
    42            {
    43                swap(ivec[i], ivec[j]);
    44                --j;
    45            }
    46        }
    47        qsort(ivec, low, i?i-1:min(i-1, low));
    48        qsort(ivec, i+1, high);
    49    }
    50
    51    int main(int argc, char **argv)
    52    {
    53        if (2 != argc)
    54        {
    55            cout << string("argc != 2") << endl;
    56            return -1;
    57        }
    58
    59        ifstream fin(argv[1]);
    60        istream_iterator<int> beg(fin), end;
    61        ostream_iterator<int> out(cout, " ");
    62        vector<int> ivec;
    63
    64        while (beg != end)
    65        {
    66            ivec.push_back(*beg);
    67            ++beg;
    68        }
    69        cout << string("before sort:");
    70        copy(ivec.begin(), ivec.end(), out);
    71        cout << endl << string("after sort:");
    72    //    sort(ivec.begin(), ivec.end());
    73        qsort(ivec, 0, ivec.size()-1);
    74        copy(ivec.begin(), ivec.end(), out);
    75        cout << endl;
    76
    77        return 0;
    78    }

#5

青春无限2012-10-12 21:43

学习

#6

senpujituan2012-10-13 08:48

回复 4楼寒风中的细雨

我知道我错的原因，就是改为从右往左扫就可以了。选一个元素为参考点，从左往右的话，假如碰到满足条件的，把它放最后
就把原来最后的元素覆盖了，所以排序是对了，就是重复的数字很多。

也许，还真只能先从右往左吧。

#7

senpujituan2012-10-13 08:49

回复 4楼寒风中的细雨

误解你的了，原来你用了交换，谢谢！！

#8

张浩5212012-10-13 09:39

和你一样啊

#9

寒风中的细雨2012-10-13 11:38

回复 6楼 senpujituan

为什么从右开始往左？

如果从左开始那第一次肯定是不成立的因为是从下标值最小的开始比较所以两个值是相同的 comp==a[i]
所以为了效率就从右边开始找