1樓：
二分法插入排序 複雜度 o(nlogn)快速排序 o(nlogn) 有可能退化歸併排序 o(nlogn) 比較快堆排序 o(nlogn)最穩定的
二分法插入排序 快速排序 歸併排序 堆排序 的時間複雜度分別是多少？
2樓：carry_小小
二分法插入排序 複雜度 o(nlogn)
快速排序 o(nlogn) 有可能退化歸併排序 o(nlogn) 比較快
堆排序 o(nlogn)最穩定的
3樓：匿名使用者
排序演算法
所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。 分類 在電腦科學所使用的排序演算法通常被分類為： 計算的複雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。
一般而言，好的表現是o。(n log n)，且壞的行為是ω(n2)。對於一個排序理想的表現是o(n)。
僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要ω(n log n)。 記憶體使用量（以及其他電腦資源的使用）
穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄r和s，且在原本的串列中r出現在s之前，在排序過的串列中r也將會是在s之前。
一般的方法：插入、交換、選擇、合併等等。交換排序包含氣泡排序（bubble sort）和快速排序（quicksort）。
選擇排序包含shaker排序和堆排序（heapsort）。 當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。
(4, 1) (3, 1) (3, 7) (5, 6) 在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有： (3, 1) (3, 7) (4, 1) (5, 6) (維持次序) (3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。
然而，要記住這種次序通常牽涉到額外的空間負擔。 排列演算法列表 在這個**中，n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的氣泡排序（bubble sort） — o(n2)
雞尾酒排序 (cocktail sort, 雙向的氣泡排序) — o(n2)
插入排序 （insertion sort）— o(n2)
桶排序 （bucket sort）— o(n);
需要 o(k) 額外 記憶體
計數排序 (counting sort) — o(n+k); 需要 o(n+k) 額外 記憶體
歸併排序 （merge sort）— o(n log n); 需要 o(n) 額外記憶體
原地歸併排序 — o(n2) 二叉樹排序 （binary tree sort） — o(n log n); 需要 o(n) 額外記憶體
鴿巢排序 (pigeonhole sort) — o(n+k); 需要 o(k) 額外記憶體
基數排序 （radix sort）— o(n·k); 需要 o(n) 額外記憶體
gnome sort — o(n2) library sort — o(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定選擇排序 （selection sort）— o(n2)
希爾排序 （shell sort）— o(n log n)
如果使用最佳的現在版本 comb sort — o(n log n)
堆排序 （heapsort）— o(n log n) **oothsort — o(n log n)
快速排序 （quicksort）— o(n log n)
期望時間, o(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序 introsort — o(n log n) patience sorting — o(n log n + k) 最外情況時間, 需要 額外的 o(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence） 不實用的排序演算法 bogo排序 — o(n × n!) 期望時間, 無窮的最壞情況。 stupid sort — o(n3); 遞迴版本需要 o(n2) 額外記憶體 bead sort — o(n) or o(√n), 但需要特別的硬體 pancake sorting — o(n), 但需要特別的硬體 排序的演算法 排序的演算法有很多，對空間的要求及其時間效率也不盡相同。
下面列出了一些常見的排序演算法。這裡面插入排序和氣泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小範圍內的排序演算法。
插入排序 氣泡排序 選擇排序 快速排序 堆排序 歸併排序 基數排序 希爾排序 插入排序 插入排序是這樣實現的： 首先新建一個空列表，用於儲存已排序的有序數列（我們稱之為"有序列表"）。 從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。
重複2號步驟，直至原數列為空。 插入排序的平均時間複雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。
氣泡排序 氣泡排序是這樣實現的： 首先將所有待排序的數字放入工作列表中。 從列表的第一個數字到倒數第二個數字，逐個檢查：
若某一位上的數字大於他的下一位，則將它與它的下一位交換。 重複2號步驟，直至再也不能交換。 氣泡排序的平均時間複雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序 選擇排序是這樣實現的： 設陣列記憶體放了n個待排數字，陣列下標從1開始，到n結束。 i=1 從陣列的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。 如果i=n－1演算法結束，否則回到第3步 選擇排序的平均時間複雜度也是o(n²)的。 快速排序 現在開始，我們要接觸高效排序演算法了。
實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。
這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關係，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查詢資料得另當別論了。
堆排序 堆排序與前面的演算法都不同，它是這樣的： 首先新建一個空列表，作用與插入排序中的"有序列表"相同。 找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。
重複2號步驟，直至原數列為空。 堆排序的平均時間複雜度為nlogn,效率高（因為有堆這種資料結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要o(1)的時間複雜度，維護需要logn的時間複雜度），但是實現相對複雜（可以說是這裡7種演算法中比較難實現的）。 看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。
至少，他們的時間複雜度差了一個數量級，一個是平方級的，一個是對數級的。 平均時間複雜度 插入排序 o(n2) 氣泡排序 o(n2) 選擇排序 o(n2) 快速排序 o(n log n) 堆排序 o(n log n) 歸併排序 o(n log n) 基數排序 o(n) 希爾排序 o(n1.25)
4樓：匿名使用者
排序算琺 時間複雜度 優點 缺點
簡單排序 o(n^2) 編寫方便 執丨行時間長
快排 o(nlbn) 執丨行時間短 很差情況下執丨行時間長、佔用記憶體多
堆排序 o(nlbn) 執丨行時間短 編寫有點麻煩，有較差的情況
計數排序 o(n+m) 編寫方便，取值範圍小時很高效 取值範圍大時效率低、易超記憶體限丨制
歸併排序 o(nlbn) 穩定的排序算琺，無較差情況 佔用記憶體很大
5樓：上官影汐
二分法插入排序複雜度：o(n2)(n2指的是n的二次方）快速排序複雜度：o(nlgn)
歸併排序o(nlgn)
堆排序o（nlgn）
在快速排序、堆排序、歸併排序中，什麼排序是穩定的？
6樓：沉珂側畔
歸併排序是穩定的「快速排序和堆排序都不穩定.不穩定：就是大小相同的兩個數，經過排序後，最終位置與初始位置交換了。
快速排序：
27 23 27 3
以第一個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個一組的時候，就可以排序這些分組，然後依次合併回原來的序列中，這樣就可以排序所有資料。合併排序比堆排序稍微快一點，但是需要比堆排序多一倍的記憶體空間，因為它需要一個額外的陣列。」
以ai與aj為例子
快速排序有兩個方向，左邊的i下標一直往右走，當a[i] <= a[center_index]，其中center_index樞元素的陣列下標，一般取為陣列第0個元素。而右邊的j下標一直往左走，當a[j] > a[center_indexij都走不動了，i <= j, 交換a[i]和a[j],重複上面的過程，直到i>j。
交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩定性打亂，比如序列5 3 3 4 3 8 9 10 11，現在中樞元素5和3(第5個元素，下標從1開始計)交換就會把元素3的穩定性打亂，所以快速排序是一個不穩定的排序演算法，不穩定發生在中樞元素和a[j]交換的時刻。
c語言插入排序法，C語言插入排序法
插入排序 insertion sort 如果需要對一個小型陣列進行升序排列，那麼可以選用插入排序，插入排序可以用打牌時對摸起的牌根據牌的點數來對其進行插入排列來描述。可以把左手中的牌比做已經摸起的牌，即已經被排列好的牌，左手可以容納的牌數的空間可以假想為和要摸的牌的總數相同 而在桌子上的那部分沒摸的...
二分法查詢最壞情況下需要比較次數，為什麼n次和O（log
後者是演算法複雜度的意思 n次是正確的嗎？應該是log 2 n次才對啊 用二分法查詢最多log2 n 用順序查詢最多是n次 順序查詢需要比較n次，二分法查詢需要比較log n次 在最壞情況下，堆排需要進行比較的次數為nlog2n，為什麼是這樣啊，n是什麼含義，如果n為奇數不就 o n1og2n 在b...
二分法的時間複雜度為olog2n是什麼意思
網頁連結 你可以看看我的上面這個部落格 由於二分查詢每次查詢都是從陣列中間切開查詢，所以每次查詢，剩餘的查詢數為上一次的一半，從下表可以清晰的看出查詢次數與剩餘元素數量對應關係 表 查詢次數及剩餘數 第幾次查詢 剩餘待查詢元素數量 1 n 22 n 2 2 3 n 2 3 k n 2 k 從上表可以...