您當前位置：首頁 > php開源 > php教程 > 算法#12--詳解各種字符串排序算法和代碼實現

算法#12--詳解各種字符串排序算法和代碼實現

來源：程序員人生發布時間：2016-09-28 10:15:32 閱讀次數：2425次

1.算法匯總

首先，來看1張各種字符串排序算法的匯總。前面的文章已介紹過插入排序、快速排序、歸并排序和3向快速排序。這里不再介紹。

我們將重點詳解：低位優先的字符串排序、高位優先的字符串排序和3向字符串快速排序。

2.低位優先的字符串排序

這類方法會從右向左檢查鍵中的字符。如果將1個字符串看做1個256進制的數字，那末從右向左檢查字符串就等價于先檢查數字的最低位。

這類方法最合適用于鍵的長度都相同的字符串排序援用。

實現代碼：


//低位優先的字符串排序
public class LSD 
{
    public static void sort(String[] a, int W)
    {//通過前W個字符將a[]排序
        int N = a.length;
        int R = 256;
        String[] aux = new String[N];

        for(int d = W - 1; d >= 0; d--)
        {//根據第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];
            }
        }
    }

    public static void main(String[] args) 
     {
        String[] a= {"4PGC938", "2IYE230", "3CI0720", "1ICK750", "1OHV845", "4JZY524", "1ICK750",
                "3CI0720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"};

        LSD.sort(a, 7);
        for(int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        } 
     }
}

運行軌跡：

3.高位優先的字符串排序

這類方法會從左到右檢查鍵中的字符，首先查看的是最高位的字符。高位優先的字符串排序的吸引人的地方在于，它們不1定需要檢查所有的輸入就可以夠完成排序。

高位優先的字符串排序和快速排序類似，由于它們都會將需要排序的數組切分為獨立的部份并遞歸地用相同的方法處理子數組來完成排序。

它們的區分的地方在于高位優先的字符串排序算法在切分時僅使用鍵的第1個字符，而快速排序的比較則會觸及鍵的全部。

接下來要學習的方法會將相同字符的鍵劃入同1個切分。

實現代碼：


//高位優先的字符串排序
public class MSD {
    private static int R = 256;     //基數
    private static final int M = 3;//小數組的切換閾值
    private static String[] aux;    //數據分類的輔助數組

    private static int charAt(String s, int d)
    {
        if(d < s.length())
        {
            return s.charAt(d);
        }
        else
        {
            return -1;
        }
    }

    public static void sort(String[] a)
    {
        int N = a.length;
        aux = new String[N];
        sort(a, 0, N-1, 0);
    }

    private static void sort(String[] a, int lo, int hi, int d)
    {//以第d個字符為鍵將a[lo]至a[hi]排序
        if(hi <= lo + M)
        {//快速排序
            InsertionSort(a, lo, hi, d);
            return;
        }

        int[] count = new int[R+2]; //計算頻率
        for(int i = lo; i <= hi; i++)
        {
            count[charAt(a[i], d) + 2]++;
        }

        for(int r = 0; r < R+1; r++) //將頻率轉換為索引
        {
            count[r+1] +=count[r];
        }

        for(int i = lo; i <= hi; i++) //數據分類
        {
            aux[count[charAt(a[i], d) + 1]++] = a[i];
        }

        for(int i = lo; i <= hi; i++) //回寫
        {
            a[i] = aux[i-lo];
        }

        //遞歸的以每一個字符為鍵進行排序
        for(int r = 0; r < R; r++)
        {
            sort(a, lo + count[r], lo + count[r+1] - 1, d+1);
        }
    }

    //快速排序
    private static void InsertionSort(String[] a, int lo, int hi, int d) 
    {   
        for( int i = lo; i < hi; i++) 
        { 
            for( int j=i+1; j>lo; j--) 
            {               
                if( a[j-1].compareTo(a[j]) <= 0)
                {
                    break;
                }
                String temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;              
            }
        }  
    }

    public static void main(String[] args) 
     {
        String[] a= {"she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she",
            "sells", "are", "surely", "seashells"};

        MSD.sort(a);
        for(int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        } 
     }

}

運行軌跡：

這里用到了小型子數組。當要排序的數量，低于閾值，我們就將快速排序轉換為插入排序。對高位優先的字符串排序算法它節儉的時間是非常可觀的。

4.3向字符串快速排序

再要學習的方法會產生3個切分，分別對應被搜索的第1個字符小于、等于或大于切分鍵的第1個字符的情況。

高位優先的字符串排序可能會創建大量（空）子數組，而3向切分總是只有3個。因此3向字符串快速排序能夠很好處理等值鍵、有較長公共前綴的鍵、取值范圍較小的鍵和小數組–所有高位優先的字符串排序算法不善于的各種情況。

實際上，3向字符串快速排序是普通的快速排序和高位優先的字符串排序算法的結合。

實現代碼：


//3向字符串快速排序
public class Quick3string {
    public static void sort (String[] a)
    {
        sort(a, 0, a.length - 1, 0);
    }

    private static void sort(String[] a, int lo, int hi, int d)
    {
        if(hi <= lo)
        {
            return;
        }
        int lt = lo, gt = hi;
        int v = charAt(a[lo], d);
        int i = lo + 1;
        while(i <= gt)
        {
            int t = charAt(a[i], d);
            if(t < v)
            {
                swap(a, lt, i);
                lt++;
                i++;
            }
            else if(t > v) 
            {
                swap(a, gt, i);
                gt--;
            }
            else 
            {
                i++;
            }
        }
        sort(a, lo, lt - 1, d);     
        if(v >= 0)
        {
            sort(a, lt, gt, d + 1);
        }
        sort(a, gt + 1, hi, d);
    }

    private static int charAt(String s, int d)
    {
        if(d < s.length())
        {
            return s.charAt(d);
        }
        else
        {
            return -1;
        }
    }

    private static void swap(String[] a, int i, int j) 
    {
        String temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) 
    {   
        String[] a= {"she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she",
                "sells", "are", "surely", "seashells"};
        Quick3string.sort(a);
        for (int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        }
    }
}