java - 我的二进制插入排序算法的错误在哪里？

Question

我尝试实现二进制插入排序算法。

这是我的代码:

public class binary_insertion {
    public static void sort(int a[],int n){
        for (int i=0;i<n;++i){
            int temp=a[i];
            int left=0;
            int right=i;
            while (left<right){
                int middle=(left+right)/2;
                if (temp>=a[middle])
                    left=right+1;
                else
                    right=middle;
            }
            for (int j=i;j>left;--j){
                swap(a,j-1,j);
            }
        }
    }

    public static void main(String[] args){
        int a[]=new int[]{12,10,34,23,9,7,8,5,6};
        sort(a,a.length);
        for (int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }
    }
    public static void swap(int a[],int i,int j){
        int k=a[i];
        a[i]=a[j];
        a[j]=k;
    }
}

我的结果是错误的:

5
7
6
9
8
10
12
34
23

我做错了什么？

Answer 1

首先突出的是这里:

      while (left<right){
          int middle=(left+right)/2;
          if (temp>=a[middle])
              left=right+1;
          else
               right=middle;

你想要 left = middle + 1。

该代码适用于该更改。