1樓：我不是他舅
氣泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第乙個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重複2號步驟，直至再也不能交換。
氣泡排序的平均時間複雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設陣列內存放了n個待排數字，陣列下標從1開始，到n結束。
i=1從陣列的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間複雜度也是o(n^2)的。
各種排序法的時間複雜度到底多少 10
2樓：世界文明導師
根據《演算法導論（中文版）》p83**以及《演算法（中文版）》部分章節版內容：
演算法 最壞情況執行時權間 平均情況
冒泡&&插入&&選擇 排序 n^2 n^2
快速排序 n^2 n*log n
希爾排序（希爾增量） n^2 n^(1.3 - 2)
堆排序 n*log n n*log n
注：希爾排序的效能依賴於選擇的增量。
以下排序演算法最壞情況下時間複雜度最低的是 a.氣泡排序 b.插入 c.選擇 d.快排
3樓：木頭釋然
在氣泡排序，插入排序，選擇排序，快速排序中，在最最壞情況下，快速排序的時間複雜為o(n2) ，插入排序o(n2)，選擇排序o(n2)，氣泡排序o(n2)。所以abcd時間複雜度是一樣的。
在快速排序演算法中，最為關鍵的就是選取乙個基值，將陣列分為大於基值以及小於基值兩部分，並返回基值所以在位置以利用於遞迴劃分。
對陣列a，設需要劃分的其中一段為a[p]~a[r]，我們期待的結果是得到乙個q，其中p<=q<=r，使得a[p]~a[q-1]<=a[q]<=a[q+1]~a[r]，這個時候原先的一段陣列被分成了三部分。
首先，設基值為這段陣列的最後乙個元素a[r]，我們希望最後得到的結果是a[r]現在對應的值在演算法結束後可以排在比他大和小的兩部分的中間愛。
然後令i=p-1; j=p，當發現有a[j]>x時，j繼續前進，不需要任何移動。當發現a[j]<=x時，我們需要將這個元素放到小於基值的一邊，於是將i自加1，並交換此時a[i]，與a[j]的元素，然後j自加1。這個時候i指向的是比基值小的那段資料的最後乙個元素，j指向的是第乙個還沒有判斷的剩餘元素。
上面一步不斷迴圈直到j指向了r，此時只剩下r沒有和基值判斷了，而a[r]本來就是基值，而除了a[r]以外，a[p]~a[i]是小於基值的部分，a[i+1]~a[r-1]是大於基值的部分，所以此時只需交換a[i+1]和a[r]即可。
由於對陣列a從頭到尾掃瞄一次就可以得到結果，因此這一部分演算法複雜度為o(n)
4樓：匿名使用者
1.選擇排序：不穩定，時間複雜度 o(n^2)
選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將l[i..n]中最小者與l[i]交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正確的了。
2.插入排序：穩定，時間複雜度 o(n^2)
插入排序的基本思想是，經過i-1遍處理後,l[1..i-1]己排好序。第i遍處理僅將l[i]插入l[1..
i-1]的適當位置，使得l[1..i] 又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。
首先比較l[i]和l[i-1]，如果l[i-1]≤ l[i]，則l[1..i]已排好序，第i遍處理就結束了；否則交換l[i]與l[i-1]的位置，繼續比較l[i-1]和l[i-2]，直到找到某乙個位置j(1≤j≤i-1)，使得l[j] ≤l[j+1]時為止。圖1演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。
3.氣泡排序：穩定，時間複雜度 o(n^2)
氣泡排序方法是最簡單的排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的「氣泡」，較小的元素比較輕，從而要往上浮。在氣泡排序演算法中我們要對這個「氣泡」序列處理若干遍。
所謂一遍處理，就是自底向上檢查一遍這個序列，並時刻注意兩個相鄰的元素的順序是否正確。如果發現兩個相鄰元素的順序不對，即「輕」的元素在下面，就交換它們的位置。顯然，處理一遍之後，「最輕」的元素就浮到了最高位置；處理二遍之後，「次輕」的元素就浮到了次高位置。
在作第二遍處理時，由於最高位置上的元素已是「最輕」元素，所以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經過前面i-1遍的處理，它們已正確地排好序。
4.堆排序：不穩定，時間複雜度 o(nlog n)
堆排序是一種樹形選擇排序，在排序過程中，將a[n]看成是完全二叉樹的順序儲存結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關係來選擇最小的元素。
5.歸併排序：穩定，時間複雜度 o(nlog n)
設有兩個有序（公升序）序列儲存在同一陣列中相鄰的位置上，不妨設為a[l..m]，a[m+1..h]，將它們歸併為乙個有序數列，並儲存在a[l..h]。
6.快速排序：不穩定，時間複雜度 最理想 o(nlogn) 最差時間o(n^2)
快速排序是對氣泡排序的一種本質改進。它的基本思想是通過一趟掃瞄後，使得排序序列的長度能大幅度地減少。在氣泡排序中，一次掃瞄只能確保最大數值的數移到正確位置，而待排序序列的長度可能只減少1。
快速排序通過一趟掃瞄，就能確保某個數（以它為基準點吧）的左邊各數都比它小，右邊各數都比它大。然後又用同樣的方法處理它左右兩邊的數，直到基準點的左右只有乙個元素為止。
幾種排序的時間複雜度，可以參考一下
5樓：匿名使用者
這幾個的最壞情況下的時間複雜度都是一樣的，一定要比較的話快排比較快，但氣泡排序比較穩定，最壞的話都是一樣的
6樓：匿名使用者
顯然都一樣，如果論平均時間就是快排最快o(nlogn)，其餘的都是o(n^2)，但快排最壞時間也是o(n^2)
7樓：匿名使用者
最壞的情況下好像都是n^2吧。
幾種常用的排序演算法以及其時間複雜度
8樓：呂布是天下無敵
資料排序演算法
哪種排序時間複雜度最低的?
9樓：匿名使用者
什麼情況下的時間複雜度，平均效能？最壞？最好？
平均最好的是快速排序，最壞情況下最好的看是記錄移動和關鍵字比較哪個佔主導，最好時最低的是氣泡排序
10樓：笪星嚴冷珍
最好是o(n)，這個時候陣列本身已經是排好序的
平均情況和最差都是o(n^2)
資料結構中各種排序的時間複雜度與空間複雜度比較！
11樓：匿名使用者
氣泡排序
是穩定的，演算法時間複雜度是o(n ^2)。 2.2 選擇排序（selection sort） 選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將l[i..
n]中最小者與l[i]交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正確的了。 選擇排序是不穩定的，演算法複雜度是o(n ^2 )。
2.3 插入排序 （insertion sort） 插入排序的基本思想是，經過i-1遍處理後,l[1..i-1]己排好序。
第i遍處理僅將l[i]插入l[1..i-1]的適當位置，使得l[1..i] 又是排好序的序列。
要達到這個目的，我們可以用順序比較的方法。首先比較l[i]和l[i-1]，如果l[i-1]≤ l[i]，則l[1..i]已排好序，第i遍處理就結束了；否則交換l[i]與l[i-1]的位置，繼續比較l[i-1]和l[i-2]，直到找到某乙個位置j(1≤j≤i-1)，使得l[j] ≤l[j+1]時為止。
圖1演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。 直接插入排序是穩定的，演算法時間複雜度是o(n ^2) 。 2.
4 堆排序 堆排序是一種樹形選擇排序，在排序過程中，將a[n]看成是完全二叉樹的順序儲存結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關係來選擇最小的元素。 堆排序是不穩定的，演算法時間複雜度o(nlog n)。 2.
5 歸併排序 設有兩個有序（公升序）序列儲存在同一陣列中相鄰的位置上，不妨設為a[l..m]，a[m+1..h]，將它們歸併為乙個有序數列，並儲存在a[l..
h]。 其時間複雜度無論是在最好情況下還是在最壞情況下均是o(nlog2n)。 2.
6 快速排序 快速排序是對氣泡排序的一種本質改進。它的基本思想是通過一趟掃瞄後，使得排序序列的長度能大幅度地減少。在氣泡排序中，一次掃瞄只能確保最大數值的數移到正確位置，而待排序序列的長度可能只減少1。
快速排序通過一趟掃瞄，就能確保某個數（以它為基準點吧）的左邊各數都比它小，右邊各數都比它大。然後又用同樣的方法處理它左右兩邊的數，直到基準點的左右只有乙個元素為止。 快速排序是不穩定的，最理想情況演算法時間複雜度o(nlog2n)，最壞o(n ^2)。
2.7 希爾排序 在直接插入排序演算法中，每次插入乙個數，使有序序列只增加1個節點，並且對插入下乙個數沒有提供任何幫助。如果比較相隔較遠距離（稱為 增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除多個元素交換。
d.l.shell於2023年在以他名字命名的排序演算法中實現了這一思想。
演算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然後再用乙個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。
希爾排序是不穩定的，其時間複雜度為o(n ^2)。 排序類別 時間複雜度 空間複雜度 穩定 1 插入排序 o(n2) 1 √ 2 希爾排序 o(n2) 1 × 3 氣泡排序 o(n2) 1 √ 4 選擇排序 o(n2) 1 × 5 快速排序 o(nlogn) o(logn) × 6 堆排序 o(nlogn) 1 × 7 歸併排序 o(nlogn) o(n) √
0 順序查詢， o(n) 二分， o(logn)需要排序分塊 分塊查詢？ 不知道..英文是什麼？
直接插入 o(n^2) 快速排序 最壞情況o(n^2) 平均o(nlogn) 起泡 和插入很像吧 o(n^2) 希爾，o(n^x) 1或< ）的排序演算法理論最低複雜度是o(nlogn) 證明： 所有可能情況為n! 構造決策樹需要n!
子節點 《為二分操作，所以樹為二叉樹，高度為o(logn!)=o(nlogn)
請教，快速排序的空間複雜度
快速排序每次將待排序陣列分為兩個部分，在理想狀況下，每一次都將待排序陣列劃分成等長兩個部分，則需要logn次劃分。而在最壞情況下，即陣列已經有序或大致有序的情況下，每次劃分只能減少乙個元素，快速排序將不幸退化為氣泡排序，所以快速排序時間複雜度下界為o nlogn 最壞情況為o n 2 在實際應用中，...
在下列排序演算法中，哪演算法的時間複雜度與初始排序無關
d不管原陣列是什麼樣子，每一次你都要遍歷一邊剩餘的數來選取最大 最小值 演算法的時間複雜度與初始排序無關的都有什麼排序 常見的幾種排序演算法複雜度如下 方式 平均 最壞 最好 插入 n 回2 n 2 n 希爾 n 1.3 冒泡 n 2 n 2 n 快速 nlogn n 2 nlogn 選擇 n 2 ...
關於時間複雜度的計算，如何計算時間複雜度？
給我十分，我告訴你答案。請問樓主答案，我也不會。如何計算時間複雜度？一般情況下，演算法的基本操作重複執行的次數是模組n的某乙個函式f n 因此，演算法的時間複雜度記做 t n o f n 隨著模組n的增大，演算法執行的時間的增長率和f n 的增長率成正比，所以f n 越小，演算法的時間複雜度越低，演...