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,实际测试结果:

  • 低位优先键索引排序: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文件下载:

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》

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

(0)

相关推荐

  • java判断字符串包含某个字符的实例方法

    java判断字符串是否包含某个字符的方法: 一.contains方法 1:描述 java.lang.String.contains() 方法返回true,当且仅当此字符串包含指定的char值序列 2:声明 public boolean contains(CharSequence s) 3:返回值 如果此字符串包含返回true,否则返回false. 4:实例 public static void main(String[] args) { String str = "abc"; bool

  • 基于Java实现文件和base64字符串转换

    这篇文章主要介绍了基于Java实现文件和base64字符串转换,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 项目中遇到需要将图片转成base64编码的字符串的需求,但是,考虑到扩展性,写了一个可以转换任务类型文件的方法.需要引入的包: <dependency> <groupId>commons-codec</groupId> <artifactId>commons-codec</artifactId

  • Java判断字符串是否是整数或者浮点数的方法

    如下所示: //判断整数(int) private boolean isInteger(String str) { if (null == str || "".equals(str)) { return false; } Pattern pattern = Pattern.compile("^[-\\+]?[\\d]*$"); return pattern.matcher(str).matches(); } //判断浮点数(double和float) private

  • java判断字符串是正整数的实例

    实例如下所示: public static boolean isPureDigital(String string) { if (isBlank(string)) return false; String regEx1 = "\\d+"; Pattern p; Matcher m; p = Pattern.compile(regEx1); m = p.matcher(string); if (m.matches()) return true; else return false; }

  • Java整数和字符串相互转化实例详解

    这篇文章主要介绍了Java整数和字符串相互转化实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 1.把int转化为String 以下三种方式把整形地i转化为字符串s,当然把Double.Float.Long转化为字符串操作一样. 1.String s=""+i; 2.String s=Integer.toString(i); 3.String s=String.valueOf(i); 2.把String转化为int型. 1.in

  • Java字符串替换函数replace()用法解析

    这篇文章主要介绍了Java字符串替换函数replace()用法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 replace(char oldChar, char newChar)返回一个新的字符串,它是通过用 newChar 替换此字符串中出现的所有 oldChar 而生成的 代码如下 import java.util.*; public class Main{ public static void main(String[] args)

  • java判断一个字符串是否是小数的方法

    函数介绍: matches() 方法用于检测字符串是否匹配给定的正则表达式. 语法: public boolean matches(String regex) 返回值: 在字符串匹配给定的正则表达式时,返回 true. StringUtils.isBlank(String str)判断某字符串是否为空或长度为0或由空白符(whitespace) 构成. 示例如下: /** * 判断是否是整数或者是小数 * @param str * @return true:是,false不是 */ privat

  • java中字符串转整数及MyAtoi方法的实现

    java中字符串转整数及MyAtoi方法的实现 该题虽然和我们正常使用的字符串转整数的API中函数不一致,但是通过增加了很多额外的边界或者异常处理,可以锻炼算法思维的敏锐性和处理边界异常等问题的能力. 思路:字符串题一般考查的都是边界条件.特殊情况的处理.所以遇到此题一定要问清楚各种条件下的输入输出应该是什么样的. 这里已知的特殊情况有: 能够排除首部的空格,从第一个非空字符开始计算 允许数字以正负号(+-)开头 遇到非法字符便停止转换,返回当前已经转换的值,如果开头就是非法字符则返回0 在转换

  • 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行的随机字符串数组

  • java String[]字符串数组自动排序的简单实现

    如下所示: import java.util.Arrays; public class xulie { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub String []str = {"abc","bca","cab","cba","aaa","111&

  • Java编程实现中英混合字符串数组按首字母排序的方法

    本文实例讲述了Java编程实现中英混合字符串数组按首字母排序的方法.分享给大家供大家参考,具体如下: 在Java中对于字符串数组的排序,我们可以使用Arrays.sort(String[])方法很便捷的进行排序.例如: String[] arrays = new String[] { "gyu", "sdf", "zf", "大同", "收到", "地方", "三等分"

  • java字符串数组进行大小排序的简单实现

    若是将两个字符串直接比较大小,会包:The operator > is undefined for the argument type(s) java.lang.String, java.lang.String的错误. 字符串比较大小可以用字符串长度或者是比较字符串内字符的ASCII码值,前者太简单,就不进行讲述记录. 字符串用ASCII码比较大小,规则是: 1.比较首字母的ASCII码大小 2.若是前面的字母相同,则比较之后的字母的ASCII码值 3.若是一个字符串从首字母开始包含另一个字符串

  • java如何给对象按照字符串属性进行排序

    目录 给对象按照字符串属性进行排序 三种方法实现字符串排序 排序方法概述 键索引计数法 低位优先的字符串排序(LSD) 高位优先的字符串排序(MSD) 三向字符串快速排序 给对象按照字符串属性进行排序 在java中对象进行排序,排序的属性是string,我们只需要实现Comparator接口,然后实现比较的方式. public class StringSort { public static void main(String[] args) { test1(); } // 方式1: public

  • Java实现字符串的分割(基于String.split()方法)

    目录 前言 一.JDK-1.8-API文档说明(推荐阅读) 二.简单的使用 1.单个字符分隔 2.正则表达式 三.Java源码分析 1.源代码的测试代码 2.源代码运行原理图示 3.解读完代码后的总结(推荐阅读) 四.limit参数使用区别 1.limit=0 2.limit<0 3.limit>0 五.易错点(推荐阅读) 1.分割到第一个字符 2.转义字符\ 3.正则表达式修饰符不可用 总结 前言 本章对Java如何实现字符串的分割,是基于jDK1.8版本中的String.split()方法

  • 基于php实现随机合并数组并排序(原排序)

    最近做了一个项目,其中有这样一个需求要实现,原有帖子列表A,现在需要在A中推广新业务B,那么需要在A列表中1:1混合B中的数据,随机混合,但是需要保持A和B两列原来的数据排序,具体详情请看下文. 原理 获知总共元素数量N: for循环N次,取随机数: 根据随机数依次从头获取A或B的值,推入新数组中: 代码: //随机合并两个数组元素,保持原有数据的排序不变(即各个数组的元素在合并后的数组中排序与自身原来一致) function shuffleMergeArray() { $mergeArray

  • Java实现几种常见排序算法代码

    稳定度(稳定性)一个排序算法是稳定的,就是当有两个相等记录的关键字R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前. 排序算法分类 常见的有插入(插入排序/希尔排序).交换(冒泡排序/快速排序).选择(选择排序).合并(归并排序)等. 一.插入排序 插入排序(Insertion Sort),它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),

  • Java 生成随机字符串数组的实例详解

    Java 生成随机字符串数组的实例详解 利用Collections.sort()方法对泛型为String的List 进行排序.具体要求: 1.创建完List<String>之后,往其中添加十条随机字符串 2.每条字符串的长度为10以内的随机整数 3.每条字符串的每个字符都为随机生成的字符,字符可以重叠 4.每条随机字符串不可重复 将涉及到的知识有: String.StringBuffer.ListArray.泛型.Collections.sort.foreach.Random等相关知识,算是

  • java对象转成byte数组的3种方法

    java对象转成byte数组,在使用netty进行通信协议传输的场景中是非常常见的.比如,协议有一些定好的协议头.classid,messageid等等信息,还有一个关键的内容是payload.不同的协议内容都会放到payload中,而这个payload往往就是一个byte数组. 那么,如何方便的将一个java对象构造成一个byte数组呢? 1 bytebuf填充 我们以下面这个对象举例: public class UgvData implements Serializible{ private

随机推荐