你能告诉我我的插入排序实现是否正确吗？它正在工作，但感觉有些可疑

Question

这是可行的，但我的老师不同意。说我的迭代次数会更多。但是怎么办呢？？

    void InsertionSort(int arr[], int size)
    {
        for (int i = 1; i < size; i++)
        {
            int flag = 1;
            int val = arr[i];

            for(int j = i-1; j>=0; j--)  //keep swapping till its inserted to its right place
            {
                if(val < arr[j])
                {
                    int temp = arr[j]; 
                    arr[j] = val;
                    arr[i] = temp;
                    i--;  //decrementing i so we keep going left until the condition is false
                    flag = 0;
                }
            if(flag) break; // optimised best case, so inner loop doesn't run for sorted part.
            }
        }
    
    }

Answer 1

要么至少更改此代码段

if(val < arr[j])
{
    int temp = arr[j]; 
    arr[j] = val;
    arr[i] = temp;
    i--;  //decrementing i so we keep going left until the condition is false
    flag = 0;
}

以下方式

if(val < arr[j])
{
    int temp = arr[j]; 
    arr[j] = val;
    arr[j+1] = temp;
    flag = 0;
}

或者换老师。:)

事实上，您的函数可以工作，但它很笨拙，因为减少内部循环中的变量 i 会导致外部循环针对 i 的相同值重复迭代。

例如，考虑一个以元素 { 2, 1, ... } 开头的数组。在外循环的第一次迭代中，i 由 1 初始化。在内部循环中，这两个第一个元素将被交换，i 将递减并等于 tp 0。然后在外部 for 循环的第三个表达式中，i 将递增并重新等于 1。因此，循环将针对变量 i.

的相同值重复其迭代

如果像您一样使用数组中相邻元素的交换，则可以在不使用变量 flag 的情况下编写更简单的函数。注意数组中元素个数的类型应该是size_t.

这是一个演示程序

#include <iostream>
#include <utility>

void InsertionSort( int arr[], size_t size )
{
    for ( size_t i = 1; i < size; i++ )
    {
        for( size_t j = i; j != 0 && arr[j] < arr[j-1]; j--)
        {
            std::swap( arr[j], arr[j-1] );
        }
    }
}
    
int main() 
{
    int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    
    InsertionSort( a, sizeof( a ) / sizeof( *a ) );
    
    for ( const auto &item : a )
    {
        std::cout << item << ' ';
    }
    
    std::cout << '\n';
    
    return 0;
}

程序输出为

1 2 3 4 5 6 7 8 9

你能告诉我我的插入排序实现是否正确吗？它正在工作，但感觉有些可疑

Can you tell me if my implementation of Insertion Sort is correct? It's working but something feels fishy

c++

algorithm

sorting

data-structures

insertion-sort