樹形選擇排序-資料下載頁
2025-08-05 08:24本頁面
【正文】 tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] tree[15] ? 樹形選擇排序構成的勝方樹是滿二叉樹 , 其深度為 ?log2n? , 其中 n 為待排序元素個數(shù)。 ? 除 第一次選擇具有最小排序碼的對象 需要進行 n1 次 排序碼比較 外 , 重構勝方樹選擇具有次小、再次小排序碼對象所需的 排序碼比較次數(shù) 為 O(log2n)。 總排序碼比較次數(shù) 為 O(nlog2n)。 ? 對象的移動次數(shù)不超過排序碼的比較次數(shù) ，所以樹形選擇排序總時間復雜度為O(nlog2n)。 ? 這種排序方法減少了許多排序時間 , 但是使用了較多的附加存儲。 ? 如果有 n 個對象，必須使用至少 2n1 個結點來存放勝方樹。最多需要找到滿足 2k1 n ? 2k 的 k，使用 2*2k1 個結點。每個結點包括排序碼 、 結點序號 和 比較標志 三種信息。所以，其需要的輔助存儲空間較多 ? 樹形選擇排序是一個 穩(wěn)定 的排序方法 。
環(huán)評公示相關推薦
鄂ICP備17016276號-1