特色：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未满之前无需移动元素。
最好时间复杂度O(nlogn)
平均时间复杂度O(nlogn)
最坏时间复杂度O(n^2)
空间复杂度O(n)
是否稳定是
Library Sort基于折半查找的插入排序，插入时在元素附近空出一定位置，这样推入后移动元素的复杂度由原来的O(n)下降为平均O(1)，于是整个算法的复杂度达到O(nlogn)。当输入正序或倒序时，插入点都在同一位置，“留空位”的策略失效，这时就出现最坏复杂度O(n^2)。
/** 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));//标志gapint 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所在位置为gapwhile(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]);}}
如果觉得《library sort (图书馆排序)》对你有帮助，请点赞、收藏，并留下你的观点哦！
