馬老師Python全系列大師課
折半插入排序
算法分析：
雖然折半插入排序法與直接插入排序法相比較，改善了算法中比較次數(shù)的數(shù)量級，但其并未改變移動元素的時間耗費，所以折半插入排序的總的時間復雜度仍然是O(n2)。 較，因此插入n-1個元素的平均關鍵字的比較次數(shù)為O(nlog2n)。
?雖然折半插入排序法與直接插入排序法相比較，改善了算法中比較次數(shù)的數(shù)量級，但其并未改變移動元素的時間耗費，所以折半插入排序的總的時間復雜度仍然是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;
? ? ? ?}
? ?}
