8

我正在尝试这样简单的事情：

template<class T>
array insertionSort(array<T> arr) {

    for (int index = 1; index < arr.size(); index++) {
        for (int insertion = index; insertion > 0 && array[insertion - 1] > array[insertion]; insertion--) {
            std::swap(array[insertion - 1], array[insertion]);
        }
    }

    return arr;
}

void main() {
    array<int, 10> mine = { 1, 0, 2, 9, 3, 8, 4, 7, 5, 6 };

    array result = insertionSort<int>(mine);

    cin.get();
}

似乎数组需要两个类型参数（type以及size），那么如何在不知道前面大小的情况下将它传递给函数和从函数传递呢？

4

3 回答 3

20

一般来说，你真的不想传递容器！适用于的相同算法std::array<T, N>也适用于其他数据结构，例如，std::vector<T>或std::deque<T>。在这种情况下，C++ 方法是传递迭代器并[稍微]调整算法：

template<typename BidrectionalIterator>
void insertionSort(BidirectionalIterator begin, BidirectionalIterator end) {
    for (BidirectionalIterator it(begin); it != end; ++it) {
        for (BidirectionalIterator insertion(it), tmp(insertion);
             begin != insertion && *--tmp > *insertion; --insertion) {
             std::swap(*tmp, *insertion);
        }
    }
}

（我没有验证算法是否真的有效，但你明白了）。

请注意，该算法故意对序列进行就地排序！如果要创建排序副本，请创建副本并对其进行排序：这样，您可以选择是否就地进行，而不是被迫使用可能需要过多内存的方法（好的，当序列是大你肯定不想使用这个算法，但这是一个单独的问题）。

于 2013-08-28T02:08:07.787 回答
10

它的工作方式与在不预先知道类型的情况下传递对象相同。您使用模板参数：

template<class T, size_t arrSize>
std::array<T, arrSize> insertionSort(std::array<T, arrSize> arr) {

    for (int index = 1; index < arrSize; index++) {
        for (int insertion = index; insertion > 0 && array[insertion - 1] > array[insertion]; insertion--) {
            std::swap(array[insertion - 1], array[insertion]);
        }
    }

    return arr;
}
于 2013-08-28T01:56:29.473 回答
3

IMO，您应该只将大小作为模板参数传递并在循环中使用它而不是 arr.size()：

template<class T, size_t size>
array<T, size> insertionSort(array<T> arr) {

    for (int index = 1; index < size; index++) {
        for (int insertion = index; insertion > 0 && array[insertion - 1] > array[insertion]; insertion--) {
            std::swap(array[insertion - 1], array[insertion]);
        }
    }

    return arr;
}

void main() {
    array<int, 10> mine; mine.fill(0);

    array<int, mine.size()> result = insertionSort<int, mine.size()>(mine);

    cin.get();
}
于 2013-08-28T01:58:09.307 回答