常用的排序算法的時間復雜度和空間復雜度
排序法最差時間分析????平均時間復雜度????穩(wěn)定度????空間復雜度
冒泡排序????O(n2)????O(n2)????穩(wěn)定????????O(1)
插入排序????O(n2)????O(n2)????穩(wěn)定????O(1)
選擇排序????O(n2)????O(n2)????穩(wěn)定????O(1)
二叉樹排序????O(n2????)O(n*log2n)????不一定????O(n)
快速排序????O(n2)????O(n*log2n)????不穩(wěn)定????????O(log2n)~O(n)
堆排序????O(n*log2n)????O(n*log2n)????不穩(wěn)定????????O(1)
希爾排序????O????????O????不穩(wěn)定????O(1)
查找算法時間復雜度
查找算法實現(xiàn)：順序查找 二分查找 二叉樹排序查找 哈希表法（散列表） 分塊查找
冒泡排序
? ? ? ? ? 冒泡排序重復地走訪過要排序的數(shù)列啼止，一次比較兩個元素狂打，如果他們的順序錯誤就把他們交換過來败匹。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換，也就是說排序完成。規(guī)模比較小的時候應用冒泡排序，主要應用于教學。摘悴。。
選擇排序--只會移動N次
? ? ? ? ?選擇排序的主要思想：首先找到數(shù)組中最小的那個元素舰绘，其次蹂喻，將它和第一個元素交換。接下來找第二小和第二個交換捂寿。運行時間和輸入無關口四，數(shù)據(jù)移動最少。當數(shù)據(jù)量較小的時候適用秦陋。
插入排序
時間復雜度為O(n^2)蔓彩，數(shù)據(jù)量小時使用。并且大部分已經(jīng)被排序驳概。
快速排序
? ? ? ?快速排序是最快的通用排序算法赤嚼，在大多數(shù)實際情況中，快速排序是最佳選擇顺又。在java的默認排序中是使用的是三向切分排序更卒。
歸并排序
? ? ? 如果需要穩(wěn)定，空間不是很重要稚照，請選擇歸并蹂空。
O(n)時間復雜度的桶排序
? ? ?當范圍已經(jīng)知道俯萌，而且空間不是很重要的情況下使用桶排序。
總結(jié)排序
(1)若n較小(如n≤50)上枕，可采用直接插入或直接選擇排序绳瘟。
??? 當記錄規(guī)模較小時，直接插入排序較好姿骏；否則因為直接選擇移動的記錄數(shù)少于直接插人，應選直接選擇排序為宜斤彼。
(2)若文件初始狀態(tài)基本有序(指正序)分瘦，則應選用直接插人、冒泡或隨機的快速排序為宜琉苇；
(3)若n較大嘲玫，則應采用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序并扇。
??? 快速排序是目前基于比較的內(nèi)部排序中被認為是最好的方法去团，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短穷蛹；
??? 堆排序所需的輔助空間少于快速排序土陪，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的肴熏。
??? 若要求排序穩(wěn)定鬼雀，則可選用歸并排序。但本章介紹的從單個記錄起進行兩兩歸并的? 排序算法并不值得提倡蛙吏，通吃戳ǎ可以將它和直接插入排序結(jié)合在一起使用。先利用直接插入排序求得較長的有序子文件鸦做，然后再兩兩歸并之励烦。因為直接插入排序是穩(wěn)定 的，所以改進后的歸并排序仍是穩(wěn)定的泼诱。
---------------------
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
