直接和二进制插入排序

Question

你好我被要求通过使用二分搜索而不是线性提高插入排序。现在的问题是，由于数据比较，现在最好的情况是O（n log n），而不是O（n），这使得程序在某些情况下如果不是较慢，就等于。这里是我的二进制插入排序代码：

void InsertionSort(int data[], int size) 
{ 
    int index = -1; 
    for(int i = 1,temp,j;i<size;i++) 
    { 
     temp = data[i];//DM O(N) 
     int high = i,low = 0,mid;//DM O(N) 
     while(low <= high)//DC O(nlogn) 
     { 
      mid = (low + high) /2; 
      if(temp < data[mid]) 
      { 
       high = mid - 1; 
       index = mid; 
      } 

      else if (temp > data[mid]) 
      { 
       low = mid + 1;  
      } 

      else if(data[mid] == temp) 
      { 
       index = mid; 
       break; 
      } 

     } 
     for(j = i;j > index;j--) 
     { 
      data[j] = data[j-1];//DC Worst Case O(n*n) but the exact is summation of n(n+1)/2 nad best case o(1) 
     } 
     data[j] = temp;//DM O(n) 
    } 
} 

Answer 1

你可以开始你的二进制搜索与有利于最好的情况下的偏见阶段。而不是直接去(low+high)/2的，开始在位置i-1，然后i-2，然后i-4，i-8，i-16，i-32 ......直到找到一个更小的元素，或者直到i-whatever变得比low低。然后继续进行普通的二分查找。

请注意，此优化需要付出代价。最好的情况---排序或几乎排序的数据---需要O（N）个时间，但是对于简单的二进制搜索版本，平均情况和最坏情况会稍微慢一些。

void InsertionSort (int data[], int size) 
{ 
    int i, j, high, low, mid, hop; 
    int temp; 

    for (i=1; i<size; i++) 
    { 
     temp = data[i]; 

     high = i; 
     low = 0; 
     hop = 1; 

     do 
     { 
      mid = high - hop; 
      hop <<= 1; 

      if (temp < data[mid]) 
       high = mid; 
      else 
       low = mid + 1; 
     } 
     while (low+hop <= high); 

     while (low != high) 
     { 
      mid = (low + high)/2; 

      if (temp < data[mid]) 
       high = mid; 
      else 
       low = mid + 1; 
     } 

     for(j=i; j>low; j--) 
      data[j] = data[j-1]; 

     data[j] = temp; 
    } 
} 

还要注意high分配mid而不是mid+1。其中temp==data[mid]的处理与temp>data[mid]的情况完全相同。这是为了保持插入排序的良好属性：它是一个stable sort。但是，排序纯整数时没有区别。

Answer 2

你也可以更换其他最后：用简单的else 因为很明显这是为真else if(data[mid] == temp)如果前两者是不正确的......