折半插入排序可视化交互式动画版

二分插入排序是一种与插入排序类似的排序算法，但我们不使用线性搜索来查找应插入元素的位置，而是使用二分搜索。这样，我们将插入单个元素的比较值从 O(N) 降低到 O(log N)。

它是一种灵活的算法，这意味着当相同的给定成员已经经过大量排序时，即特征的当前位置更接近其在排序列表中的实际位置时，它的工作速度更快。

这是一种稳定的过滤算法——具有相同值的元素在最后一个列表中以相同的顺序出现。

二分插入排序的应用：

当数组的项数较少时，二分插入排序效果最佳。
在进行快速排序或归并排序时，当子数组大小变小时（比如 <= 25 个元素），最好使用二分插入排序。
当键之间的比较成本足够高时，该算法也适用。例如，如果我们要过滤多个字符串，那么两个字符串的比较性能会更高。

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

在二进制插入排序模式中，我们将相同的成员分为两个子数组——已过滤的和未过滤的。相同成员的第一个元素位于有组织的子数组中，所有其他元素都是无计划的。
然后我们从第二个元素迭代到最后一个元素。在重复第 i 次时，我们将当前对象设为我们的“密钥”。这个键是我们应该添加到下面现有列表中的一个功能。
为了做到这一点，我们首先对下面的排序子数组使用二分搜索来查找大于我们的键的元素的位置。我们称这个位置为“pos”。然后我们将所有元素从 pos 右移到 1 并创建 Array[pos] = key。
我们可以注意到，在每个第 i 次乘法中，数组的左侧部分直到 (i – 1) 都已排序。

实现二分插入排序的方法：

将数组从第二个元素迭代到最后一个元素。
将当前元素 A[i] 存储在变量 key 中。
使用二分查找法在 A[0] 到 A[i-1] 的子数组中查找刚好大于 A[i] 的元素的位置。假设该元素位于索引 pos 处。
将索引 pos 到 i-1 的所有元素向右移动。
A[位置] = 键。

下面是上述方法的实现：

C++

              
                
                    // C program for implementation of
// binary insertion sort
                        
#include <iostream>
using namespace std;
 
// A binary search based function
// to find the position
                        
// where item should be inserted
// in a[low..high]
int binarySearch(int a[], int item,
                int low, int high)
{
    if
                          (high <= low)
        return (item > a[low]) ?
                (low + 1) : low;
 
    int
                          mid = (low + high) / 2;
 
    if
                          (item == a[mid])
        return mid + 1;
 
    if
                          (item > a[mid])
        return binarySearch(a, item,
                            mid + 1, high);
    return binarySearch(a, item, low,
                        
                        mid - 1);
}
 
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
                        
