這種排序算法的複雜性是什麼？使用相同的缺點是什麼？

1.從陣列數據創建二進制搜索樹。

（對於多次出現，遞增當前節點的occurence變量）

2.導線BST在序方式。

（按順序遍歷將返回數組中元素的排序順序）。

3.在按順序遍歷的每個節點上，用當前節點值覆蓋當前索引（索引從0開始）處的數組元素。

下面是相同的Java實現：

節點類的結構

class Node { 
    Node left; 
    int data; 
    int occurence; 
    Node right; 
}

序功能 （返回類型爲int只是在每次調用獲取正確的指標，他們服務沒有其他目的）

public int inorder(Node root,int[] arr,int index) { 
    if(root == null) return index; 
    index = inorder(root.left,arr,index); 
    for(int i = 0; i < root.getOccurence(); i++) 
     arr[index++] = root.getData(); 
    index = inorder(root.right,arr,index); 
    return index; 
}

的main（）

public static void main(String[] args) { 
    int[] arr = new int[]{100,100,1,1,1,7,98,47,13,56}; 
    BinarySearchTree bst = new BinarySearchTree(new Node(arr[0])); 
    for(int i = 1; i < arr.length; i++) 
     bst.insert(bst.getRoot(),arr[i]); 
    int dummy = bst.inorder(bst.getRoot(),arr,0); 
    System.out.println(Arrays.toString(arr)); 
}

的空間複雜度是可怕的，我知道，但除非排序是用於一個非常龐大的數據集它不應該是一個大問題。但是，正如我所看到的，不是時間複雜性O（n）？（從BST插入和檢索是O（log n），並且每個元素被觸摸一次，使其成爲O（n））。如果我錯了，請糾正我，因爲我還沒有很好地學習過Big-O。

來源

2017-07-25 saketk21

如果你的目標是排序爲O陣列（N *日誌（N））的時候，你已經可以使用快速排序或歸併具有更好的空間使用情況，你從陣圖 - >陣列，而不是陣列 - >樹。 –

@DougCoburn實際上，我們的目標是實現一個O（n）算法，用n [1，n^2]範圍內的每個元素對n個元素進行排序。 – saketk21

我很確定沒有O（n）排序算法。在這些限制下。 –

假設攤銷的插入的（平均）複雜性是O(log n)，然後N插入物（樹結構）將給出O(log(1) + log(2) + ... + log(N-1) + log(N) = O(log(N!)) = O(NlogN)（斯特林定理）。要回讀排序後的數組，請執行按順序深度優先遍歷，它訪問每個節點一次，因此爲O(N)。結合你得到O(NlogN)。

但是這需要樹總是平衡！對於最基本的二叉樹，通常情況並非如此，因爲插入操作不檢查每個子樹的相對深度。有很多變體是自平衡 - 這兩個最有名的是紅黑樹和AVL樹。然而，平衡的實現相當複雜，並且常常導致實際性能中的更高恆定因素。

來源

2017-07-25 15:51:47 meowgoesthedog

很好的解釋！感謝您的快速回復。我如何接受這個答案作爲解決問題的方法？ – saketk21

@SaketKulkarni點擊下面的投票按鈕，並複製代碼 – meowgoesthedog

Got it！ +1進行簡要說明。 – saketk21

目標是實現一個O（n）的算法進行排序n個元素與在範圍內的每個元素的數組[1，N^2]

在這種情況下基數排序（計數變量）將是O（n），採取固定數量的通過（logb（n^2）），其中b是用於該字段的「基數」，以及ba的n函數，例如b == n，其中它需要兩遍，或者b == sqrt（n），它需要四遍，或者如果n足夠小，b == n^2在哪裏需要一次傳遞並且可以使用計數排序。 b可以四捨五入到2的下一個冪，以便用二進制移位和二進制移位來取代除法和模數。基數排序需要O（n）額外的空間，但二叉樹的鏈接也是如此。

來源

2017-07-26 04:23:40 rcgldr

+1好的解決方案。我仍然無法圍繞如何將它作爲O（n）算法。將研究它。 – saketk21

有趣的解決方案。如果值限制爲[1，n^2]，則可以在兩個（常量）遍中對n個桶執行基數排序，從而形成最終解決方案O（n）。聽起來像是面試或家庭作業問題。 –

@SaketKulkarni - 我更新了我的答案，注意到Doug Coburn評論說b是n的函數，如b == n（兩遍）或b = sqrt（n）（四遍）。 – rcgldr

這種排序算法的複雜性是什麼？使用相同的缺點是什麼？

回答

相關問題