文章/答案/技术大牛

发布

社区首页 >问答首页 >为什么我的Shell排序这么慢

问为什么我的Shell排序这么慢
EN

Stack Overflow用户

提问于 2017-09-17 16:47:16

回答 1查看 101关注 0票数 0

我正在尝试自己实现shell排序算法。我写了自己的代码，没有看任何代码样本，只看the video of algorithm description

我的排序工作很慢(冒泡排序100项- 0.007秒；外壳排序100项- 4.83秒)，怎么可能改进它？

void print(vector<float>vec)
{
    for (float i : vec)
    cout << i << " ";
    cout << "\n\n";
}

void Shell_sorting(vector<float>&values)
{
    int swapping = 0;
    int step = values.size();
    clock_t start;
    double duration;
    start = clock();

    while (step/2 >= 1)
    {
        step /= 2;
        for (int i = 0; i < values.size()-step; i++)
        {
            if ((i + step < values.size()))
            {
                if ((values[i + step] < values[i]))
                {
                    swap(values[i], values[i + step]);
                    print(values);
                    ++swapping;
                    int c = i;
                    while (c - step > 0)
                    {
                        if (values[c] < values[c - step])
                        {
                            swap(values[c], values[c - step]);
                            print(values);
                            ++swapping;
                            c -= step;
                        }
                        else
                            break;
                    }
                }
            }
            else
                break;
        }
    }
    duration = (clock() - start) / (double)CLOCKS_PER_SEC;
    print(values);
    cout << swapping << "  " << duration;
    print(values);
}

algorithm

sorting

c++

回答 1

Stack Overflow用户

发布于 2017-09-17 18:34:36

更好的实现可能是：

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec = {
                            726,621,81,719,167,958,607,130,263,108,
                            134,235,508,407,153,162,849,923,996,975,
                            250,78,460,667,654,62,865,973,477,912,
                            580,996,156,615,542,655,240,847,613,497,
                            274,241,398,84,436,803,138,677,470,606,
                            226,593,620,396,460,448,198,958,566,599,
                            762,248,461,191,933,805,288,185,21,340,
                            458,592,703,303,509,55,190,318,310,189,
                            780,923,933,546,816,627,47,377,253,709,
                            992,421,587,768,908,261,946,75,682,948,
                            };

    std::vector<int> gaps = {5, 2, 1};
    int j;

    for (int gap : gaps) {
        for (int i = gap; i < vec.size(); i++) 
        {
            j = i-gap;
            while (j >= 0) {
                if (vec[j+gap] < vec[j])
                {
                    int temp = vec[j+gap];
                    vec[j+gap] = vec[j];
                    vec[j] = temp;
                    j = j-gap;
                }
                else break;
            }
        }
    }

    for (int item : vec) std::cout << item << " " << std::endl;

    return 0;
}

我更喜欢使用向量来存储间隙数据，这样您就不需要计算除法(这是一个扩展操作)。此外，这种选择使您的代码具有更大的灵活性。

外部循环对间隙值进行循环。一旦选择了gap，你就可以迭代你的向量，从vec[gap]开始，根据外壳排序的逻辑探索是否有比它小的元素。

因此，您开始设置j=i-gap并测试if条件。如果为真，则交换项目，然后重复while循环递减j。注意：：vec[j+gap]是在最后一个循环周期中被交换的元素。如果条件为真，则没有理由继续循环，因此可以使用break退出循环。

在我的机器上，使用time外壳命令计算的时间为0.002秒(包括打印数字的过程)。

附注：为了生成所有这些数字并将它们写入数组，因为我懒得编写随机函数，所以我使用this link，然后在shell中使用以下命令编辑输出：

sed -e 's/[[:space:]]/,/g' num | sed -e 's/$/,/'

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/46262239

复制

相似问题

问为什么我的Shell排序这么慢
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么我的Shell排序这么慢EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么我的Shell排序这么慢
EN