? ? ?常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括：

?

關于時間復雜度：

1.? ? ?平方階 (O(n2)) 排序各類簡單排序：直接插入、直接選擇和冒泡排序。

2.?????線性對數階 (O(nlog2n)) 排序快速排序、堆排序和歸并排序；

3.? ? ?O(n1+§))排序，§ 是介于 0 和 1 之間的常數。希爾排序

4.?????線性階 (O(n)) 排序基數排序，此外還有桶、箱排序。

關于穩定性：

? ? ?穩定的排序算法：冒泡排序、插入排序、歸并排序和基數排序。

?????不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

? ? ?n：數據規模

? ? ?k：“桶”的個數

? ? ?In-place：占用常數內存，不占用額外內存

? ? ?Out-place：占用額外內存

? ? ?穩定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同

希爾排序

希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序算法的改進。該方法又稱縮小增量排序，因DL．Shell于1959年提出而得名。

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。

希爾排序是基于插入排序的以下兩點性質而提出改進方法的：

• 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率；

• 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位；

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

1. 算法步驟

1.???????選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

2.???????按增量序列個數 k，對序列進行 k 趟排序；

3.???????每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

2. JavaScript 代碼實現

functionshellSort(arr)?{var?len?=arr.length,temp,gap?=1;while(gap?<?len/3)?{??????????//動態定義間隔序列gap?=gap*3+1;}for?(gap;?gap?>0;?gap?=Math.floor(gap/3))?{for?(var?i?=?gap;?i?<?len;?i++)?{temp?=?arr[i];for?(var?j?=?i-gap;?j?>=0&&?arr[j]?>?temp;?j-=gap)?{arr[j+gap]?=?arr[j];}arr[j+gap]?=?temp;}}return?arr;
}

3. Python 代碼實現

def?shellSort(arr):import?mathgap=1while(gap?<?len(arr)/3):gap?=?gap*3+1while?gap?>?0:for?i?in?range(gap,len(arr)):temp?=?arr[i]j?=?i-gapwhile?j?>=0?and?arr[j]?>?temp:arr[j+gap]=arr[j]j-=gaparr[j+gap]?=?tempgap?=?math.floor(gap/3)return?arr
}

4. Go 代碼實現

func?shellSort(arr?[]int)?[]int?{length?:=?len(arr)gap?:=?1for?gap?<?gap/3?{gap?=?gap*3?+?1}for?gap?>?0?{for?i?:=?gap;?i?<?length;?i++?{temp?:=?arr[i]j?:=?i?-?gapfor?j?>=?0?&&?arr[j]?>?temp?{arr[j+gap]?=?arr[j]j?-=?gap}arr[j+gap]?=?temp}gap?=?gap?/?3}return?arr
}

5.Java代碼實現

public?void?shellSort(int[]?list)?{int?gap?=?list.length?/?2;while?(1?<=?gap)?{//?把距離為?gap?的元素編為一個組，掃描所有組for?(int?i?=?gap;?i?<?list.length;?i++)?{int?j?=?0;int?temp?=?list[i];//?對距離為?gap?的元素組進行排序for?(j?=?i?-?gap;?j?>=?0?&&?temp?<?list[j];?j?=?j?-?gap)?{list[j?+?gap]?=?list[j];}list[j?+?gap]?=?temp;}System.out.format("gap?=?%d:\t",?gap);printAll(list);gap?=?gap?/?2;?//?減小增量}
}

探討交流技術、或者對編程感興趣，都可以加我qq： 525331804?