为什么使用二分搜索的插入排序比使用线性搜索的插入排序慢?
使用线性搜索进行插入排序的代码:
void InsertionSort(int data[], int size)
{
int i=0, j=0, temp=0;
for(i=1; i<size; i++)
{
temp = data[i];
for (j=i-1; j>=0; j--)
{
if(data[j]>temp)
data[j+1]=data[j];
else
break;
}
data[j+1] = temp;
}
}
使用二分查找进行插入排序的代码:
void InsertionSort (int A[], int n)
{
int i, temp;
for (i = 1; i < n; i++)
{
temp = A[i];
/* Binary Search */
int low = 0, high = i, k;
while (low<high)
{
int mid = (high + low) / 2;
if (temp <= A[mid])
high = mid;
else
low = mid+1;
}
for (k = i; k > high; k--)
A[k] = A[k - 1];
A[high] = temp;
}
}
尽管对于平均情况,使用二分搜索的比较次数 = O(nlogn),使用线性搜索的比较次数 = O(n^2)。
原始插入排序是线性搜索,修改后的插入排序是二分搜索。
因为第一种情况下搜索和移动是结合在一起的,而第二种情况下搜索只是额外的工作。
与移动整数相比,比较整数的成本较低。考虑除法、循环开销、每次循环迭代中采取的条件跳转与非采取的条件跳转等...
PS。事实上,在线性搜索版本中,内部循环通常如下所示:
.L5:
leaq -1(%rcx), %rsi
movl 4(%rdi,%rsi,4), %eax
cmpl %eax, %r9d
jge .L3
movq %rcx, %r8
movq %rsi, %rcx
subl $1, %edx
movl %eax, 4(%rdi,%r8,4)
cmpl $-1, %edx
jne .L5
movq $-1, %rcx
.L3:
其中
jge .L3
仅执行一次,并且可以合理地预期该分支将被预测为不被采用,并且不会对管道产生不利影响。
至于其他版本的内循环,我不想看:)
PS。顺便说一句,线性搜索也有更好的局部性,而二分搜索则到处跳跃。