溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
注意，本文不是字符串排序，是字符串數組的排序。
方法分別是：
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》
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
