特色: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]);
}
}
分享到:
相关推荐
A Sinusoidally-Modulated Leaky-Wave Antenna with Gapped Graphene Ribbons
export KKZONE=cn curl -sfL https://get-kk.kubesphere.io | sh - ...https://www.kubesphere.io/zh/docs/v3.4/installing-on-linux/introduction/air-gapped-installation/#%E9%83%A8%E7%BD%B2%E5%87%86%E5%A4%87
气隙激活示例 这是使用移动设备执行激活请求的气隙(离线)设备的许可证激活的示例客户端/服务器实现。 这种激活类型不仅限于服务器端应用程序,还可以用于台式机和本地软件。 该示例应用程序尚未100%投入生产,仅...
气密性工具
离线安装参考文档:https://kubesphere.io/zh/docs/v3.3/installing-on-linux/introduction/air-gapped-installation/
sort XMFA file by block (LCB) and generate gapped fasta files with fasta/xmfa coordinates This is accomplished by defining a multi-pass sort using sequence IDs found in the XMFA header. The primary ...
CUSHAW2是针对大型基因组(例如人类基因组)的快速且平行的缺口阅读比对。 通过将模拟数据集和真实数据集与人类基因组对齐进行的性能评估表明,就单端和双端对齐的对齐质量而言,CUSHAW2始终是排名最高的对齐器,...
化学爆破 BLASTing 化学库相似性搜索 用法 a) 格式化输入数据库 sh format.sh data/database.txt b) 相似度搜索 sh search.sh data... Gapped blast and psiblast: a new generation of protein database search progr
名称Bio::Cigar - 解析 CIGAR 字符串并将坐标转换为/从参考/查询概要 use 5.014;use Bio::Cigar;...描述Bio::Cigar 是一个小型库,用于解析 CIGAR 字符串(“Compact Idiosyncratic Gapped Alignment Report
这是因为生成器会在整个系统中创建相同的基本代码。 重新生成系统时,对代码的更改会在一个地方自动降落到系统的所有部分。 服务器端代码将在使用大多数操作系统的大多数计算机上运行。 生成的用户界面在浏览器中...
As a kind of two-dimensional transition metal dichalcogenide material, tungsten diselenide (WSe2) has attracted increasing attention, owing to its gapped electronic structure, relatively high carrier ...
缺损幅度和相位估计(Gapped Amplitude and Phase Estimation—GAPES),作为非参数化插值方法,按照谱估计加插值这一思路进行处理。 GAPES 方法的基础,是高分辨谱估计方法(Amplitude and Phase Estimation—APES)...
化学爆破 BLASTing 化学库相似性搜索 用法 a) 格式化输入数据库 sh format.sh data/database.txt b) 相似度搜索 sh search.sh ... Gapped blast and psiblast: a new generation of protein database search program
法姆Ruby 中 RFam 数据的轻型包装器。 提供两个模型, Rbfam::Family和Rbfam::Rna 。...family_id: integer, accession: string, sequence: text, gapped_sequence: text, from: integer, to: inte