线段树做大数据排序（未完）

//比较字符基类大小 相同返回0，str1>str2 返回1，str1<str2 返回-1，
function str_compare(str1,str2){
    let index=0;
    let dis=0;
    while (dis===0&&index<str1.length){
        if(str1.charCodeAt(index)>str2.charCodeAt(index)){
            dis=1
        }else if(str1.charCodeAt(index)<str2.charCodeAt(index)){
            dis=-1
        }else{
            index++;
            if(index>str2.length){
                dis=1;
            }
        }
    }
    if(dis===0&&index<str2.length){
        dis=-1
    }
    return dis;
}
//用二分法查找最近的字符位置
function str_find(str,hasSortArr) {
    let l=0,r=hasSortArr.length;
    let index=-1;
    if(hasSortArr.length>0){
        const ri=str_compare(str,hasSortArr[r-1]);
        if(ri===1){
            return [r,-1]
        }else if(ri===0){
            return [r-1,r-1]
        }else{
            r=r-1;
        }
        const li=str_compare(str,hasSortArr[0]);
        if(li===-1){
            return [0,-1]
        }else if(li===0){
            return [0,0]
        }else{
            l=l+1;
        }
        while(r-l>0){
            const m=(l+r)>>1;
            //比较下坐标大小
            const order=str_compare(str,hasSortArr[m])
            if(order===1){
                l=Math.max(l+1,m)
            }else if(order===-1){
                r=Math.min(r-1,m)
            }else{
                l=r=m;
                index=m;
            }
        }
    }
    return [(l+r)>>1,index]
}
//字符排序,isOnly 是否去重
function str_sort(arr,isOnly) {
    const sa=[]
    for(let i=0;i<arr.length;i++){
        const [n,index]=str_find(arr[i],sa);
        if(!isOnly||index===-1){
            sa.splice(n,0,arr[i])
        }
    }
    return sa;
}
//线段树做大数据排序
const tree={
    init(){
        this.data=[
            {
                path:‘‘,
                range:[‘12‘,‘22‘],
                length:0
            }
        ]
    },
    sort(){
        let index=0;
        while (index<this.data.length){
            const range1=this.data[index].range;
            const arr1=getArrByPath(this.data[index].path)
            for(let i=index+1;i<this.data.length;i++){
                //排序不对，需要交换
                if(str_compare(range1[1],this.data[i].range[0])===1){
                    //第一个的最大值和第二个的最小值做交换，
                    const arr2=getArrByPath(this.data[i].path)
                    do{
                        const str2=arr2.shift()
                        const [n1,index1]=str_find(str2,arr1);
                        str2.splice(n1,0,str2)

                        const str1=arr1.pop()
                        const [n2,index2]=str_find(str1,arr2);
                        arr2.splice(n2,0,str1)
                    }while (str_compare(arr1[arr1.length-1],arr2[0])===1)
                    range1[0]=arr1[0]
                    range1[1]=arr1[arr1.length-1]
                    this.data[i].range[0]=arr2[0]
                    this.data[i].range[1]=arr2[arr2.length-1]
                }
            }
        }

    },
    find(){

    }
}