C++中的插入排序

Question

我已经创建了一个插入排序代码来排序数字(很明显)。

#include <iostream>
#include <cstdlib>

void insertion_sort(int arr[], int length);
void print_array(int array[],int size);

int main()
{
    int array[] = {4,6,3,7,5,9,2,8,1,10};
    insertion_sort(array,10);
    print_array(array,10);
    return 0;
}

void insertion_sort(int arr[], int length)
{
    int i,j,tmp;
    for (i = 1; i < length; i++) {
        j = i;
        while (j > 0 && arr[j - 1] > arr[j]) {
            tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
            j--;
        }
    }
}

void print_array(int array[], int size)
{
    int j;
    for (j = 0; j < size; j++)
    {
        std::cout << array[j] << std::endl;
    }
}

有没有办法使它更短或更好？

Answer 1

几件事：

int i，j，tmp；

可以更好地格式化：

int i, j, tmp;

即使这样做也会在两方面受到阻碍：

1. 在需要变量的地方声明变量，而不是在此之前。
2. 单行上的多个声明不是很容易读懂。

事实上，这并不是必要的，正如后面解释的。

int j；for (j = 0；j< size；j++) { std::cout <<数组J << std::endl；}

C++约定的大括号与语句的一行相同：

int j;
for (j = 0; j < size; j++) {
    std::cout << array[j] << std::endl;
}

实际上，第一行可以合并到循环中：

for (int j = 0; j < size; j++) {
    std::cout << array[j] << std::endl;
}

(j >0& arrJ-1 > arrJ) { tmp = arrJ；arrJ = arrJ-1；arrJ-1 = tmp；j-；}

可以是一个for循环，如所解释的：

    j = i; // Initialization
    while (j > 0 && arr[j - 1] > arr[j]) { // Condition
        tmp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = tmp;
        j--; // Decrement
    }

它转化为：

for (j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
    tmp = arr[j];
    arr[j] = arr[j - 1];
    arr[j - 1] = tmp;
}

现在，为什么第一行没有必要，甚至气馁呢？

因为应该在需要变量的地方声明变量，而不是在此之前：

void insertion_sort(int arr[], int length)
{
    for (int i = 1; i < length; i++) {
        for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
            int tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
        }
    }
}

Answer 2

这还不是C++。仅仅使用std::cout并不能使C++生成。但别担心，我们会到的。

安全接口

无论何时设计API (或接口)，都应该努力使其尽可能安全。

这里的接口是不安全的:要正确传递两个未链接的变量是很麻烦的；将变量混在一起传递与要排序(或打印)数组不相对应的大小太容易了。

显然，在您的玩具示例中，它不会出现，但是一旦您在同一个函数中操作多个数组，您很可能会犯这个错误。即使只有一个数组，在重新分配(例如)之前传递长度也是可能的。

因此，您需要以一个接口为目标，该接口可以在单个参数中传递两部分信息。一个明显的选择是std::vector，另一个可能是array_view或random_access_range的实例，但这些都不是标准，所以现在我们不必费心了。

因此，接口变成：

void insertion_sort(std::vector<int>& array);
void print(std::vector<int> const& array);

请注意命名过程中的一致性；这两次参数都被命名为array，而不是一次arr和一次array。一致性也许是小人的心中有数，但它确实对读者有帮助。

算法

插入排序通常简单地描述为:依次读取每个元素，并将其插入到前面的read (和排序)元素中的正确位置。

因此，该算法的成本是：

• 对于每个N元素
• 在i-1中插入它的成本(其中i是正在读取的元素的索引)

外循环，我们不能做任何事情，但插入怎么办？

在代码中，插入是通过以下方式完成的：

    while (j > 0 && arr[j - 1] > arr[j]) {
        tmp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = tmp;
        j--;
    }

也就是说，这个值正向前方涌出，直到找到它的位置。

就比较而言，这是次优的:寻找要插入位置的最优算法是使用二进制搜索而不是线性搜索，对于O(log )复杂度，而不是O(N)复杂度。

就移动的次数而言，好吧，你可能必须移动所有的元素，所以它只能通过一个常数因子来改进。

