C++中的插入排序

Question

来自维基百科：

插入排序迭代，每次重复使用一个输入元素，并生成一个排序输出列表。每次迭代，插入排序从输入数据中删除一个元素，找到它在排序列表中的位置，然后插入到那里。它会重复执行，直到没有任何输入元素。排序通常是就地完成的，方法是迭代数组，在数组后面增加排序列表.在每个数组位置，它根据排序列表中的最大值检查那里的值(恰好在它旁边，在前面的数组位置选中)。如果更大，则将元素留在适当的位置并移动到下一个元素。如果较小，则在排序列表中找到正确的位置，将所有较大的值向上移动以生成一个空格，并插入到正确的位置。

刚刚在C++中试用了我的解决方案：

#include <vector>

std::vector<int> ins_sort(std::vector<int> series)
{
    for(int i=1; i<series.size(); i++)
    {
        int key = series[i];
        for(int j=i-1; j>-1; j--)
        {
            if (key < series[j])
            {
                series[j+1] = series[j];
                series[j] = key;
            }
            else break;
        }
    }
    return series;
}

Answer 1

我不建议按值传递和返回向量。通过引用传递，而且根本不返回-通常排序都是在适当的地方完成的。

另一个一般性建议：没有原始循环。内部循环完成了一些重要的工作，这必须得到实现，并给出一个正确的名称，insert。

typedef std::vector<int>::size vsize_t;
void ins_sort(std::vector<int> & series)
{
    for(vsize_t i=1; i < series.size(); i++)
    {
        insert(series, i, series[i]);
    }
}

void insert(std::vector<int> & series, vsize_t last, int key)
{
    for (vsize_t j = last - 1; j > -1; --j)
    {
        if (key < series[j]) {
            series[j + 1] = series[j];
            series[j] = key;
        }
        else
            break;
    }
}

现在，通过消除j并将两个条件检查组合在一起，可以简化逻辑：

void insert(std::vector<int> & series, vsize_t last, int key)
{
    while ((--last > -1) && (key < series[last]))
    {
        series[last + 1] = series[last];
        series[last] = key;
    }
}

您可以看到series[last] = key;分配是多么的多余--它在下一次迭代中必然会被覆盖，因此只有在最后一次迭代时才有意义：

void insert(std::vector<int> & series, vsize_t last, int key)
{
    while ((--last > -1) && (key < series[last]))
    {
        series[last + 1] = series[last];
    }
    series[last] = key;
}

在每次迭代中测试两个条件是昂贵的。您可能会注意到，只有当键小于所有元素时，第一个条件才会触发，换句话说，它小于series[0] (它已经排序到要点了)：

void insert(std::vector<int> & series, vsize_t last, int key)
{
    if (key < series[0]) {
        while (last-- > 0) {
            series[last+1] = series[last];
        }
    } else {
        while (key < series[last])
        {
            series[last+1] = series[last];
        }
    }
    series[last] = key;
}

再应用规则一次，我们看到第一个循环向右移动1，第二个循环不受保护地向右移动1。

把一切结合起来，我们得到：

typedef std::vector<int>::size vsize_t;
vsize_t unguarded_shift(std::vector<int> & series, vsize_t last, int key)
{
    while (key < series[last--])
    {
        series[last + 1] = series[last];
    }
    return last;
}

vsize_t shift(std::vector<int> & series, vsize_t last)
{
    while (last-- > 0) {
        series[last+1] = series[last];
    }
    return last;
}


void insert(std::vector<int> & series, vsize_t last, int key)
{
    if (key < series[0]) {
        last = shift(series, last);
    } else {
        last = unguarded_shift(series, last, key);
    }
    series[last] = key;
}



void ins_sort(std::vector<int> & series)
{
    for(vsize_t i=1; i < series.size(); i++)
    {
        insert(series, i, series[i])
    }
}

Answer 2

• 这里有更多的空格: for(int j=i-1；j>-1；j--)可以帮助提高可读性，特别是当浏览它时: for (int j=i-1；j> -1；j-)
• 这一行:否则中断；可以使用花括号，至少要保持一致性:否则{坏；}
• 对于循环计数器类型，使用std::vector::size_type而不是int，特别是size()。您不能保证int足够大，特别是在对许多元素进行排序的情况下。由于它们都使用这种类型，所以更倾向于在存储容器中使用std::size_type。为了简洁起见，您可以使用std::size_t作为std::size_type通常只是typedef其中之一。