在快速排序中修改比較器

整數數組上的快速排序通過對整個數組的半部分進行遞歸分區來工作 - 並且這樣做對數組進行排序。我知道分區需要O（n），並且因爲它在每個半（logN次）遞歸執行，所以總成本出現在O（NlogN）上。在快速排序中修改比較器

在解碼編碼採訪第6版中，問題10.2要求編寫一個方法來對字符串數組進行排序，以使所有字符串相鄰。作者提出了兩種不同的解決方案 - 其中一種解決方案是快速排列整個陣列，因此字符串最終會彼此相鄰。

但她說這是時間O（NlogN）。這是我迷失的地方。對於整數數組，快速排序必須訪問每個元素和交換整數，具體取決於一個是否大於另一個。這是每N個元素的O（1）成本，總計爲O（N）。然而，作者建議的兩個字符串的比較將兩個字符串分解爲一個char數組，並對它們進行排序，然後對它們進行比較。這個過程是每個字符串O（L logL）（其中L是字符串的長度）..所以它是每N個字符串的O（LlogL）成本 - 不是O（NlogN（L LogL））？可能會迷失在數字中，但如果有人能夠向我解釋作者的過程如何在字符串比較中具有O（NlogN）複雜性，那將會非常有幫助。下面是她的代碼：

class AnagramComparator implements Comparator <String> { 
    public String sortChars(String s) { 
    char[] content = s.toCharArray(); 
    Arrays.sort(content) 
    return new String(content); 
    } 
    public int compare(String s1, String s2) { 
    return sortChars(s1).compareTo(sortChars(s2)); 
    } 
}

來源

2017-01-02 Sunny

這裏有兩個_different_'N'在這裏混淆：字符串的長度和字符串的數量。 –

只是爲了糾正錯誤表達：Quicksort不一定將數組分成兩半。它將數組分成兩部分，但在最壞的情況下，第一部分（或第二部分）可能只包含一個元素。在最壞的情況下，每當算法遞歸時都會發生這種情況，這就是爲什麼Quicksort的最壞情況時間是O（n^2）而不是O（n log n）。雖然_average_時間是O（n log n）。 – ajb

@LouisWasserman你是完全正確的 - 添加相應的編輯。 – Sunny

作者可以假定字符串的最大長度是一些恆定，從而比較字符串仍然O（1）。

來源

2017-01-02 00:15:58

根據您編輯的問題，您是對的 - 每次比較都需要O（L log L）時間，其中L是最大字符串長度。根據最大字符串長度的大小，這可以將排序時間乘以相當重要的因素。由於對每個字符串中的字符進行排序將多次完成，這似乎是處理它的低效方式。

一個更好的辦法可能是定義一個新的對象：

public class AnagramSortElement implements Comparable<AnagramSortElement> { 
    private String sourceString; 
    private String sortedChars; 
    // getters, constructors as needed 
    // compareTo that compares sortedChars 
}

，所以你只爲每個輸入串計算sortedChars一次。你首先從原始的String[]創建一個新的AnagramSortElement[]數組，然後使用該數組進行排序。這個過程將採用O（N *（L log L））而不是O（（N log N）*（L log L））。然後，當你進行排序時，比較會更快，因爲你已經對字符排序了;這種排序平均需要O（N log N）。

看起來這應該是更快，但你必須對其進行配置以確保。對於非常大的N來說，創建N個新對象會對內存資源造成壓力，對於較小的L，原始代碼可能會更快。

來源

2017-01-02 00:31:32 ajb

在快速排序中修改比較器

回答

相關問題