锐客网

  1. 首页 > it技术 > >

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

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) { for (int j = i+1; 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)//快速排序算法 { Stringf,t; int rtemp,ltemp; ltemp=left; rtemp=right; f=arr[(left+right)/2]; //分界值 while(ltemp0) { --rtemp; } if(ltemp<=rtemp) { t=arr[ltemp]; arr[ltemp]=arr[rtemp]; arr[rtemp]=t; --rtemp; ++ltemp; } } if(ltemp==rtemp) { ltemp++; } if(left

三向快速：
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
【6种字符串数组的java排序|6种字符串数组的java排序 (String array sort)】ReadFiledata帮助类：
6种字符串数组的java排序|6种字符串数组的java排序 (String array sort)
文章图片
6种字符串数组的java排序|6种字符串数组的java排序 (String array sort)
文章图片
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 txt2List(File file){ try{ BufferedReader br = new BufferedReader(new FileReader(file)); List list = new ArrayList(); 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){ returntxt2List(file).toArray(); }}

View Code
参考书目：《算法 4th》
posted @ 2019-04-19 16:29 昕友软件开发 阅读( ...) 评论( ...) 编辑 收藏

    推荐阅读


    上一篇：找一个能相伴一生的人究竟有多难?

    下一篇：window10|window10 无法搜索本地应用