题解 | #字符串排序#

字符串排序

http://www.nowcoder.com/practice/5af18ba2eb45443aa91a11e848aa6723

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int num=sc.nextInt();
        String[] str=new String[num+1];
        //堆排序第一个字符串是换行符
        sc.nextLine();
        //队排序从第一个元素开始要不 i=0 i*2=0
        for(int i=1;i<=num;i++){
            str[i]=sc.nextLine();
        }
        //堆排序
        duisort(str);
    }
    //堆排序
    static void duisort(String[] str){
        //先建立小根堆
        int last=(str.length-1)/2;
        for(int i=last;i>0;i--){
            singlesort(str,i,str.length);
        }
        int len=str.length;
        while(len>1){
            System.out.println(str[1]);
            //最后一个元素提到str[0]
            str[1]=str[len-1];
            len--;
            singlesort(str,1,len);
        }
    }
    //下坠 比较
    //last是元素个数
    static void singlesort(String[] str,int i,int last){
        String min;int minindex,res;
        //
        while(i*2<last){
            if(i*2+1<last){
                res= sort(str[i*2],str[i*2+1]);//1为小
                //不要再[]内写表达式
//                 res==1?max=str[left]:max=str[right];
//                 res==1?maxindex=i*2:maxindex=i*2+1;
                if(res==1){
                    min=str[i*2];
                    minindex=i*2;
                }else{
                    min=str[i*2+1];
                    minindex=i*2+1;
                }
            }
            else{
                min=str[i*2];
                minindex=i*2;
            }
            res=sort(min,str[i]);
            if(res==1){
                str[minindex]=str[i];
                str[i]=min;
                i=minindex;
            }
            else return;
        }
    }
    static int sort(String str1,String str2){
        int i1=0,i2=0;
        int len1=str1.length();
        int len2=str2.length();
        while(i1<len1&&i2<len2){
            if(str1.charAt(i1)<str2.charAt(i2)) return 1;
            else if(str1.charAt(i1)>str2.charAt(i2)) return -1;
            else if(str1.charAt(i1)==str2.charAt(i2)){
                i1++;
                i2++;
            }
        }
        if(i1==len1&&i2==len2) return 1;
        //先达到长度的长度小
        else return i1==len1?1:-1;
    }
}
全部评论

相关推荐

能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务