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

算法#12--詳解各種字符串排序算法和代碼實現(xiàn)

來源：程序員人生發(fā)布時間：2016-09-28 10:15:32 閱讀次數(shù)：2434次

1.算法匯總

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

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

2.低位優(yōu)先的字符串排序

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

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

實現(xiàn)代碼：


//低位優(yōu)先的字符串排序
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--)
        {//根據(jù)第d個字符用鍵索引計算法排序
            int[] count = new int[R+1]; //計算出現(xiàn)的頻率
            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.高位優(yōu)先的字符串排序

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

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

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

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

實現(xiàn)代碼：


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

    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++) //數(shù)據(jù)分類
        {
            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]);
        } 
     }

}

運行軌跡：

這里用到了小型子數(shù)組。當要排序的數(shù)量，低于閾值，我們就將快速排序轉換為插入排序。對高位優(yōu)先的字符串排序算法它節(jié)儉的時間是非?？捎^的。

4.3向字符串快速排序

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

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

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

實現(xiàn)代碼：


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