1樓：_鈊_煩_薏亂
氣泡排序是穩定的，演算法時間複雜度是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)√
2樓：求是的夢
順序查詢， 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)
演算法用英文倒不是我崇洋媚外 只是從大學才開始學，而我們學校的教科書都是英語的.
排序演算法的穩定性和演算法的具體實現有關 通常認為不穩定的快排也有一些小技巧讓他穩定
每種查詢方法的時間複雜度
3樓：宛丘山人
直接查詢複雜度：o(n)
二分查詢複雜度：o(log2(n))
分塊（索引）查詢複雜度在直接查詢複雜度與二分查詢複雜度之間雜湊查詢複查度與資料規模無關，只與查詢因子、雜湊函式的選取、衝突處理方式相關。
幾種排序的時間複雜度
4樓：我不是他舅
氣泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重複2號步驟，直至再也不能交換。
氣泡排序的平均時間複雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設陣列記憶體放了n個待排數字，陣列下標從1開始，到n結束。
i=1從陣列的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間複雜度也是o(n^2)的。
幾種常用的排序演算法以及其時間複雜度
5樓：呂布是天下無敵
資料**：https://zh.wikipedia.org/wiki/排序演算法
幾種排序以及其時間複雜度
6樓：我不是他舅
氣泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的專第一個數字到屬倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重複2號步驟，直至再也不能交換。
氣泡排序的平均時間複雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設陣列記憶體放了n個待排數字，陣列下標從1開始，到n結束。
i=1從陣列的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間複雜度也是o(n^2)的。
時間複雜度為On的排序演算法，你會嗎
排序方法 最壞時間複雜度 最好時間複雜度 平均時間複雜度直接插入 o n2 o n o n2 簡單選擇 o n2 o n2 o n2 起泡專排序屬 o n2 o n o n2 快速排序 o n2 o nlog2n o nlog2n 堆排序 o nlog2n o nlog2n o nlog2n 歸併排...
演算法的時間複雜度和空間複雜度怎麼看
時間複雜度，就是計算程式執行的時間，空間複雜度，就是所佔的記憶體空間。同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。電腦科學中，演算法的時間複雜度是一個函式，它定量描述了該演算法的執行時間。這是一個關於代表演算法輸入值...
演算法的複雜度主要包括演算法的時間複雜度和空間複雜度，演算法的時間複雜度是指
時間複雜度考慮的是演算法的執行時間，因此是d 演算法的空間複雜度指的是什麼？1 簡單來說bai 演算法的空間du 複雜度指的是佔zhi用記憶體 dao，cpu等計算機資源回的程度。答 2 具體點來解釋就是 空間複雜度 space complexity 是對一個演算法在執行過程中臨時佔用儲存空間大小的...