思想：一个图书管理员需要按照字母顺序放置书本，当在书本之间留有一定空隙时，一本新书上架将无需移动随后的书本，可以直接插空隙。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]);
}
}
