星期四, 九月 21, 2006

基本算法连载(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]);
}

}

2 条评论:

Franco Peña Campos 说...

Hey, I tested the code and it has a bug! Every random time with length>100 one of the elements that should be in the middle is translated to the end D:

Franco Peña Campos 说...

Check out my solution:
http://programmingtenacity.blogspot.pe/2016/05/library-sort.html