双向插入排序错误

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

这里的问题是您的算法只在交换整数的数组上进行一次传递。由于在第一次传递时将 93 交换到后面，第二次迭代查看现在为 33（而不是 58）的 a[2]。所以你基本上跳过了处理 58 的过程。这个算法只对数组进行了部分排序。你必须在这里进行多次传递才能得到你想要的...

void twowaysort(int n, int a[])
{
    int j;
    int first;

    for (int k = 0; k < n; ++k)
    {
        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;
                }
            }
        }
    }

}

输出：11 13 32 33 41 58 58 63 87 93

Answer 2

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

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

总而言之，这只是一个标准的插入排序。（也就是说，如果我正确理解了算法。）

将变量 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;
        } 
    }
}

Answer 3

我用向量实现了这个，我保存了起始数字的位置然后插入左边是数字较小或右边如果数字更大。然后数字向左或向右移动，直到它们变大或变小。

希望对您有所帮助

int poz = 0; //starting value position
vector<int> b;    
b.push_back(a[0]);//first value

for (int i = 1; i < n; i++)
{
    if (a[i] > prad)    //if greater
    {
        vector<int>::iterator it = b.begin() + poz;    //position of starting element
        it = b.insert(it + 1, a[i]); //insertion to the right
        int t = poz + 1;    //position of the inserted element
        while (t + 1 < b.size() && b[t] > b[t + 1])    
        {
            swap(b[t], b[t + 1]);   
            t++;                    //we go right until our number is greater
        }
    }
    else  //same here but instead of going right we go left until the value is lower
    {
        vector<int>::iterator it = b.begin() + poz;
        it = b.insert(it, a[i]);
        poz++; 
        int t = poz - 1;
        while (t > 0 && b[t] < b[t - 1])
        {
            swap(b[t], b[t - 1]);
            t--;                
        }
    }
}

双向插入排序错误

Two-way insertion sorting error

c++

sorting

algorithm

insertion-sort

two-way