注意,本文不是字符串排序,是字符串数组的排序。
成都创新互联专业为企业提供建安网站建设、建安做网站、建安网站设计、建安网站制作等企业网站建设、网页设计与制作、建安企业网站模板建站服务,十年建安做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。
方法分别是:
1、低位优先键索引排序
2、高位优先建索引排序
3、Java自带排序(经过调优的归并排序)
4、冒泡排序
5、快速排序
6、三向快速排序
时间复杂度:
本文中使用的例子是一个5757行的随机字符串数组文本TXT,实际测试结果:
稳定的排序是:
低位优先:
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文件下载:
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》
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持创新互联。
分享题目:java实现6种字符串数组的排序(Stringarraysort)
浏览地址:https://www.cdcxhl.com/article48/gphhep.html
成都网站建设公司_创新互联,为您提供网页设计公司、网站排名、虚拟主机、网站内链、自适应网站、品牌网站设计
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联