1樓：匿名使用者
每趟排序需要一個輔助空間，輔助空間和趟數有關，最好情況是log2 n ，最差的情況是n。
快速排序由c. a. r. hoare在2023年提出。
它的基本思想是：通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分別進行快速排序，整個排序過程可以遞迴進行，以此達到整個資料變成有序序列。
擴充套件資料
一趟快速排序的演算法是：
1、設定兩個變數i、j，排序開始的時候：i=0，j=n-1；
2、以第一個陣列元素作為關鍵資料，賦值給key，即key=a[0]；
3、從j開始向前搜尋，即由後開始向前搜尋(j--)，找到第一個小於key的值a[j]，將a[j]和a[i]的值交換；
4、從i開始向後搜尋，即由前開始向後搜尋(i++)，找到第一個大於key的a[i]，將a[i]和a[j]的值交換；
5、重複第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中a[j]不小於key,4中a[i]不大於key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。
找到符合條件的值，進行交換的時候i， j指標位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令迴圈結束）。
2樓：小修
快速排序對待排序序列的劃分大約為log2n次，而快速排序是通過遞迴演算法來完成的，遞迴深度大約為log2n，因此所需的輔助儲存空間為o(log2n)。
3樓：love焦小米
每趟排序需要一個輔助空間，輔助空間和趟數有關，最好log2 n ，最差n
4樓：cindy錦時
o(log2n)2是底數
對n個記錄的檔案進行快速排序，所需要的輔助儲存空間大致為？求解釋
5樓：
前面幾個答案都是答非所問。！！
快速排序的思想是不斷對待排序的元素按指定的元素進行劃分，然後對兩部分再進行劃分……。在劃分過程中，用到遞迴演算法，其遞迴演算法平均深度為約為 log2n，所以其空間複雜度為o(log2n)。
6樓：匿名使用者
快速排序在系統內部需要一個棧來實現遞迴。若每次劃分比較均勻，則其遞迴樹的高度為o(logn)。最壞情況下，遞迴樹的高度為o(n)，所需的棧空間為o(n)。
——資料結構（用c++語言描述）
北京郵電大學出版社
7樓：匿名使用者
堆排序：是一種樹型選擇排序，特點是，在排序過程中，把r[1..n]看成是一個完全二叉樹的儲存結構，利用完全二叉樹雙親結點和孩子結點的內在關係，在當前無序區中選擇關鍵字最大（最小）的記錄。
（2）堆排序步驟：
1、從k-1層的最右非葉結點開始，使關鍵字值大（或小）的記錄逐步向二叉樹的上層移動，最大（或小）關鍵字記錄成為樹的根結點，使其成為堆。
2、逐步輸出根結點，令r[1]=r[i](i=n,,n-1,...,2)，在將剩餘結點調整成堆。直到輸出所有結點。我們稱這個自堆頂到葉子的調整過程為「篩選」。
（3）要解決的兩個問題：
1、如何由一個無序序列建成一個堆；
2、輸出一個根結點後，如何將剩餘元素調整成一個堆。
將一個無序序列建成一個堆是一個反覆「篩選」的過程。若將此序列看成是一個完全二叉樹，則最後一個非終端結點是第floor(n/2)個元素，由此「篩選」只需從第floor(n/2)個元素開始。
堆排序中需一個記錄大小的輔助空間，每個待排的記錄僅佔有一個儲存空間。堆排序方法當記錄較少時，不值得提倡。當n很大時，效率高。堆排序是非穩定的。
堆排序的演算法和篩選的演算法如第二節所示。為使排序結果是非遞減有序排列，我們在排序演算法中先建一個「大頂堆」，即先選得一個關鍵字為最大的記錄並與序列中最後一個記錄交換，然後對序列中前n-1個記錄進行篩選，重新將它調整為一個「大頂堆」，然後將選得的一個關鍵字為最大的記錄（也就是第一個元素）與當前最後一個記錄交換（全域性看是第n-1個），如此往復，直到排序結束。由到，篩選應按關鍵字較大的孩子結點向下進行。
資料結構問題！求個詳細點的答案。。。萬分感激。。。
8樓：匿名使用者
第九題應該是這樣的，雜湊地址為1的元素是55,64,46,10這四個
所以答案應選d
9樓：匿名使用者
每趟排序需要一個輔助空間，輔助空間和趟數有關，最好log2 n ，最差n
10樓：李本質
d 55 64 46 10
資料結構筆試題
11樓：baishier白拾貳
a=22,3,30,4,60,11,58,18,40,16;low=0;high=9;
a=11,3,16,4,18,22,58,60,40,30;low=0;high=4;
a=4,3,11,16,18,22,58,60,40,30;low=3;high=4;
a=4,3,11,16,18,22,58,60,40,30;low=4;high=4;
a=3,4,11,16,18,22,58,60,40,30;low=0;high=0;
a=3,4,11,16,18,22,40,30,58,60;low=6;high=7;
a=3,4,11,16,18,22,30,40,58,60;low=6;high=6;
fails
對於輸入為n個數進行快速排序演算法的平均時間複雜度是多少?
12樓：cfv呆呆獸
根據t(n) = t(ðn) + o(n) (0 < ð <1) 則有 t(n) = o(n)
因此關鍵問題
是怎樣解決劃分標準的問題, 因此產生下列線性時間找中位數的演算法:
將陣列a有n個元素, 劃分成5個一組, 則共有[n/5]個元素, 對於每組用一般的排序找中位數,需要25次, 則總共需要o(25*[n/5]) = o(n), 然後在這些中位數中遞迴找其中位數需要t(n/5)次,然後以找到的中位數x來作為劃分標準則顯然劃分時間為o(n), 再遞迴的劃分, 顯然最多有3n/4的元素小於或大於x, 則選擇中位數的總複雜度為:
t(n) = o(n) + t(n/5) + t(3n/4) 有t(n) = o(n)。
因此快速排序的複雜度為t(n) = 2t(n/2) + o(n) 有:t(n) = nlogn。
但最壞情況下複雜度為o(n^2)，出現此條件的情況是n個數原來就已經按照規定要求排好序了。
對多個資料夾裡的檔案進行重新命名
不清楚你的實際檔案 情況，僅以問題中的樣例 說明為據 以下 複製貼上到記事本，另存為xx.bat，編碼選ansi，跟要處理的多個資料夾放一起執行 echo off rem 將多個資料夾裡的檔案以遞增的數字序號重新命名 title z cd d dp0 for d a in do set n 0 pu...
如何快速對比兩個資料夾裡的檔案的不同
堅果雲 堅果雲網盤支援office文件的歷史版本比較功能，通過堅果雲的電腦客戶端可以對檔案的歷史版本進行比較，不同版本中的不同內容會以修訂方式標出。圖中的a b c d分別是修改記錄，修改檢視，原文件，當前文件。您可以在修改記錄裡檢視詳細的修改記錄，哪怕僅僅只有一個字的修改也逃不過你的眼睛，而在修改...
如何對ai格式檔案中的文字進行修改
對準文字部位直接雙擊，游標進入文字中就可以和在word裡面一樣的修改。或者單擊左鍵選擇，然後快捷鍵 ctrl t 進行字型屬性各方面修改 要用adobe illustrator 看文字是否已經被弄了輪廓 如果沒有直接用文字工具就可以修改 如果有輪廓了 要直接刪掉重新寫 位興賢 直接在裡面調選文字工具...