基本算法连载（8）－Library Sort(gapped insertion sort)

特色：Library sort优于传统的插入排序（时间复杂度为O(n^2))，它的时间复杂度为O（nlogn），采用了空间换时间的策略。
思想：一个图书管理员需要按照字母顺序放置书本，当在书本之间留有一定空隙时，一本新书上架将无需移动随后的书本，可以直接插空隙。Library sort的思想就源于此。
实现：有n个元素待排序，这些元素被插入到拥有(1+e)n个元素的数组中。每次插入2^(i-1)个元素，总共需要插logn趟。这2^(i-1)个元 素将被折半插入到已有的2^(i-1)个元素中。因此，插入i趟之后，已有2^i个元素插入数组中。此时，执行rebalance操作，原有处在(1+ e)2^i个位置的元素将被扩展到(2+2e)2^i个位置。这样，在做插入时，由于存在gap，因此在gap未满之前无需移动元素。
具体代码：

/*
* length：待排序元素个数
* elements：待排序数组
* factor：常数因子
*/
void librarySort(int length,float factor,int elements[]){
 int i,j;
 //扩展后的数组长度
 int expandedLen = (int)((1+factor)*length);
 int* orderedElem = (int*) malloc(expandedLen*sizeof(int));
  
 //标志gap
 int flag = 1<<31;
 for(i=0;i<expandedLen;i++){
  orderedElem[i] = flag;
 }
 
 int index = 1;
 int numOfIntercalatedElem = 1;
 orderedElem[0] = elements[0];
  
 while(length>numOfIntercalatedElem){
  //第i次插入2^(i-1)个元素
  for(j=0;j<numOfIntercalatedElem;j++){
   //待插入元素为elements[index]   
   //------------折半插入---------------
   int mid;
   int low = 0;
   int high = 2 * numOfIntercalatedElem - 1;
   while(low <= high){
    mid = (low + high)/2;
    
    int savedMid = mid;
    //如果mid所在位置为gap
    while(orderedElem[mid] == flag){     
     if(mid == high){
      //当向右遍历没有找到元素值时，改成向左遍历
      mid = savedMid - 1;
      while(orderedElem[mid] == flag){
       mid--;
      }
      break;
     }
     mid++;
    }
    
    if(elements[index] > orderedElem[mid]){
     low = mid + 1;
     //缩小范围
     while(orderedElem[low] == flag){
      low = low+1;
     }
    }else{
     high = mid - 1;
    }
   }   
   
   //把elements[index]插入到orderedElem[high+1]
   //当位置为空，没有存储元素值时...
   if(orderedElem[high+1] == flag){
    orderedElem[high+1] = elements[index];
   }else{
    //位置非空，首先往前挪动元素，如果前面已满，向后挪动元素
    int temp = high+1;
    while(orderedElem[temp] != flag){
     temp--;
     if(temp < 0){
      temp = high+1;
      break;
     }
    }     
    
    //向后移动 
    while(orderedElem[temp] !=flag){
     temp++;
    }     
     
    while(temp < high){
     orderedElem[temp] = orderedElem[temp+1];
     temp++;
    }
     
    while(temp > high+1){
     orderedElem[temp] = orderedElem[temp-1];
     temp--;
    }   
     
    orderedElem[temp] = elements[index];          
   }
   //--------------------------------- 
   index++;
   if(index == length){
    break;
   } 
  }
  
  numOfIntercalatedElem *=2;
  int generatedIndex;
  //Rebalance...
  for(j=numOfIntercalatedElem;j>0;j--){
   if(orderedElem[j] == flag){
    continue;
   }
   //原数组元素从i处移到2i处
   generatedIndex = j*2;
   if(generatedIndex >= expandedLen){    
    generatedIndex = expandedLen - 1;
    if(orderedElem[generatedIndex] != flag){
     break;
    }
   }   
   orderedElem[generatedIndex] = orderedElem[j];
   orderedElem[j] = flag;
  }     
 }
 //测试输出
 for(i=0;i<expandedLen;i++){
  printf("%d\n",orderedElem[i]);
 }
 
}