c++ - 利用二分查找误差的插入排序算法

Question

我运行了以下代码，它是插入排序算法，它使用二进制搜索来找到插入项目的正确位置而不是线性搜索，但结果中有两个数字没有正确排序!

#include <iostream>
using namespace std;

void insertion_sort (int a[], int n /* the size of array */)
{
    int i, temp,j;
    for (i = 1; i < n; i++)
    {
        /* Assume items before a[i] are sorted. */
        /* Pick an number */
        temp = a[i];

        /* Do binary search to find out the
           point where b is to be inserted. */

        int low = 0, high = i - 1, k;

        while (high-low>1)
        {
            int mid = (high + low) / 2;

            if (temp <= a[mid]) 
                high = mid;
            else 
                low = mid;
        }

        /* Shift items between high and i by 1 */
        for (k = i; k > high; k--)
            a[k] = a[k - 1];

        a[high] = temp;
    }
}


int main()
{
    int A[15]={9,5,98,2,5,4,66,12,8,54,0,11,99,55,13};
    insertion_sort(A,15);
    for (int i=0; i<15; i++)
        cout<<A[i]<<endl;
    system("pause");
    return 0;
}

输出:

为什么？

Answer 1

#include <iostream>
using namespace std;

void insertion_sort (int a[], int n /* the size of array */)
{
    int i, temp,j;
    for (i = 1; i < n; i++)
    {
        /* Assume items before a[i] are sorted. */
        /* Pick an number */
        temp = a[i];

        /* Do binary search to find out the
           point where b is to be inserted. */

上限应该在范围之上并且不包括搜索，因为您可能需要在末尾插入，即什么都不做。

        // int low = 0, high = i - 1, k;
        int low = 0, high = i, k;

这里的条件应该是low < high , 不是 low + 1 < high

        // while (high-low>1)
        while (low < high)
        {
            int mid = (high + low) / 2;

            if (temp <= a[mid]) 
                high = mid;
            else 

一旦你有a[mid ] 严格大于 temp , 插入的最低可能位置是 mid + 1 .

                // low = mid;
                low = mid + 1
        }

        /* Shift items between high and i by 1 */
        for (k = i; k > high; k--)
            a[k] = a[k - 1];

        a[high] = temp;
    }
}


int main()
{
    int A[15]={9,5,98,2,5,4,66,12,8,54,0,11,99,55,13};
    insertion_sort(A,15);
    for (int i=0; i<15; i++)
        cout<<A[i]<<endl;
    system("pause");
    return 0;
}