6种字符串数组的java排序 (String array sort)

注意，本文不是字符串排序，是字符串数组的排序。

方法分别是：

1、低位优先键索引排序
2、高位优先建索引排序
3、Java自带排序（经过调优的归并排序）
4、冒泡排序
5、快速排序
6、三向快速排序

时间复杂度：

最慢的肯定是冒泡，O(n的平方)
最快的是快速排序，平均 O(nlogn)
低位优先，O(nW),W是字符串长度，在字符串长度较短情况下和快速排序时间应该很接近
高位优先，O(n) - O(nW)
三向快速排序，O(n) - O(nW)

本文中使用的例子是一个5757行的随机字符串数组文本TXT，实际测试结果：

低位优先键索引排序：5 ms

高位优先键索引排序：8 ms

JAVA自带排序：9 ms

冒泡排序：284 ms

快速排序：8 ms

三向快速排序：12 ms

稳定的排序是：

低位优先键索引排序
高位优先建索引排序
归并排序（Java自带的排序算法），速度还行，关键是保持循环情况下的顺序稳定

低位优先：

public static void sort(String[] a, int w) {

        int n = a.length;

        int R = 256;   // extend ASCII alphabet size

        String[] aux = new String[n];

        for (int d = w-1; d >= 0; d--) {

            int[] count = new int[R+1];

            for (int i = 0; i < n; i++)

                count[a[i].charAt(d) + 1]++;

            for (int r = 0; r < R; r++)

                count[r+1] += count[r];

            for (int i = 0; i < n; i++)

                aux[count[a[i].charAt(d)]++] = a[i];

            for (int i = 0; i < n; i++)

                a[i] = aux[i];

        }

    }

高位优先：

https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/MSD.java.html

JAVA自带排序：

Arrays.sort(arr);

冒泡：

    public static void bubblingSort(String[] arr) {

        int size = arr.length;

        for(int i = 0; i<size-1; i++) {

             for (int j = i+1; j<arr.length; j++) {

                if(arr[i].compareTo(arr[j])>0) {

                   String temp = arr[i];

                   arr[i] = arr[j];

                   arr[j] = temp;

                }

             }

          }

    }

快速：

static void quickSort(String[] arr,int left,int right)            //快速排序算法

    {

        String  f,t;

        int rtemp,ltemp;

        ltemp=left;

        rtemp=right;

        f=arr[(left+right)/2];                        //分界值

        while(ltemp<rtemp)

        {

            while(arr[ltemp].compareTo(f)<0)

            {

                ++ltemp;

            }

            while(arr[rtemp].compareTo(f)>0)

            {

                --rtemp;

            }

            if(ltemp<=rtemp)

            {

                t=arr[ltemp];

                arr[ltemp]=arr[rtemp];

                arr[rtemp]=t;

                --rtemp;

                ++ltemp;

            }

        }

        if(ltemp==rtemp)

        {

            ltemp++;

        }

        if(left<rtemp)

        {

            quickSort(arr,left,ltemp-1);            //递归调用

        }

        if(ltemp<right)

        {

            quickSort(arr,rtemp+1,right);            //递归调用

        }

    }

三向快速：

https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick3string.java.html

验证代码：

public static void main(String[] args) {

        URL path = SortWords.class.getResource("");

        //不定长随机单词1000个

        //File file = new File(path.getPath()+"/1000words.txt");

        //长度为5的单词，5757个

        File file = new File(path.getPath()+"/words5.txt");

        File file1 = new File(path.getPath()+"/words5.txt");

        File file2 = new File(path.getPath()+"/words5.txt");

        File file3 = new File(path.getPath()+"/words5.txt");

        File file4 = new File(path.getPath()+"/words5.txt");

        File file5 = new File(path.getPath()+"/words5.txt");

        String[] arr = (String[])ReadFiledata.txt2List(file).toArray(new String[0]);

        //排序前

        for(String s : arr) {

            //System.out.println(s.toString());

        }

        //##############低位优先

        TimeMillis.setStart();

        LSD.sort(arr,5);

        TimeMillis.setEnd("低位优先键索引排序：");

        //排序后

        for(String s : arr) {

            //System.out.println(s.toString());

        }

        //##############高位优先

        String[] arr1 = (String[])ReadFiledata.txt2List(file1).toArray(new String[0]);

        TimeMillis.setStart();

        MSD.sort(arr1);

        TimeMillis.setEnd("高位优先键索引排序：");

        //排序后

        for(String s : arr1) {

            //System.out.println(s.toString());

        }

      //##############JAVA自带排序

        String[] arr2 = (String[])ReadFiledata.txt2List(file2).toArray(new String[0]);

        TimeMillis.setStart();

        Arrays.sort(arr2);

        TimeMillis.setEnd("JAVA自带排序：");

        //排序后

        for(Object s : arr2) {

            //System.out.println(s.toString());

        }

      //##############冒泡排序

        String[] arr3 = (String[])ReadFiledata.txt2List(file3).toArray(new String[0]);

        TimeMillis.setStart();

        bubblingSort(arr3);

        TimeMillis.setEnd("冒泡排序：");

        //排序后

        for(String s : arr3) {

            //System.out.println(s.toString());

        }

      //##############快速排序

        String[] arr4 = (String[])ReadFiledata.txt2List(file4).toArray(new String[0]);

        TimeMillis.setStart();

        quickSort(arr4,0,5756);

        TimeMillis.setEnd("快速排序：");

        //排序后

        for(String s : arr4) {

            //System.out.println(s.toString());

        }

      //##############三向快速排序

        String[] arr5 = (String[])ReadFiledata.txt2List(file5).toArray(new String[0]);

        TimeMillis.setStart();

        Quick3string.sort(arr5);

        TimeMillis.setEnd("三向快速排序：");

        //排序后

        for(String s : arr5) {

            //System.out.println(s.toString());

        }

    }

运行多次结果相近：

低位优先键索引排序：8 ms

高位优先键索引排序：10 ms

JAVA自带排序：15 ms

冒泡排序：315 ms

快速排序：9 ms

三向快速排序：13 ms

用到的数据txt文件下载：

https://files.cnblogs.com/files/starcrm/words5.zip

ReadFiledata帮助类：

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.util.ArrayList;

import java.util.List;

public class ReadFiledata {

    public static String txt2String(File file){

        StringBuilder result = new StringBuilder();

        try{

            BufferedReader br = new BufferedReader(new FileReader(file));

            String s = null;

            while((s = br.readLine())!=null){

                result.append(System.lineSeparator()+s);

            }

            br.close();

        }catch(Exception e){

            e.printStackTrace();

        }

        return result.toString();

    }

    public static List<String> txt2List(File file){

        try{

            BufferedReader br = new BufferedReader(new FileReader(file));

            List<String> list = new ArrayList<String>();

            String s;

            while((s = br.readLine())!=null){

                list.add(s);

            }

            br.close();

            return list;

        }catch(Exception e){

            e.printStackTrace();

        }

        return null;

    }

    public static Object[] txt2Array(File file){

        return  txt2List(file).toArray();

    }

}

参考书目：《算法 4th》

巴特西

6种字符串数组的java排序 (String array sort)

最新文章

热门文章