你能告訴我，我對插入式排序的實作是否正確？它正在作業，但感覺有些不對勁。 -有解無憂

它正在作業，但我的老師不同意。他說，我的迭代次數會更多。但怎么做呢？

 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[/span].
                    flag = 0;
                }
            if(flag) break; //優化的最佳情況，所以內回圈不運行排序的部分。
            }
        }
    
    }

uj5u.com熱心網友回復：

至少要改變這個代碼片段

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[/span].
    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將被遞減，變成等于0。然后在外回圈的第三個運算式中i將被遞增并重新等于1。因此，該回圈將為變數i的相同值重復其迭代。

如果像你所做的那樣使用陣列中相鄰元素的交換，那么這個函式可以寫得更簡單，而不需要使用變數flag。請注意，陣列中元素的數量應該是size_t的型別。

下面是一個演示程式

#include <iostream>
#include < utility>

void InsertionSort( int arr[], size_t size ) /span>
{
    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 << ' '/span>;
    }
    
    std::cout <<'
'。
    
    return 0。

程式輸出是

1  2  3 4 5 6 7 8 9

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/310853.html

標籤：

上一篇：如何根據同一輸出中的觀察結果對每一列進行排序？

下一篇：用勾股定理的方法找出最小的二維平面（盒子）來容納所有的碎片（最大的）。