二分插入排序

选一种语言就能看到代码

def binary_insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        lo, hi = 0, i
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] <= key:
                lo = mid + 1
            else:
                hi = mid
        for j in range(i, lo, -1):
            a[j] = a[j - 1]
        a[lo] = key

function binaryInsertionSort(a) {
  for (let i = 1; i < a.length; i++) {
    const key = a[i];
    let lo = 0;
    let hi = i;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (a[mid] <= key) lo = mid + 1;
      else hi = mid;
    }
    for (let j = i; j > lo; j--) a[j] = a[j - 1];
    a[lo] = key;
  }
}

void binary_insertion_sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int lo = 0, hi = i;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (a[mid] <= key) lo = mid + 1;
            else hi = mid;
        }
        memmove(a + lo + 1, a + lo, sizeof(int) * (i - lo));
        a[lo] = key;
    }
}

void binary_insertion_sort(std::vector<int>& a) {
    for (size_t i = 1; i < a.size(); i++) {
        int key = a[i];
        size_t lo = 0, hi = i;
        while (lo < hi) {
            size_t mid = (lo + hi) / 2;
            if (a[mid] <= key) lo = mid + 1;
            else hi = mid;
        }
        for (size_t j = i; j > lo; j--) a[j] = a[j - 1];
        a[lo] = key;
    }
}

static void BinaryInsertionSort(int[] a) {
    for (int i = 1; i < a.Length; i++) {
        int key = a[i];
        int lo = 0, hi = i;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (a[mid] <= key) lo = mid + 1;
            else hi = mid;
        }
        Array.Copy(a, lo, a, lo + 1, i - lo);
        a[lo] = key;
    }
}

static void binaryInsertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int lo = 0, hi = i;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= key) lo = mid + 1;
            else hi = mid;
        }
        System.arraycopy(a, lo, a, lo + 1, i - lo);
        a[lo] = key;
    }
}