c++ - 双向插入排序错误

Question

我正在尝试进行双向插入排序。它应该获取数组中的第一个值，然后通过将其与第一个值进行比较来对数组中的以下数字进行排序。如果数字较大，则放在数组中第一个数字的后面，如果数字较小，则放在前面。

这是一张说明该过程的图片。

这里的数组是6 5 3 1 8 7 2 4，从上往下读就是排序过程的每一步。它将数字 6 与其余数字进行比较，然后相应地放置它们。

到目前为止我有这段代码:

void twowaysort(int n, int a[])
{
    int j;
    int first = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] > first) {
            j = i + 1;
            while (j <= n - 1 && a[j] < a[j - 1]) {
                swap(a[j - 1], a[j]);
                j = j + 1;
            }
        }
        if (a[i] < first) {
            j = i - 1;
            while (j >= 0 && a[j] > a[j + 1]) {
                swap(a[j + 1], a[j]);
                j = j - 1;
            }
        }
    }
}

虽然这适用于上面的数组，但它似乎无法对以下内容进行排序:13 93 58 33 58 63 11 41 87 32。这让我相信某处存在错误。

如有任何帮助，我们将不胜感激。

Answer 1

我注意到的第一件事是即使有一个选定的值，也没有相应的选定索引。所以必须添加和使用它。

第二件事是所选值只是一个边界。每次当前排序的值都必须冒泡时，它就会下降。

所以总而言之，这只是一个标准的插入排序。 (也就是说，如果我正确理解算法的话。)

将变量 i 和 j 重命名为 to_sort_idx 和 look_at_idx。

void twowaysort( int a_size, int a[] )
{
    if ( a_size < 2 )
        return;

    int selected_idx   = 0;
    int selected_value = a[ selected_idx ];

    for ( int to_sort_idx = 1; to_sort_idx < a_size; to_sort_idx++ )
    {
        if ( a[ to_sort_idx ] > selected_value )
        {
            int look_at_idx = to_sort_idx;

            while ( look_at_idx > selected_idx && a[ look_at_idx ] < a[ look_at_idx - 1] )
            {              
                std::swap( a[ look_at_idx -1 ], a[ look_at_idx  ] );
                --look_at_idx;
            }
        }
        else //if ( a[ to_sort_idx ] <= selected_value )
        {
            int look_at_idx = to_sort_idx - 1;

            while ( look_at_idx >= 0 && a[ look_at_idx ] > a[ look_at_idx + 1 ] )
            {
                std::swap( a[ look_at_idx ], a[ look_at_idx + 1] );
                --look_at_idx;
            }

            ++selected_idx;
        } 
    }
}