java实现6种字符串数组的排序(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();
    * .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文件下载：

words5_jb51.rar

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》

来源：https://www.cnblogs.com/starcrm/p/10736749.html