站在巨人的肩膀上，我们可以通过将搜索和移动分开来改进代码，并使用现有的算法这样做：

• std::upper_bound生成一个指向范围内的第一个元素的指针，该指针大于我们搜索的值。
• std::rotate旋转传递给它的范围(和中间点)的元素，因此最后两个元素分隔的范围在前两个元素分隔的范围之前。

我们可以使用它们保持索引，尽管它有点冗长：

void insertion_sort(std::vector<int>& array) {
    typedef std::vector<int>::iterator It;

    for (size_t i = 1, length = array.size(); i < length; ++i) {
        // 1. Search
        It const end_sorted = array.begin() + i;
        It const insertion_point =
            std::upper_bound(array.begin(), end_sorted, array[i]);

        // 2. Insert
        std::rotate(insertion_point, end_sorted, end_sorted + 1);
    }
}

因此，我建议跳过这一步，只需切换到迭代器，因为我们使用的算法的接口是这样的：

void insertion_sort(std::vector<int>& array) {
    typedef std::vector<int>::iterator It;

    for (It it = array.begin(), end = array.end(); it != end; ++it) {
        // 1. Search
        It const insertion_point =
            std::upper_bound(array.begin(), it, *it);

        // 2. Insert
        std::rotate(insertion_point, it, it + 1);
    }
}

在现代C++中，它将使用auto而不是显式命名迭代器类型：

void insertion_sort(std::vector<int>& array) {
    for (auto it = array.begin(), end = array.end(); it != end; ++it) {
        // 1. Search
        auto const insertion_point =
            std::upper_bound(array.begin(), it, *it);

        // 2. Insert
        std::rotate(insertion_point, it, it + 1);
    }
}

请注意，进一步缩写并不是一个好主意；虽然一行可能会给作者一种模糊的温暖感觉，但它们最终只会让维护人员感到头脑发热：

// Puzzle time!
void insertion_sort(std::vector<int>& array) {
    for (auto it = array.begin(), end = array.end(); it != end; ++it) {
        std::rotate(std::upper_bound(array.begin(), it, *it), it, it + 1);
    }
}

endl做什么？

最后，刁钻的问题:认为std::endl是什么，做什么？

std::endl是一个所谓的流操作程序，它是一个签名为：

template< class CharT, class Traits >
std::basic_ostream<CharT, Traits>& endl( std::basic_ostream<CharT, Traits>& os );

因此，当在流上使用时，它对所述流执行操作并返回它(以允许进一步链接)。

具体来说，ostream << std::endl相当于：

ostream << '\n';
ostream.flush();

其中，flush确保数据不会在进程中缓冲，而是完全发送到操作系统(它不能保证数据在磁盘上、通过网络发送或其他任何东西)。

通常，几乎没有理由称flush为：

• 在没有保证数据到达磁盘(或任何地方)的情况下，它没有实际的用途。
• 缓冲区是出于性能原因而引入的，绕过它就是要慢慢来。

因此，您不仅应该避免使用flush，std::endl也是一个口头禅。只需编写'\n'以获得行尾字符，并完成它.

因此，我们重写了print：

void print(std::vector<int> const& array) {
    for (auto it = array.begin(), end = array.end(); it != end; ++i) {
        std::cout << *it << '\n';
    }
}

或者，使用现代C++的范围表示法：

void print(std::vector<int> const& array) {
    for (int e: array) { std::cout << e << '\n'; }
}

谁说C++不可能漂亮？

Answer 3

减少写

的次数

现在，您交换相邻的元素，直到最新的元素到达适当的位置。这需要2n数组写入来移动元素n点。您可以将数组元素移到一个位置上，然后将最新的元素写入其正确位置，而不是交换。这需要n数组写入，它将需要编写的写入次数减少一半。

下面是代码的样子：

void insertion_sort(int arr[], int length)
{
    int i,j;
    for (i = 1; i < length; i++) {
        int tmp = arr[i];
        for (j = i; j > 0 && arr[j - 1] > tmp; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = tmp;
    }
}