k-移位数组上的插入排序时间复杂度

在一个k-移位数组上进行插入排序的时间复杂度可以分为两种情况：当k为常数时，复杂度为O(n^2)，当k为n（数组长度）时，复杂度可以降至O(nlogn)。

对于第一种情况，可以直接使用插入排序的代码实现，因为移位操作只需要常数时间。以下是代码示例：

def insertionsort(arr):
    for i in range(1,len(arr)):
        j = i-1
        key = arr[i]
        while (j>=0 and arr[j]>key):
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

对于第二种情况，我们可以使用希尔排序（Shell sort）或增量排序（Incremental insertion sort）的算法，以达到复杂度O(nlogn)。以下是增量排序的代码示例：

def insertion_sort(arr, start, gap):
    for i in range(start + gap, len(arr), gap):
        current_val = arr[i]
        pos = i
        while pos >= gap and arr[pos - gap] > current_val:
            arr[pos] = arr[pos - gap]
            pos -= gap
        arr[pos] = current_val

def shell_sort(arr):
    sublist_count = len(arr) // 2
    while sublist_count > 0:
        for start_position in range(sublist_count):
            insertion_sort(arr, start_position, sublist_count)

        print("After increments of size", sublist_count, "The list is", arr)

        sublist_count //= 2

    return arr