马老师Python全系列大师课
折半插入排序
算法分析：
虽然折半插入排序法与直接插入排序法相比较，改善了算法中比较次数的数量级，但其并未改变移动元素的时间耗费，所以折半插入排序的总的时间复杂度仍然是O(n2)。 较，因此插入n-1个元素的平均关键字的比较次数为O(nlog2n)。
虽然折半插入排序法与直接插入排序法相比较，改善了算法中比较次数的数量级，但其并未改变移动元素的时间耗费，所以折半插入排序的总的时间复杂度仍然是O(n2)。
void sort(Node[] nodes) {
Node x;
int low, mid, high = 0;
for (int i = 1; i < nodes.length; i++) {
x = nodes[i];
low = 0;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (x.key < nodes[mid].key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
for (int j = i - 1; j >= low; j--) {
nodes[j + 1] = nodes[j];
}
nodes[low] = x;
}
}
