java实现6种字符串数组的排序(Stringarraysort)-创新互联

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

方法分别是：

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

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。