排序算法

一、插入排序

1.直接插入排序

算法穩定，時間複雜度為O(n^2)，空間移動複雜度為O(n2)

如果序列是有序的，最好的時間複雜度為O(n)

2.折半插入排序

查找插入位置采用折半查找法。

算法穩定，時間複雜度為O(nlog2n)，空間移動複雜度為O(n2)

3.希爾排序

将待排資料分組，組内進行直接插入排序。逐漸減小分組數，最後再整體進行直接插入排序。

希爾排序的時間複雜度為介于O(nlog2n)與O(n*n)之間，大約為O(n1.3);

希爾排序算法是不穩定的。

二、交換排序

1.冒泡排序

時間複雜度為O(n*n),是穩定的排序算法。

2.快速排序

分治法的思想，最壞的情況是待排資料時有序的時候，此時會造成軸元素的一側子序列的長度為0，另一側的長度為n，此時時間複雜度為O(n*n)

空間複雜度主要是遞歸調用的棧的開銷，最好的時候是O(logn),最壞的情況是O(n).

平均的時間複雜度為：O(nlogn);

該算法是不穩定的。

三、選擇排序

1.簡單選擇排序

時間複雜度為O(n*n),空間複雜度為O(1)

是不穩定為排序算法。

2.堆排序

最大堆的調整函數為shiftdown()函數。

每次最多執行O(logn)次資料的交換，是以其時間複雜度為O(nlogn).

空間開銷是O(1).

四、歸并排序

最壞的情況下的時間發複雜度也為O(nlogn),算法是穩定的。

空間複雜度為O(n).