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，实际测试结果：
- 低位优先键索引排序：5ms
- 高位优先键索引排序：8ms
- JAVA自带排序：9ms
- 冒泡排序：284ms
- 快速排序：8ms
- 三向快速排序：12ms
稳定的排序是：
- 低位优先键索引排序
- 高位优先建索引排序
- 归并排序（Java自带的排序算法），速度还行，关键是保持循环情况下的顺序稳定
低位优先：
publicstaticvoidsort(String[]a,intw){
intn=a.length;
intR=256;//extendASCIIalphabetsize
String[]aux=newString[n];
for(intd=w-1;d>=0;d--){
int[]count=newint[R+1];
for(inti=0;i
高位优先：https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/MSD.java.html
JAVA自带排序：
Arrays.sort(arr);
冒泡：
publicstaticvoidbubblingSort(String[]arr){
intsize=arr.length;
for(inti=0;i0){
Stringtemp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
快速：
staticvoidquickSort(String[]arr,intleft,intright)//快速排序算法
{
Stringf,t;
intrtemp,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
验证代码：
publicstaticvoidmain(String[]args){
URLpath=SortWords.class.getResource("");
//不定长随机单词1000个
//Filefile=newFile(path.getPath()+"/1000words.txt");
//长度为5的单词，5757个
Filefile=newFile(path.getPath()+"/words5.txt");
Filefile1=newFile(path.getPath()+"/words5.txt");
Filefile2=newFile(path.getPath()+"/words5.txt");
Filefile3=newFile(path.getPath()+"/words5.txt");
Filefile4=newFile(path.getPath()+"/words5.txt");
Filefile5=newFile(path.getPath()+"/words5.txt");
String[]arr=(String[])ReadFiledata.txt2List(file).toArray(newString[0]);
//排序前
for(Strings:arr){
//System.out.println(s.toString());
}
//##############低位优先
TimeMillis.setStart();
LSD.sort(arr,5);
TimeMillis.setEnd("低位优先键索引排序：");
//排序后
for(Strings:arr){
//System.out.println(s.toString());
}
//##############高位优先
String[]arr1=(String[])ReadFiledata.txt2List(file1).toArray(newString[0]);
TimeMillis.setStart();
MSD.sort(arr1);
TimeMillis.setEnd("高位优先键索引排序：");
//排序后
for(Strings:arr1){
//System.out.println(s.toString());
}
//##############JAVA自带排序
String[]arr2=(String[])ReadFiledata.txt2List(file2).toArray(newString[0]);
TimeMillis.setStart();
Arrays.sort(arr2);
TimeMillis.setEnd("JAVA自带排序：");
//排序后
for(Objects:arr2){
//System.out.println(s.toString());
}
//##############冒泡排序
String[]arr3=(String[])ReadFiledata.txt2List(file3).toArray(newString[0]);
TimeMillis.setStart();
bubblingSort(arr3);
TimeMillis.setEnd("冒泡排序：");
//排序后
for(Strings:arr3){
//System.out.println(s.toString());
}
//##############快速排序
String[]arr4=(String[])ReadFiledata.txt2List(file4).toArray(newString[0]);
TimeMillis.setStart();
quickSort(arr4,0,5756);
TimeMillis.setEnd("快速排序：");
//排序后
for(Strings:arr4){
//System.out.println(s.toString());
}
//##############三向快速排序
String[]arr5=(String[])ReadFiledata.txt2List(file5).toArray(newString[0]);
TimeMillis.setStart();
Quick3string.sort(arr5);
TimeMillis.setEnd("三向快速排序：");
//排序后
for(Strings:arr5){
//System.out.println(s.toString());
}
}
运行多次结果相近：
低位优先键索引排序：8ms
高位优先键索引排序：10ms
JAVA自带排序：15ms
冒泡排序：315ms
快速排序：9ms
三向快速排序：13ms
用到的数据txt文件下载：
words5_jb51.rar
ReadFiledata帮助类：
importjava.io.BufferedReader;
importjava.io.File;
importjava.io.FileReader;
importjava.util.ArrayList;
importjava.util.List;
publicclassReadFiledata{
publicstaticStringtxt2String(Filefile){
StringBuilderresult=newStringBuilder();
try{
BufferedReaderbr=newBufferedReader(newFileReader(file));
Strings=null;
while((s=br.readLine())!=null){
result.append(System.lineSeparator()+s);
}
br.close();
}catch(Exceptione){
e.printStackTrace();
}
returnresult.toString();
}
publicstaticListtxt2List(Filefile){
try{
BufferedReaderbr=newBufferedReader(newFileReader(file));
Listlist=newArrayList();
Strings;
while((s=br.readLine())!=null){
list.add(s);
}
br.close();
returnlist;
}catch(Exceptione){
e.printStackTrace();
}
returnnull;
}
publicstaticObject[]txt2Array(Filefile){
returntxt2List(file).toArray();
}
}
参考书目：《算法4th》
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。