C++插入排序实现

Question

我想知道是否可以改进插入排序的实现。我做错了什么吗？

template<typename Element>
void insertion_sort(Element arr[], size_t size) {
    size_t index, index_sorted;
    for (index = 0u; index < size; ++index) {
        auto temp = arr[index];
        index_sorted = index - 1;
        while (arr[index_sorted] >= 0 && arr[index_sorted] > temp) {
            arr[index_sorted + 1] = arr[index_sorted--];
        }
        arr[index_sorted + 1] = temp;
    }
}

Answer 1

小淘气

• for循环可以从1开始，因为0的迭代实际上不会做任何事情。
• 如果可能的话，更愿意缩小变量的范围。这允许编译器/优化器进行更好的推理，并使代码更加可读性，因为变量声明更接近实际使用。
• while循环中的check arr[index_sorted] >= 0可能应该是index_sorted >= 0u (毕竟，Element可能无法与整数相比)，但在所有情况下都是true (对于无符号整数类型的-1等于该类型的最大值)。但是，如果第一次迭代从1开始，即使检查这一点也是不必要的。
• 数组元素可能被移动到它们的新位置(在某些情况下这可能会提高性能)。

template<typename Element>
void insertion_sort(Element arr[], size_t size) {
    for (auto index = 1u; index < size; ++index) {
        auto temp = std::move(arr[index]);
        auto index_sorted = index - 1;
        while (arr[index_sorted] > temp) {
            arr[index_sorted + 1] = std::move(arr[index_sorted--]);
        }
        arr[index_sorted + 1] = std::move(temp);
    }
}

从技术上讲，可以通过引用来自动推断数组的大小(尽管它有一个丑陋的语法)。但是，通过使用显式的size参数，可以对部分数组进行排序，因此我更喜欢这种方法的灵活性。