import time import random import copy def InsertSort(R): #对R[0..n-1]按递增有序进行直接插入排序 def BinInsertSort(R): #对R[0..n-1]按递增有序进行折半插入排序 for i in range(1,len(R)): if R[i]<R[i-1]: #反序时 tmp=R[i] #将R[i]保存到tmp中 low,high=0,i-1 while low<=high: #在R[low..high]中折半查找插入位置high+1 mid=(low+high)//2 #取中间位置 if tmp<R[mid]: high=mid-1 #插入点在左区间 else: low=mid+1 #插入点在右区间 for j in range(i-1,high,-1): #元素集中后移 R[j+1]=R[j] R[high+1]=tmp #插入原来的R[i]

这段代码实现了直接插入排序和折半插入排序两种算法，可以按照以下方式补全代码：

import time
import random
import copy

def InsertSort(R):
    # 对R[0..n-1]按递增有序进行直接插入排序
    for i in range(1, len(R)):
        if R[i] < R[i-1]:  # 反序时
            tmp = R[i]  # 将R[i]保存到tmp中
            j = i - 1
            while j >= 0 and tmp < R[j]:
                R[j+1] = R[j]  # 元素集中后移
                j -= 1
            R[j+1] = tmp  # 插入原来的R[i]

def BinInsertSort(R):
    # 对R[0..n-1]按递增有序进行折半插入排序
    for i in range(1, len(R)):
        if R[i] < R[i-1]:  # 反序时
            tmp = R[i]  # 将R[i]保存到tmp中
            low, high = 0, i-1
            while low <= high:  # 在R[low..high]中折半查找插入位置high+1
                mid = (low + high) // 2  # 取中间位置
                if tmp < R[mid]:
                    high = mid - 1  # 插入点在左区间
                else:
                    low = mid + 1  # 插入点在右区间
            for j in range(i-1, high, -1):  # 元素集中后移
                R[j+1] = R[j]
            R[high+1] = tmp  # 插入原来的R[i]

这里补全了直接插入排序和折半插入排序两个函数的实现部分。直接插入排序是一种基于比较的排序算法，它的时间复杂度为O(n^2)，但是对于小规模的数据，它的效率比较高。折半插入排序是在直接插入排序的基础上优化而来的，它的时间复杂度为O(nlogn)，比直接插入排序要快一些。