注意，本文不是字符串排序，是字符串?dāng)?shù)組的排序。

方法分別是：

1、低位優(yōu)先鍵索引排序

2、高位優(yōu)先建索引排序

3、java自帶排序(經(jīng)過調(diào)優(yōu)的歸并排序)

4、冒泡排序

5、快速排序

6、三向快速排序

時間復(fù)雜度：

最慢的肯定是冒泡，o(n的平方)

最快的是快速排序，平均 o(nlogn)

低位優(yōu)先，o(nw),w是字符串長度，在字符串長度較短情況下和快速排序時間應(yīng)該很接近

高位優(yōu)先，o(n) - o(nw)

三向快速排序，o(n) - o(nw)

本文中使用的例子是一個5757行的隨機字符串?dāng)?shù)組文本txt，實際測試結(jié)果：

低位優(yōu)先鍵索引排序：5 ms

高位優(yōu)先鍵索引排序：8 ms

java自帶排序：9 ms

冒泡排序：284 ms

快速排序：8 ms

三向快速排序：12 ms

穩(wěn)定的排序是：

低位優(yōu)先鍵索引排序

高位優(yōu)先建索引排序

歸并排序(java自帶的排序算法)，速度還行，關(guān)鍵是保持循環(huán)情況下的順序穩(wěn)定

低位優(yōu)先：

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];

}

}

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) //快速排序算法

{

string f,t;

int rtemp,ltemp;

ltemp=left;

rtemp=right;

f=arr[(left+right)/2]; //分界值

while(ltemp

{

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

{

quicksort(arr,left,ltemp-1); //遞歸調(diào)用

}

if(ltemp

{

quicksort(arr,rtemp+1,right); //遞歸調(diào)用

}

}

三向快速：

驗證代碼：

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());

}

//##############低位優(yōu)先

timemillis.setstart();

lsd.sort(arr,5);

timemillis.setend("低位優(yōu)先鍵索引排序：");

//排序后

for(string s : arr) {

//system.out.println(s.tostring());

}

//##############高位優(yōu)先

string[] arr1 = (string[])readfiledata.txt2list(file1).toarray(new string[0]);

timemillis.setstart();

msd.sort(arr1);

timemillis.setend("高位優(yōu)先鍵索引排序：");

//排序后

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());

}

}

運行多次結(jié)果相近：

低位優(yōu)先鍵索引排序：8 ms

高位優(yōu)先鍵索引排序：10 ms

java自帶排序：15 ms

冒泡排序：315 ms

快速排序：9 ms

三向快速排序：13 ms

用到的數(shù)據(jù)txt文件下載：

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 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();

}

}

參考書目：《算法 4th》

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持萬仟網(wǎng)。

希望與廣大網(wǎng)友互動？？

點此進(jìn)行留言吧！

總結(jié)

以上是生活随笔為你收集整理的java sort 字符串_java实现6种字符串数组的排序(String array sort)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。