题解 | #字符串排序#

import java.util.*;
public class Main {
    /**********************************************************************************/
    // 自定义比较器
    public static class ComparaString implements Comparator<String> {
        public int compare(String str1, String str2) {
            int len1 = str1.length();
            int len2 = str2.length();
            int p1 = 0;
            int p2 = 0;
            char[] chrs1 = str1.toCharArray();
            char[] chrs2 = str2.toCharArray();
            while (p1 < len1 && p2 < len2) {
                if (chrs1[p1] < chrs2[p2]) {
                    return -1;
                } else if (chrs1[p1] > chrs2[p2]) {
                    return 1;
                } else {
                    p1++;
                    p2++;
                }
            }
            if (len1 < len2) {
                return -1;
            } else if (len1 > len2) {
                return 1;
            } else {
                return 0;
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.valueOf(scan.nextLine().trim());
        ArrayList<String> arrayList = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            arrayList.add(scan.nextLine());
        }
        // 调用自定义的比较器进行排序
        arrayList.sort(new ComparaString());
        for (String str : arrayList) {
            System.out.println(str);
        }
        // 调用自己实现的快速排序算法
        /*
        String[] strs = new String[arrayList.size()];
        for (int i = 0; i < arrayList.size(); i++) {
            strs[i] = arrayList.get(i);
        }
        quickSort(strs);
        for (String str : strs) {
            System.out.println(str);
        }
        */
    }
    /**********************************************************************************/
    // 快速排序算法
    public static void quickSort(String[] strs) {
        if (null == strs || strs.length < 2) {
            return;
        }
        process(strs, 0, strs.length - 1);
    }
    public static void process(String[] strs, int start, int end) {
        if (start > end) {
            return;
        }
        int l = start - 1;
        int r = end + 1;
        int p = start;
        String str = strs[end];
        while (p < r) {
            if (compare(strs[p], str) == -1) {
                swap(strs, p++, ++l);
            } else if (compare(strs[p], str) == 1) {
                swap(strs, p, --r);
            } else {
                p++;
            }
        }
        process(strs, start, l);
        process(strs, r, end);
    }
    public static void swap(String[] strs, int p1, int p2) {
        String tmp = strs[p1];
        strs[p1] = strs[p2];
        strs[p2] = tmp;
    }
    public static int compare(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int p1 = 0;
        int p2 = 0;
        char[] chrs1 = str1.toCharArray();
        char[] chrs2 = str2.toCharArray();
        while (p1 < len1 && p2 < len2) {
            if (chrs1[p1] < chrs2[p2]) {
                return -1;
            } else if (chrs1[p1] > chrs2[p2]) {
                return 1;
            } else {
                p1++;
                p2++;
            }
        }
        if (len1 < len2) {
            return -1;
        } else if (len1 > len2) {
            return 1;
        } else {
            return 0;
        }
    }
}