在Java中使用二進制搜索實現二進制插入排序

Question

我無法將這兩種算法組合在一起。我被要求修改Binary Search以返回元素應該插入到數組中的索引。然後我被要求執行一個Binary Insertion Sort，它使用我的Binary Search對隨機生成的ints的數組進行排序。

我Binary Search我的Binary Search工作方式，每當我單獨測試時返回正確的索引。我寫出了Binary Insertion Sort來感受它是如何工作的，並讓它工作。只要我將兩者結合在一起，就會破裂。我知道我在一起執行它們的方式不正確，但我不確定我的問題在哪裏。

下面是我得到了什麼：

public class Assignment3 
{ 
    public static void main(String[] args) 
    { 
     int[] binary = { 1, 7, 4, 9, 10, 2, 6, 12, 3, 8, 5 }; 

     ModifiedBinaryInsertionSort(binary); 

    } 

    static int ModifiedBinarySearch(int[] theArray, int theElement) 
    { 
     int leftIndex = 0; 
     int rightIndex = theArray.length - 1; 
     int middleIndex = 0; 

     while(leftIndex <= rightIndex) 
     { 
      middleIndex = (leftIndex + rightIndex)/2; 

      if (theElement == theArray[middleIndex]) 
       return middleIndex; 
      else if (theElement < theArray[middleIndex]) 
       rightIndex = middleIndex - 1; 
      else 
       leftIndex = middleIndex + 1; 
     } 

     return middleIndex - 1; 
    } 

    static void ModifiedBinaryInsertionSort(int[] theArray) 
    { 
     int i = 0; 
     int[] returnArray = new int[theArray.length + 1]; 

     for(i = 0; i < theArray.length; i++) 
     { 
      returnArray[ModifiedBinarySearch(theArray, theArray[i])] = theArray[i]; 
     } 

     for(i = 0; i < theArray.length; i++) 
     { 
      System.out.print(returnArray[i] + " "); 
     } 
    } 
} 

返回值我得到這個當我運行它是1 0 0 0 0 2 0 0 3 5 12。有什麼建議麼？

更新：更新ModifiedBinaryInsertionSort

static void ModifiedBinaryInsertionSort(int[] theArray) 
{ 
    int index = 0; 
    int element = 0; 
    int[] returnArray = new int[theArray.length]; 

    for (int i = 1; i < theArray.lenght - 1; i++) 
    { 
     element = theArray[i]; 
     index = ModifiedBinarySearch(theArray, 0, i, element); 
     returnArray[i] = element; 

     while (index >= 0 && theArray[index] > element) 
     { 
      theArray[index + 1] = theArray[index]; 
      index = index - 1; 
     } 
     returnArray[index + 1] = element; 
    } 
} 

Answer 1

插入排序如何工作的，它創建一個新的空數組B和，用於排序的數組A中，它的二進制搜索到具有B的部分中的每個元素（從左到右），將所有元素移到B中位置的右側，選擇一個右側並插入元素。因此，您正在B中構建一個所有時間排序的數組，直到它爲止B的全尺寸幷包含A中的所有內容。

兩件事：

一，二進制搜索應該能夠接受一個int startOfArray和一個int endOfArray，它將只能在這兩個點之間進行二分搜索。這使您可以僅考慮實際上是排序數組的數組B的部分。

二，在插入之前，您必須先將所有元素向右移動，然後再插入您製作的縫隙中。

Answer 2

我意識到這是舊的，但問題的答案是，也許有點不直觀，「Middleindex - 1」將不會成爲所有情況下的插入索引。 如果您在紙上通過幾個案例，問題應該變得明顯。

我有一個解決這個問題的擴展方法。爲了將其應用於您的情況，您可以遍歷現有列表，並將其插入空的起始列表中。

public static void BinaryInsert<TItem, TKey>(this IList<TItem> list, TItem item, Func<TItem, TKey> sortfFunc) 
     where TKey : IComparable 
    { 
     if (list == null) 
      throw new ArgumentNullException("list"); 

     int min = 0; 
     int max = list.Count - 1; 
     int index = 0; 

     TKey insertKey = sortfFunc(item); 

     while (min <= max) 
     { 
      index = (max + min) >> 1; 

      TItem value = list[index]; 
      TKey compKey = sortfFunc(value); 
      int result = compKey.CompareTo(insertKey); 

      if (result == 0) 
       break; 
      if (result > 0) 
       max = index - 1; 
      else 
       min = index + 1; 
     } 

     if (index <= 0) 
      index = 0; 
     else if (index >= list.Count) 
      index = list.Count; 
     else 
      if (sortfFunc(list[index]).CompareTo(insertKey) < 0) 
       ++index; 

     list.Insert(index, item); 
    } 

Answer 3

老兄，我認爲你的代碼有一些嚴重的問題。不幸的是，你錯過了這個算法的成果（邏輯）。你的神聖目標是首先獲得索引，插入是蛋糕散步，但索引需要一些汗水。請不要看到這個算法，除非你盡力而爲，絕望。永不放棄，你已經知道邏輯，你的目標是在你身上找到它。請讓我知道任何錯誤，差異等快樂編碼！

public class Insertion { 
private int[] a; 
int n; 
int c; 

public Insertion() 
{ 
    a = new int[10]; 
    n=0; 
} 

int find(int key) 
{ 
    int lowerbound = 0; 
    int upperbound = n-1; 

    while(true) 
    { 
     c = (lowerbound + upperbound)/2; 
     if(n==0) 
      return 0; 
     if(lowerbound>=upperbound) 
     { 
      if(a[c]<key) 
       return c++; 
      else 
       return c; 
     } 
     if(a[c]>key && a[c-1]<key) 
      return c; 
     else if (a[c]<key && a[c+1]>key) 
      return c++; 
     else 
     { 
      if(a[c]>key) 
       upperbound = c-1; 
      else 
       lowerbound = c+1; 
     } 
    } 
} 

void insert(int key) 
{ 
    find(key); 
    for(int k=n;k>c;k--) 
    { 
     a[k]=a[k-1]; 
    } 
    a[c]=key; 
    n++; 
} 
void display() 
{ 
    for(int i=0;i<10;i++) 
    { 
     System.out.println(a[i]); 
    } 
} 

public static void main(String[] args) 
{ 
    Insertion i=new Insertion(); 
    i.insert(56); 
    i.insert(1); 
    i.insert(78); 
    i.insert(3); 
    i.insert(4); 
    i.insert(200); 
    i.insert(6); 
    i.insert(7); 
    i.insert(1000); 
    i.insert(9); 
    i.display(); 
} 

}

Answer 4

這裏是我的方法排序使用二進制搜索整數數組。 它修改作爲參數傳遞的數組。

public static void binaryInsertionSort(int[] a) { 
    if (a.length < 2) 
     return; 
    for (int i = 1; i < a.length; i++) { 
     int lowIndex = 0; 
     int highIndex = i; 
     int b = a[i]; 

     //while loop for binary search 
     while(lowIndex < highIndex) { 
      int middle = lowIndex + (highIndex - lowIndex)/2; //avoid int overflow 
      if (b >= a[middle]) { 
       lowIndex = middle+1; 
      } 
      else { 
       highIndex = middle; 
      } 
     } 
     //replace elements of array 
     System.arraycopy(a, lowIndex, a, lowIndex+1, i-lowIndex); 
     a[lowIndex] = b; 
    } 
}