{
    int
                          i, loc, j, k, selected;
 
    for (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inserted
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}
 
// Driver Code
int main()
{
    int
                          a[]
        = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int
                          n = sizeof(a) / sizeof(a[0]), i;
 
    insertionSort(a, n);
 
    cout <<"Sorted array: \n";
    for (i = 0; i < n; i++)
        cout <<" "<< a[i];
 
    return 0;
}
 
// this code is contribution by shivanisinghss2110

                  

              
            

C

              
                
                    // C program for implementation of 
// binary insertion sort
                        
#include <stdio.h>
                        
 
// A binary search based function
// to find the position
                        
// where item should be inserted 
// in a[low..high]
int binarySearch(int a[], int item, 
                 int low, int high)
{
    if
                          (high <= low)
        return (item > a[low]) ? 
                (low + 1) : low;
 
    int
                          mid = (low + high) / 2;
 
    if
                          (item == a[mid])
        return mid + 1;
 
    if
                          (item > a[mid])
        return binarySearch(a, item, 
                            mid + 1, high);
    return binarySearch(a, item, low, 
                        
                        mid - 1);
}
 
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
                        
{
    int
                          i, loc, j, k, selected;
 
    for (i = 1; i < n; ++i) 
    {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inserted
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc) 
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}
 
// Driver Code
int main()
{
    int
                          a[]
        = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int
                          n = sizeof(a) / sizeof(a[0]), i;
 
    insertionSort(a, n);
 
    printf("Sorted array: \n");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
 
    return 0;
}

                  

              
            

Java

              
                
                    // Java Program implementing
                        
// binary insertion sort
                        
 
import java.util.Arrays;
class GFG 
{
   
                        
    public
                          static void main(String[] args)
    {
        final int[] arr = { 37, 23, 0,   17, 12, 72,
                            31, 46, 100, 88, 54 };
 
        new GFG().sort(arr);
 
        for (int
                          i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
 
    // Driver Code
    public
                          void sort(int array[])
    {
        for (int
                          i = 1; i < array.length; i++) 
        {
            int x = array[i];
 
            // Find location to insert
            // using binary search
            int j = Math.abs(
                Arrays.binarySearch(array, 0, 
                                    i, x) + 1);
 
            // Shifting array to one
            // location right
            System.arraycopy(array, j,
                             array, j + 1, i - j);
 
            // Placing element at its 
            // correct location
            array[j] = x;
        }
    }
}
 
// Code contributed by Mohit Gupta_OMG

                  

              
            

Python3

              
                
                    # Python Program implementation
# of binary insertion sort
                        
 
 
def binary_search(arr, val, start, end):
     
    # we need to distinguish whether we 
    # should insert before or after the 
    # left boundary. imagine [0] is the last 
    # step of the binary search and we need 
    # to decide where to insert -1
    if
                          start ==
                          end:
        if arr[start] > val:
            return start
        else:
            return start+1
 
    # this occurs if we are moving 
    # beyond left's boundary meaning 
    # the left boundary is the least 
    # position to find a number greater than val
    if
                          start > end:
        return start
 
    mid = (start+end)//2
    if
                          arr[mid] < val:
        return binary_search(arr, val, mid+1, end)
    elif
                          arr[mid] > val:
        return binary_search(arr, val, start, mid-1)
    else:
        return mid
 
 
def insertion_sort(arr):
    for
                          i in range(1, len(arr)):
                        
        val = arr[i]
                        
        j = binary_search(arr, val, 0, i-1)
        arr = arr[:j] + [val] + arr[j:i] + arr[i+1:]
    return
                          arr
 
 
print("Sorted array:")
print(insertion_sort([37, 23, 0, 31, 22, 17, 12, 72, 31, 46, 100, 88, 54]))
 
# Code contributed by Mohit Gupta_OMG

                  

              
            

C＃

              
                
                    // C# Program implementing
                        
// binary insertion sort
                        
using System;
 
class GFG {
 
    public
                          static void Main()
    {
        int[] arr = { 37, 23, 0,   17, 12, 72,
                      31, 46, 100, 88, 54 };
 
        sort(arr);
 
        for (int
                          i = 0; i < arr.Length; i++)
            Console.Write(arr[i] + " ");
    }
 
    // Driver Code
    public
                          static void sort(int[] array)
    {
        for (int
                          i = 1; i < array.Length; i++)
        {
            int x = array[i];
 
            // Find location to insert using
            // binary search
            int j = Math.Abs(
                Array.BinarySearch(array, 
                                   0, i, x) + 1);
 
            // Shifting array to one location right
            System.Array.Copy(array, j, 
                              array, j + 1,
                              i - j);
 
            // Placing element at its correct
            // location
            array[j] = x;
        }
    }
}
 
// This code is contributed by nitin mittal.

                  

              
            

PHP

              
                
                    <?php
// PHP program for implementation of 
// binary insertion sort
                        
 
// A binary search based function to find 
// the position where item should be 
// inserted in a[low..high]
                        
function binarySearch($a, $item, $low, $high)
{
 
    if
                          ($high <= $low) 
                        
        return ($item > $a[$low]) ? 
                       ($low + 1) : $low; 
                        
 
    $mid
                          = (int)(($low + $high) / 2); 
 
    if($item == $a[$mid]) 
        return $mid + 1; 
 
    if($item > $a[$mid]) 
        return binarySearch($a, $item, 
                            $mid + 1, $high); 
         
    return
                          binarySearch($a, $item, $low, 
                            $mid - 1); 
} 
 
// Function to sort an array a of size 'n' 
function insertionSort(&$a, $n) 
{ 
    $i; $loc; $j; $k; $selected; 
                        
 
    for
                          ($i = 1; $i < $n; ++$i) 
    { 
        $j = $i
                          - 1; 
        $selected = $a[$i]; 
 
        // find location where selected 
        // item should be inserted 
        $loc = binarySearch($a, $selected, 0, $j); 
 
        // Move all elements after location 
        // to create space 
        while ($j
                          >= $loc) 
        { 
            $a[$j + 1] = $a[$j]; 
            $j--; 
        } 
        $a[$j + 1] = $selected; 
    } 
} 
 
// Driver Code
$a = array(37, 23, 0, 17, 12, 72, 
           31, 46, 100, 88, 54); 
            
                        
$n = sizeof($a); 
                        
 
insertionSort($a, $n); 
 
echo "Sorted array:\n"; 
for ($i = 0; $i < $n; $i++) 
    echo
                          "$a[$i] "; 
 
// This code is contributed by 
// Adesh Singh
?>

                  

              
            

JavaScript

              
                
                    <script>
// Javascript Program implementing
// binary insertion sort
                        
 
function binarySearch(a, item, low, high)
{
  
    if
                          (high <= low)
        return (item > a[low]) ?
                       (low + 1) : low;
  
    mid = Math.floor((low + high) / 2);
  
    if(item == a[mid])
        return mid + 1;
  
    if(item > a[mid])
        return binarySearch(a, item,
                            mid + 1, high);
          
                        
    return
                          binarySearch(a, item, low,
                            mid - 1);
}
 
function sort(array)
{
    for
                          (let i = 1; i < array.length; i++)
        {
            let j = i - 1;
            let x = array[i];
  
            // Find location to insert
            // using binary search
            let loc = Math.abs(
                binarySearch(array, x,
                                    0, j));
  
            // Shifting array to one
            // location right
             
                        
            while (j >= loc)
            {
                array[j + 1] = array[j];
                j--;
            }
  
            // Placing element at its
            // correct location
            array[j+1] = x;
        }
}
 
// Driver Code
let arr=[ 37, 23, 0,   17, 12, 72,
                            31, 46, 100, 88, 54];
sort(arr);
 
for (let i = 0; i < arr.length; i++)
    document.write(arr[i] + " ");
 
 
// This code is contributed by unknown2108
</script>
// C program for implementation of
// binary insertion sort
#include <stdio.h>
 
// A binary search based function
// to find the position
// where item should be inserted
// in a[low..high]
int binarySearch(int a[], int item,
                int low, int high)
{
                        
    if
                          (high <= low)
        return (item > a[low]) ?
                (low + 1) : low;
 
    int mid = (low + high) / 2;
 
    if
                          (item == a[mid])
        return mid + 1;
 
    if
                          (item > a[mid])
        return binarySearch(a, item,
                            mid + 1, high);
    return
                          binarySearch(a, item, low,
                        mid - 1);
}
                        
 
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
{
                        
    int i, loc, j, k, selected;
 
    for
                          (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inserted
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}
                        
 
// Driver Code
int main()
{
                        
    int a[]
                        
        = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int n = sizeof(a) / sizeof(a[0]), i;
 
    insertionSort(a, n);
 
    printf("Sorted array: \n");
    for
                          (i = 0; i < n; i++)
        printf("%d ", a[i]);
 
    r// C program for implementation of
// binary insertion sort
#include <stdio.h>
 
// A binary search based function
// to find the position
// where item should be inserted
// in a[low..high]
int binarySearch(int a[], int item,
                int low, int high)
{
                        
    if
                          (high <= low)
        return (item > a[low]) ?
                (low + 1) : low;
 
    int mid = (low + high) / 2;
 
    if
                          (item == a[mid])
        return mid + 1;
 
    if
                          (item > a[mid])
        return binarySearch(a, item,
                            mid + 1, high);
    return
                          binarySearch(a, item, low,
                        mid - 1);
}
                        
 
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
{
                        
    int i, loc, j, k, selected;
 
    for
                          (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inseretd
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}
                        
 
// Driver Code
int main()
{
                        
    int a[]
                        
        = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int n = sizeof(a) / sizeof(a[0]), i;
 
    insertionSort(a, n);
 
    printf("Sorted array: \n");
    for
                          (i = 0; i < n; i++)
        printf("%d ", a[i]);
 
    // C program for implementation of
// binary insertion sort
#include <stdio.h>
 
// A binary search based function
// to find the position
// where item should be inserted
// in a[low..high]
int binarySearch(int a[], int item,
                int low, int high)
{
                        
    if
                          (high <= low)
        return (item > a[low]) ?
                (low + 1) : low;
 
    int mid = (low + high) / 2;
 
    if
                          (item == a[mid])
        return mid + 1;
 
    if
                          (item > a[mid])
        return binarySearch(a, item,
                            mid + 1, high);
    return
                          binarySearch(a, item, low,
                        mid - 1);
}
                        
 
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
{
                        
    int i, loc, j, k, selected;
 
    for
                          (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inseretd
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}
                        
 
// Driver Code
int main()
{
                        
    int a[]
                        
        = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int n = sizeof(a) / sizeof(a[0]), i;
 
    insertionSort(a, n);
 
    printf("Sorted array: \n");
    for
                          (i = 0; i < n; i++)
        printf("%d ", a[i]);
 
// C program for implementation of
// binary insertion sort
#include <stdio.h>
 
// A binary search based function
// to find the position
// where item should be inserted
// in a[low..high]
int binarySearch(int a[], int item,
                int low, int high)
{
                        
    if
                          (high <= low)
        return (item > a[low]) ?
                (low + 1) : low;
 
    int mid = (low + high) / 2;
 
    if
                          (item == a[mid])
        return mid + 1;
 
    if
                          (item > a[mid])
        return binarySearch(a, item,
                            mid + 1, high);
    return
                          binarySearch(a, item, low,
                        mid - 1);
}
                        
 
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
{
                        
    int i, loc, j, k, selected;
 
    for
                          (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inserted
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}
                        
 
// Driver Code
int main()
{
                        
    int a[]
                        
        = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int n = sizeof(a) / sizeof(a[0]), i;
 
    insertionSort(a, n);
 
    printf("Sorted array: \n");
    for
                          (i = 0; i < n; i++)
        printf("%d ", a[i]);
// C program for implementation of
// binary insertion sort
#include <stdio.h>
 
// A binary search based function
// to find the position
// where item should be inserted
// in a[low..high]
int binarySearch(int a[], int item,
                int low, int high)
{
                        
    if
                          (high <= low)
        return (item > a[low]) ?
                (low + 1) : low;
 
    int mid = (low + high) / 2;
 
    if
                          (item == a[mid])
        return mid + 1;
 
    if
                          (item > a[mid])
        return binarySearch(a, item,
                            mid + 1, high);
    return
                          binarySearch(a, item, low,
                        mid - 1);
}
                        
 
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
{
                        
    int i, loc, j, k, selected;
 
    for
                          (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inseretd
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}
                        
 
// Driver Code
int main()
{
                        
    int a[]
                        
        = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int n = sizeof(a) / sizeof(a[0]), i;
 
    insertionSort(a, n);
 
    printf("Sorted array: \n");
    for
                          (i = 0; i < n; i++)
        printf("%d ", a[i]);// C program for implementation of
// binary insertion sort
#include <stdio.h>
 
// A binary search based function
// to find the position
// where item should be inserted
// in a[low..high]
int binarySearch(int a[], int item,
                int low, int high)
{
                        
    if
                          (high <= low)
        return (item > a[low]) ?
                (low + 1) : low;
 
    int mid = (low + high) / 2;
 
    if
                          (item == a[mid])
        return mid + 1;
 
    if
                          (item > a[mid])
        return binarySearch(a, item,
                            mid + 1, high);
    return
                          binarySearch(a, item, low,
                        mid - 1);
}
                        
 
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
{
                        
    int i, loc, j, k, selected;
 
    for
                          (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inseretd
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}
                        
 
// Driver Code
int main()
{
                        
    int a[]
                        
        = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int n = sizeof(a) / sizeof(a[0]), i;
 
    insertionSort(a, n);
 
    printf("Sorted array: \n");
    for
                          (i = 0; i < n; i++)
        printf("%d ", a[i])

                  

              
            

输出

排序数组：
0 12 17 23 31 37 46 54 72 88 100

时间复杂度： 由于每次插入所需的一系列交换，整个算法的最坏情况运行时间仍然为 O(n ^{2 )。}

另一种方法： 以下是上述递归代码的迭代实现

C++

              
                
                    #include <iostream>
using namespace std;
 
// iterative implementation
                        
int binarySearch(int a[], int item, int low, int high)
{
    while (low <= high) {
        int mid = low + (high - low) / 2;
                        
        if (item == a[mid])
            return mid + 1;
        else if (item > a[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
 
    return low;
}
 
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
                        
{
    int
                          i, loc, j, k, selected;
 
    for (i = 1; i < n; ++i) {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inserted
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}
 
// Driver Code
int main()
{
    int
                          a[]
        = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int
                          n = sizeof(a) / sizeof(a[0]), i;
 
    insertionSort(a, n);
 
    cout <<"Sorted array: \n";
    for (i = 0; i < n; i++)
        cout <<" "<< a[i];
 
    return 0;
}
 
// This code is contributed by shivanisinghss2110.

                  

              
            

C

              
                
                    #include <stdio.h>
                        
 
// iterative implementation
                        
int binarySearch(int a[], int item, int low, int high)
{
    while (low <= high) {
        int mid = low + (high - low) / 2;
                        
        if (item == a[mid])
            return mid + 1;
        else if (item > a[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
 
    return low;
}
 
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
                        
{
    int
                          i, loc, j, k, selected;
 
    for (i = 1; i < n; ++i) {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inserted
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}
 
// Driver Code
int main()
{
    int
                          a[]
        = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int
                          n = sizeof(a) / sizeof(a[0]), i;
 
    insertionSort(a, n);
 
    printf("Sorted array: \n");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
 
    return 0;
}
// contributed by tmeid
                        

                  

              
            

Java

              
                
                    import java.io.*;
 
class GFG {
 
// iterative implementation
                        
static int binarySearch(int a[], int
                          item, int low, int high)
                        
{
    while
                          (low <= high) {
        int mid = low + (high - low) / 2;
        if (item == a[mid])
            return mid + 1;
        else if (item > a[mid])
            low = mid + 1;
                        
        else
            high = mid - 1;
                        
    }
 
    return
                          low;
}
 
// Function to sort an array a[] of size 'n'
static void insertionSort(int a[], int
                          n)
{
    int
                          i, loc, j, k, selected;
 
    for
                          (i = 1; i < n; ++i) {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inserted
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc) {
            a[j + 1] = a[j];
                        
            j--;
        }
        a[j + 1] = selected;
    }
}
 
// Driver Code
public static void main (String[] args) 
{
    int
                          a[]
        = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int
                          n = a.length, i;
 
    insertionSort(a, n);
 
    System.out.println("Sorted array:");
    for
                          (i = 0; i < n; i++)
        System.out.print(a[i] +" ");
 
}
}
 
// This code is contributed by shivanisinghss2110.

                  

              
            

Python3

              
                
                    # iterative implementation
                        
def binarySearch(a, item, low, high):
    while
                          (low <= high):
        mid = low + (high -
                          low) //
                          2
        if (item == a[mid]):
                        
            return mid +
                          1
        elif (item > a[mid]):
            low = mid + 1
        else:
            high = mid - 1
    return
                          low
     
# Function to sort an array a[] of size 'n'
def insertionSort(a, n):
    for
                          i in range (n): 
        j = i - 1
        selected = a[i]
                        
         
        # find location where selected should be inserted
        loc = binarySearch(a, selected, 0, j)
         
        # Move all elements after location to create space
        while (j >= loc):
            a[j + 1] = a[j]
            j-=1
        a[j + 1] = selected
                        
 
# Driver Code
a = [37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54]
n = len(a)
                        
insertionSort(a, n)
print("Sorted array: ")
for i in range
                          (n):
    print(a[i], end=" ")
 
# This code is contributed by shivanisinghss2110

                  

              
            

C＃

              
                
                    using System;
 
class GFG {
 
// iterative implementation
                        
static int binarySearch(int []a, int
                          item, int low, int high)
                        
{
    while
                          (low <= high) {
        int mid = low + (high - low) / 2;
        if (item == a[mid])
            return mid + 1;
        else if (item > a[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
 
    return
                          low;
}
 
// Function to sort an array a[] of size 'n'
static void insertionSort(int []a, int
                          n)
{
    int
                          i, loc, j, selected;
 
    for
                          (i = 1; i < n; ++i) {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inserted
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}
 
// Driver Code
public static void Main (String[] args) 
{
    int
                          []a = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };
    int
                          n = a.Length, i;
 
    insertionSort(a, n);
 
    Console.WriteLine("Sorted array:");
    for
                          (i = 0; i < n; i++)
        Console.Write(a[i] +" ");
 
}
}
 
// This code is contributed by shivanisinghss2110

                  

              
            

JavaScript

              
                
                    <script>
// iterative implementation
                        
function binarySearch( a,  item,  low,  high)
{
    while
                          (low <= high) {
        var mid = low + (high - low) / 2;
        if (item == a[mid])
            return mid + 1;
        else if (item > a[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
 
    return
                          low;
}
 
// Function to sort an array a[] of size 'n'
function insertionSort(a, n)
{
    var
                          i, loc, j, k, selected;
 
    for
                          (i = 1; i < n; ++i) {
        j = i - 1;
        selected = a[i];
 
        // find location where selected should be inserted
        loc = binarySearch(a, selected, 0, j);
 
        // Move all elements after location to create space
        while (j >= loc) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = selected;
    }
}
 
// Driver Code
    var
                          a = [ 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 ];
    var
                          n = a.length, i;
 
    insertionSort(a, n);
 
    document.write("Sorted array:" + "<br>");
                        
    for
                          (i = 0; i < n; i++)
        document.write(a[i] +" ");
 
 
// This code is contributed by shivanisinghss2110
</script>

                  

              
            

输出

排序数组：
0 12 17 23 31 37 46 54 72 88 100

如果您发现任何不正确的内容，或者您想分享有关上述主题的更多信息，请发表评论

折半插入排序 可视化交互式动画版

二分插入排序的应用：

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

实现二分插入排序的方法：

C++

C

Java

Python3

C＃

PHP

JavaScript

C++

C

Java

Python3

C＃

JavaScript

折半插入排序可视化交互式动画版