(資料圖片)

冒泡排序

從頭開始，兩兩依次比較，直到找出這組數(shù)據(jù)中最大的，放在最后面，重復(fù)此過程，直到有序 時(shí)間復(fù)雜度：o(n^2) 空間復(fù)雜度：o(1) 穩(wěn)定性：穩(wěn)定 優(yōu)點(diǎn)：簡單，易實(shí)現(xiàn)，不需要額外空間 缺點(diǎn)： `效率低

選擇排序：從頭開始，依次找最小的，放在第一個(gè)，直到有序 時(shí)間復(fù)雜度：o(n^2) 空間復(fù)雜度：o(1) 穩(wěn)定性：不穩(wěn)定 優(yōu)點(diǎn)：表現(xiàn)最穩(wěn)定，時(shí)間復(fù)雜度永遠(yuǎn)o(n^2),不需要額外空間 缺點(diǎn)：穩(wěn)定性上講，不穩(wěn)定，效率低

插入排序：從頭開始，不斷地將當(dāng)前數(shù)據(jù)插入到之前排好的數(shù)據(jù)中，直到最后一個(gè) 時(shí)間復(fù)雜度：o(n^2) 空間復(fù)雜度：o(1) 穩(wěn)定性：穩(wěn)定 優(yōu)點(diǎn)：效率略高于選擇和冒泡，穩(wěn)定 缺點(diǎn)：效率不高

希爾排序：將一組數(shù)據(jù)分成若干組，每個(gè)組中第一個(gè)元素與第二個(gè)元素相差“增量”個(gè)元素，對(duì)每個(gè)組進(jìn)行插入排序，然后逐漸減小增量，分小組，直到增量為1（只有一個(gè)組）。 時(shí)間復(fù)雜度：o(nlogn) 空間復(fù)雜度：o(1) 穩(wěn)定性：不穩(wěn)定 優(yōu)點(diǎn)：效率高于三種簡單排序，不需要額外空間 缺點(diǎn)：不穩(wěn)定

快速排序：從一組數(shù)據(jù)中找出一個(gè)基準(zhǔn)，然后從后向前找比這個(gè)基準(zhǔn)小的，放在基準(zhǔn)位置，然后再從前向后找比基準(zhǔn)大的，放在剛剛那個(gè)數(shù)字的位置，循環(huán)此過程，直到基準(zhǔn)找到合適的位置，使基準(zhǔn)前面的數(shù)字小于基準(zhǔn)，基準(zhǔn)后面的數(shù)字大于基準(zhǔn)。接著換一個(gè)基準(zhǔn)重復(fù)此方法,直到數(shù)列有序。 時(shí)間復(fù)雜度：o(nlogn) 空間復(fù)雜度：o(logn) 穩(wěn)定性：不穩(wěn)定 優(yōu)點(diǎn)：排序速度最快

歸并排序：(二路歸并排序)將一個(gè)長度為n的數(shù)列，兩兩分組，組的個(gè)數(shù)>=2，對(duì)每個(gè)組內(nèi)排序；再將兩個(gè)組合并，排序，合并，排序，直到整個(gè)數(shù)列有序。 時(shí)間復(fù)雜度：o(nlogn) 空間復(fù)雜度：o(n) 穩(wěn)定性：穩(wěn)定

堆排序：大頂堆：每個(gè)節(jié)點(diǎn)的值都大于其左右孩子 將一組數(shù)維護(hù)成大頂堆，找出堆頂元素拿走（交換堆頂元素和堆底元素，堆的元素個(gè)數(shù)減一），重新維護(hù)成一個(gè)大頂堆，重復(fù)操作，直到數(shù)列有序 時(shí)間復(fù)雜度：o(nlogn) 空間復(fù)雜度：o(n) 穩(wěn)定性：不穩(wěn)定

基數(shù)排序：將一組數(shù)按個(gè)位元素分別放到0~9（十個(gè)桶）中，然后按十個(gè)桶的順序取出（先去0號(hào)桶，再取1號(hào)桶…）,然后按十位元素分十個(gè)桶，將數(shù)字按十位元素再次放入，再次取出，直到數(shù)列有序。 時(shí)間復(fù)雜度：o(n*k) k:桶的個(gè)數(shù) 空間復(fù)雜度：o(n+k) 穩(wěn)定性：穩(wěn)定 缺點(diǎn)：不能對(duì)小數(shù)排序，只針對(duì)整數(shù)