二進制插入排序如何工作？

我知道二進制搜索是如何工作的，並且知道插入排序如何工作，但是這個代碼是關於二進制插入排序的，並且我在理解它的工作方式方面存在問題。二進制插入排序如何工作？

static void Main(string[] args) 
{ 
    int[] b = BinarySort(new[] { 4, 3, 7, 1, 9, 6, 2 }); 
    foreach (var i in b) 
     Console.WriteLine(i); 
} 
public static int[] BinarySort(int[] list) 
{ 
    for (int i = 1; i < list.Length; i++) 
    { 
     int low = 0; 
     int high = i - 1; 
     int temp = list[i]; 
     //Find 
     while (low <= high) 
     { 
      int mid = (low + high)/2; 
      if (temp < list[mid]) 
       high = mid - 1; 
      else 
       low = mid + 1; 
     } 
     //backward shift 
     for (int j = i - 1; j >= low; j--) 
      list[j + 1] = list[j]; 
     list[low] = temp; 
    } 
    return list; 
}

我不明白這是什麼做的部分：

//backward shift 
for (int j = i - 1; j >= low; j--) 
    list[j + 1] = list[j]; 
list[low] = temp;

，什麼是這裏使用二進制搜索的目的是什麼？你能告訴我二進制插入排序是如何工作的嗎？（C＃控制檯）

代碼源：http://w3mentor.com/learn/asp-dot-net-c-sharp/asp-dot-net-language-basics/binary-insertion-sort-in-c-net/

來源

2014-10-19 Masoud Mohammadi

這有什麼困惑嗎？你用調試器完成了它嗎？ – gunr2171 2014-10-19 20:12:32

@ gunr2171是的，但我不知道這段代碼如何對數據進行排序，這裏的二進制搜索的目的是什麼？在編輯中添加的源代碼中沒有關於它的信息。 – 2014-10-19 20:16:16

折半插入排序工作方式插入排序，但它分離定位與實際插入的插入點。

爲數組實施的插入排序將在定位插入點的同時移動項目。在循環播放項目以查找插入點時，它還會移動項目以騰出空間進行插入。

二進制插入排序將利用這樣一個事實，即已排序的項目已排序，因此它可以使用二進制搜索來查找插入點。由於二進制搜索不能移動項目以騰出空間來插入，因此必須在找到插入點後的單獨步驟中完成。

您想要解釋的代碼是移動項目以騰出空間進行插入的代碼。

來源

2014-10-19 20:19:54 Guffa

二進制插入排序如何工作？

回答

相關問題