算法描述

  • 普通MSD算法每层递归会创建count[R+2],其中大部分都是空数组.而三项切分字符串快排,根据键的首字母v,切分成首字符小于v,等于v,大于v三部分,仅在首字符等于v的子数组中对下一个字符再次三向切分,其余两部分继续对首字符三向切分

实现

  1. public class Quick3string {
  2.     private static int charAt(String s, int d){
  3.         if (d < s.length()) return s.charAt(d);
  4.         else return -1;
  5.     }
  7.     public static void sort(String[] a){
  8.         sort(a, 0, a.length-1, 0);
  9.     }
  10.     private static void exch(String[] a, int v, int w){
  11.         String temp = a[v];
  12.         a[v] = a[w];
  13.         a[w] = temp;
  14.     }
  15.     private static void sort(String[] a, int lo, int hi, int d){
  16.         if (lo >= hi) return;
  17.         int lt = lo, gt = hi;
  18.         int v = charAt(a[lo], d);//枢轴
  19.         int i = lo + 1;
  20.         while (i <= gt){
  21.             int t = charAt(a[i], d);
  22.             if (t > v) exch(a, lt++, i++);
  23.             else if (t < v) exch(a, i, gt--);
  24.             else i++;
  25.         }
  26.         sort(a, lo, lt-1, d);
  27.         if (v > 0) sort(a, lt, gt, d+1);//空子数组,不进行递归
  28.         sort(a, gt+1, hi, d);
  29.     }
  30. }

示例

Quick3string.png
the.png

算法分析

  • 当字符串很长但长度相同,且前面大部分字符相同时
    • 标准快排:~w2NlnN
    • 三向切分: wN+2NlnN

证明:三向切分中发现相同开头字母需要花wN,而对剩下部分的比较需2NlnN次比较

stringSort.png