欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java实现6种字符串数组的排序(String array sort)

程序员文章站 2024-02-03 10:22:16
注意,本文不是字符串排序,是字符串数组的排序。 方法分别是: 1、低位优先键索引排序 2、高位优先建索引排序 3、java自带排序(经过调优的归并排序) 4、冒泡排序 5、...

注意,本文不是字符串排序,是字符串数组的排序。

方法分别是:

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自带的排序算法),速度还行,关键是保持循环情况下的顺序稳定

低位优先:

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文件下载:

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》

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。