题解 | #字符串排序#

字符串排序

http://www.nowcoder.com/practice/5190a1db6f4f4ddb92fd9c365c944584

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String originalStr = scan.nextLine();
        StringBuffer sb = new StringBuffer("");
        int sign = 0;
        int start = 0;
        char[] chrs = originalStr.toCharArray();
        Queue<Character> queue = new LinkedList<>();
        for (int i = 0; i < chrs.length; i++) {
            char chr = chrs[i];
            if ((chr >= 'A' && chr <= 'Z') || (chr >= 'a' && chr <= 'z')) {
                if (sign == 0) {
                    sign = 1;
                    start = i;
                }
            } else {
                if (sign == 1) {
                    sign = 0;
                    sb.append(originalStr.substring(start, i));
                }
                queue.add(chr);
            }
        }
        if (sign == 1) {
            sb.append(originalStr.substring(start));
        }
        char[] newchrs = process(new String(sb)).toCharArray();
        int index = 0;
        StringBuffer ans = new StringBuffer("");
        for (int i = 0; i < chrs.length; i++) {
            char chr = chrs[i];
            if ((chr >= 'A' && chr <= 'Z') || (chr >= 'a' && chr <= 'z')) {
                ans.append(newchrs[index++]);
            } else {
                ans.append(queue.poll());
            }
        }
        System.out.println(ans);
    }
    public static String process(String str) {
        char[] chrs = str.toCharArray();
        // quickSort(chrs); // 快速排序具有不稳定性,所以不能使用
        mergeSort(chrs); // 归并排序具有稳定性,因此我们选择它
        StringBuffer sb = new StringBuffer("");
        for (char chr : chrs) {
            sb.append(chr);
        }
        return new String(sb);
    }
    /**********************************************************************************/
    public static void quickSort(char[] chrs) {
        if (null == chrs || chrs.length < 2) {
            return;
        }
        sort(chrs, 0, chrs.length - 1);
    }
    public static void sort(char[] chrs, int start, int end) {
        if (start >= end) {
            return;
        }
        int l = start - 1;
        int r = end + 1;
        int p = start;
        char compareChr = String.valueOf(chrs[end]).toLowerCase().charAt(0);
        while (p < r) {
            if (String.valueOf(chrs[p]).toLowerCase().charAt(0) < compareChr) {
                swap(chrs, p++, ++l);
            } else if (String.valueOf(chrs[p]).toLowerCase().charAt(0) > compareChr) {
                swap(chrs, p, --r);
            } else {
                p++;
            }
        }
        sort(chrs, start, l);
        sort(chrs, r, end);
    }
    public static void swap(char[] chrs, int p1, int p2) {
        char tmp = chrs[p1];
        chrs[p1] = chrs[p2];
        chrs[p2] = tmp;
    }
    /**********************************************************************************/
    public static void mergeSort(char[] chrs) {
        if (null == chrs || chrs.length < 2) {
            return;
        }
        process1(chrs, 0, chrs.length - 1);
    }
    public static void process1(char[] chrs, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + ((end - start) >> 1);
        process1(chrs, start, mid);
        process1(chrs, mid + 1, end);
        merge(chrs, start, mid, end);
    }
    public static void merge(char[] chrs, int start, int mid, int end) {
        char[] helper = new char[end - start + 1];
        int index = 0;
        int p1 = start;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= end) {
            helper[index++] = String.valueOf(chrs[p1]).toLowerCase().charAt(0) <= String.valueOf(chrs[p2]).toLowerCase().charAt(0) ? chrs[p1++] : chrs[p2++];
        }
        while (p1 <= mid) {
            helper[index++] = chrs[p1++];
        }
        while (p2 <= end) {
            helper[index++] = chrs[p2++];
        }
        for (int i = 0; i < helper.length; i++) {
            chrs[start + i] = helper[i];
        }
    }
}
全部评论
该牛油正在参与牛客写题解薅羊毛的活动,牛币,周边,京东卡超多奖品放送,活动进入倒计时!快来捡漏啦https://www.nowcoder.com/discuss/888949?source_id=profile_create_nctrack&channel=-1
点赞 回复 分享
发布于 2022-04-20 16:44

相关推荐

07-08 13:48
门头沟学院 C++
点赞 评论 收藏
分享
05-26 10:24
门头沟学院 Java
qq乃乃好喝到咩噗茶:其实是对的,线上面试容易被人当野怪刷了
找工作时遇到的神仙HR
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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