1樓：靖芷啦
快速排序是二叉查詢樹（二叉查詢樹）的乙個空間最優化版本。不是循序地把資料項插入到乙個明確的樹中，而是由快速排序組織這些資料項到乙個由遞迴呼叫所隱含的樹中。這兩個演算法完全地產生相同的比較次數，但是順序不同。
對於排序演算法的穩定性指標，原地分割槽版本的快速排序演算法是不穩定的。其他變種是可以通過犧牲效能和空間來維護穩定性的。
快速排序的最直接競爭者是堆排序（heapsort）。堆排序通常比快速排序稍微慢，但是最壞情況的執行時間總是o(n log n)。快速排序是經常比較快，除了introsort變化版本外，仍胡純然有最壞情況效能的機會。
如果事先知道堆排序將會是需要使用的，那麼直接地使用堆排序比等待introsort再切換到它還要快。堆排序也擁有重要的特點，僅使用固定額外的空間（堆排序是原地排序），而即使是最佳的快速排序變化版本也需要θ(log n)的空間。然而，堆排序需要有效率的隨機存取才能變成可行。
快速排序也與歸併排序（mergesort）競爭，這是另外一種遞迴排序演算法，但有壞情況o(n log n)執行時間的優勢。不像快速排序或堆排序，歸併排序是乙個穩定排序，且可以輕易地被採用在連結串列（linkedlist）和儲存在慢速訪問**上像是磁碟儲存或網路連線儲存的非常巨大數列。儘管快速排序可以被重新改寫使用在煉串列褲孝咐上，但是它通常會因為無法隨機存取而導致差的基準選擇。
歸併排序的主要缺點，是在最慎缺佳情況下需要ω(n)額外的空間。
快速排序和堆排序不穩定，歸併排序穩定。<>
2樓：網友
非原地版本的快速肆亮排序，在它的任何遞迴呼叫前需要使用o(n)空間。在最好的情況下，它的空間仍然限制在o(n)，因為遞迴的每一階中，使用裂穗寬與上一次所使用最多空間的一半，且平均為o(2n)。
它的最壞情況是很恐怖的，需要o(n2)空間，遠族鎮比數列本身還多。如果這些數列元素本身自己不是固定的大小，這個問題會變得更大；舉例來說，如果數列元素的大部分都是不同的，每乙個將會需要大約o(log n)為原來儲存，導致最好情況是o(n log n)和最壞情況是o(n2 log n)的空間需求。<>
3樓：峰佘無敵
被快速排序所使用的空間，依照使用的版本而定。使用原地（in-place）分割槽的快速排序版本，在任何遞迴呼叫前，僅會使用固定的額外空間。然而，如果需要產生o(log n)巢狀遞迴呼叫，它需要在他們每乙個存鬧辯儲乙個固定數量的資訊。
因為最好的情況最多需要o(log n)次的巢狀遞迴呼叫，所以它需要o(log n)的空間。最壞情況下需要o(n)次巢狀液沒缺遞迴呼叫，因此需要o(n)的空間。
然而我們在這裡省略一些小的細節。如果我們考慮排序任意很長的數列，我們必須要記住我們的變數像是left和right，不再被認為是佔據固定的空間；也需要o(log n)對原來乙個n項的數列作索引。因為我們察碰在每乙個堆疊框架中都有像這些的變數，實際上快速排序在最好跟平均的情況下，需要o(log2 n)空間的位元數，以及最壞情況下o(n log n)的空間。
然而，這並不會太可怕，因為如果乙個數列大部分都是不同的元素，那麼數列本身也會佔據o(n log n)的空間位元組。<>
快速排序方法在任何情況下均可以得到最快的排序效率，對嗎？
4樓：當代汽車科技知識庫
要排序的資料已基本有序的情況下。
快速排序的基本思想是以基準元素為中心，將待排序表分成兩個子表，然後繼續對子表進行劃分，直到所有子表的長度為1。
快速排序第一趟的結果是：將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小。
5樓：網工小菜鳥
肯定不對啊···例如對於乙個本來就有序的陣列，每次取的主軸元素都是最大或最小的，就和氣泡排序一樣的複雜度了。
什麼是堆排序， 為什麼要有堆排序， 在什麼地方用堆排序， 怎麼使用堆排序
6樓：
摘要。概念】堆排序(heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序演算法，它是選擇排序的一種。可以利用陣列的特點快速定位指定索引的元素。
堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值，即a[parent[i]]>a[i]。在陣列的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
起源】1991年的計算機先驅獎獲得者、史丹福大學電腦科學系教授羅伯特·弗洛伊德(robertw．floyd）和威廉士(j．williams）在1964年共同發明了著名的堆排序演算法（heapsort)。【簡介】堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最小）這一特徵，使得在當前無序區中選取最大（或最小）關鍵字的記錄變得簡單。
怎麼使用堆排序。
什麼是堆排序，為什麼要有堆排序，在什麼地方用堆排序，什麼是堆排序，怎麼使用堆排序。
在什麼地方用堆排序，為什麼要有堆排序，什麼是堆排序，怎麼使用堆排序。
在什麼地方用堆排序，為什麼要有堆排序，什麼是堆排序，
在快速排序、堆排序、歸併排序中，什麼排序是穩定的？
7樓：網友
歸併排序是穩定的排序演算法。
歸併排序的穩定性分析：
歸併排序是把序列遞迴地分成短序列，遞迴出口是短序列只有1個元素或者2個序列，然後把各個有序的段序列合併成乙個有序的長序列，不斷合併直到原序列全部排好序。
可以發現，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等，沒有外部干擾，將不會破壞穩定性。
那麼，在短的有序序列合併的過程中，穩定性是沒有受到破壞的，合併過程中如果兩個當前元素相等時，把處在前面的序列的元素儲存在結果序列的前面，這樣就保證了穩定性。所以，歸併排序也是穩定的排序演算法。
8樓：網友
歸併排序是穩定的。
快速排序和堆排序都不穩定。
不穩定：就是大小相同的兩個數，經過排序後，最終位置與初始位置交換了。快速排序：
以第乙個27作為pivot中心點，則27與後面那個3交換，形成3 23 27 27，排序經過一次結束，但最後那個27在排序之初先於初始位置3那個27，所以不穩定。
堆排序：比如：3 27 36 27，如果堆頂3先輸出，則，第三層的27（最後乙個27）跑到堆頂，然後堆穩定，繼續輸出堆頂，是剛才那個27，這樣說明後面的27先於第二個位置的27輸出，不穩定。」
2 歸併排序（mergesort）
歸併排序先分解要排序的序列，從1分成2，2分成4，依次分解，當分解到只有1個一組的時候，就可以排序這些分組，然後依次合併回原來的序列中，這樣就可以排序所有資料。合併排序比堆排序稍微快一點，但是需要比堆排序多一倍的記憶體空間，因為它需要乙個額外的陣列。」
參考資料。
9樓：卟懂
在常見排序中，只有希爾排序、堆排序、快速排序是不穩定的。
10樓：網友
歸併排序(n log n);穩定。
堆排序 (n log n);不穩定。
快排（n log n）不穩定。
11樓：傅邃出好
是歸併排序，我剛剛也做這個題目。
因為堆排序時間複雜度為n*logn，空間複雜度為1，是不穩定排序，適合較多情況；
而歸併排序的時間複雜度為n*logn，空間複雜度為n，是穩定排序。
快速排序的時間複雜度為n，空間複雜度最好的情況是logn，最壞的情況是n^2，是不穩定的排序方法。（書本原話）。
什麼是堆排序？
12樓：匿名使用者
堆積排序(heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序演算法，可以利用陣列的特點快速定位指定索引的元素。
演算法思想：1）堆的定義：
堆是滿足下列性質的數列：
若將此數列看成是一棵完全二叉樹，則堆或是空樹或是滿足下列特性的完全二叉樹：其左、右子樹分別是堆，並且當左/右子樹不空時，根結點的值小於(或大於)左/右子樹根結點的值。由此，若上述數列是堆，則 r1 必是數列中的最小值或最大值，分別稱作小頂堆或大頂堆。
堆排序：即是利用堆的特性對記錄序列進行排序的一種排序方法。
2）堆排序思想：
先建乙個「大頂堆」，即先選得乙個關鍵字為最大的記錄，然後與序列中最後乙個記錄 交換，之後繼續對序列中前 n-1 記錄進行「篩選」，重新將它調整為乙個「大頂堆」再 將堆頂記錄和第 n-1 個記錄交換，如此反覆直至排序結束。所謂「篩選」指的是對一棵 左/右子樹均為堆的完全二叉樹，「調整」根結點使整個二叉樹為堆。 ■堆排序的特點：
在以後各趟的「選擇」中，利用在第一趟選擇中已經得到的關鍵字比 較的結果。
在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸併排序中，平均比較次數最少的排序是___。
13樓：
摘要。您好。
在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸併排序中，平均比較次數最少的排序是快速排序。
在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸併排序中，平均比較次數最少的排序是___
您好在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸併排序中，平均比較次數最少的排序是快速排序。
基數排序和快排那個比較少。
快排的哈。基數排序不是不比較嗎 不就是0次嗎。
不是的，基數排序不基於比較，不能算在裡面的，題目裡問的是那個比較次數最少。
選擇排序和堆排序
14樓：天羅網
最近瞭解到了hadoop中的merge過程，其中使用到了外部排序。
因此總結一下選擇排序和堆排序：
選擇排序：選擇排序的時間複雜度為o(n^2);不需要額外的儲存空間。也就是簡單選擇排序。
就是每次選出來乙個最小值，和第乙個元素交換；第二輪再選未排序佇列中的最小值。。。
樹形選擇排序的優點是，相較於簡單選擇排序，是和中間結果比較，減少了比較的次數。樹形選擇排序只有葉子節點是待排序列，中間結點是排序的中間結果。
外部排序中：多路歸併排序+敗者樹（用到了記憶體中的歸併排序（分治法，divide and conquer）+外部的多路歸併排序，多路歸併的限制因素是外部磁碟的訪問次數，雖然多路減少了磁碟的讀寫次數，但是多路的極值比較增多，抵消掉多路歸併中磁碟讀寫帶來的效能提公升，因此採用敗者樹）
敗者樹：是一種完全二叉樹，是樹形選擇排序的變種。只有葉子節點是待排序的。中間節點是排序的中間結果。
選擇排序（o（n^2））-樹形選擇排序(額外的儲存空間較大)--堆排序。
堆排序：所有的節點都是待比較的資料
大頂堆和小頂堆：
每個節點都大於或者等於左右孩子結點的值，稱為大頂堆；
每個節點都小於或者等於左右孩子節點的值，成為小頂堆；
並且，堆是完全二叉樹，因此可以用陣列來進行儲存。
以前學這些，因為沒有具體的應用場景，不是很理解，每次看完就忘。
氣泡排序在最壞的情況下的比較次數為什麼是n n
氣泡排序如1，2,3,4最好的情況是按完全升級排列，最壞就是數字完全按降序排列 第一次是1 然後1和2,3,4 第2次是2 比較誰比它小交換，於是2和34交換，答案是3421 第3次為3 3和4 最後是4321 這就是最壞情況下的次數3 2 1 6 4 3 2 其實對於n個的話，你要求降低排列，但是...
在最壞情況下，氣泡排序的時間複雜度為
n n 1 2 n n 1 2 o n n 1 2 o n n 1 2 在最壞的情況下氣泡排序的時間複雜度是什麼 氣泡排序的演算法時間複雜度上 最壞情況下 是 o n 2 氣泡排序是這樣實現的 首先將所有待排序的數字放入工作列表中。從列表的第一個數字到倒數第二個數字，逐個檢查 若某一位上的數字大於他...
在什么情況下維護自尊，在什麼情況下維護自尊
讓你不開心，或者沒有讓你不開心，只要他說了對你不好的話，就要立即做出反應。底線很低只會縱容別人，別人一旦嚐到甜頭，就會習慣於從你身上獲取利益，你那個時候也會覺得讓他何妨，心態已經變了。但是這樣對嗎，這樣好嗎。除非特殊情況。無論是底線後退還是底線很低，實際上都是沒有底線。只有有能力維護好自己底線，才能...