java实现6种字符串数组的排序(String array sort)
发布于 2020-8-11|
复制链接
摘记: 注意,本文不是字符串排序,是字符串数组的排序。方法分别是:1、低位优先键索引排序
2、高位优先建索引排序
3、Java自带排序(经过调优的归并排序)
4、冒泡排序
5、快速排序
6、三向快速排序
时间复杂度:
最慢的肯定是冒泡,O(n的 ..
注意,本文不是字符串排序,是字符串数组的排序。方法分别是: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自带的排序算法),速度还行,关键是保持循环情况下的顺序稳定
低位优先:
```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 高位优先:https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/MSD.java.htmlJAVA自带排序:
```java
Arrays.sort(arr);
```
冒泡:
```java
public static void bubblingSort(String[] arr) {
int size = arr.length;
for(int i = 0; i0) {
String temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
```
快速:
```java
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(ltemp0)
{
--rtemp;
}
if(ltemp三向快速:https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick3string.java.html验证代码:
```java
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文件下载:ReadFiledata帮助类:
```java
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){
return txt2List(file).toArray();
}
}
```