试图理解“二进制插入排序” ？ [英] Trying to understand "binary insertion sort" ?

问题描述

有谁能告诉我这个代码如何对数组进行排序？我不明白！这段代码如何降低常规插入排序的复杂性？

could anyone please tell me how this code sorts the array? i don't get it! and how is this code reducing the complexity of a regular insertion sort?

// 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 sould 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;
    }
}

推荐答案

从这里开始： https://www.bluffton.edu/~nesterd/java/SortingDemo.html [ ^ ]

这篇关于试图理解“二进制插入排序” ？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！