先總結一下演算法的時間複雜度

此文章只對前4種演算法做總結

一. 氣泡排序(BubbleSort)

基本思想：

兩個數比較大小，較大的數下沉，較小的數冒起來。

過程：

比較相鄰的兩個資料，如果第二個數小，就交換位置。

從後向前兩兩比較，一直到比較最前兩個資料。最終最小數被交換到起始的位置，這樣第一個最小數的位置就排好了。

繼續重複上述過程，依次將第2.3...n-1個最小數排好位置。

平均時間複雜度：O(n2)

java程式碼實現：

優化：

針對問題

資料的順序排好之後，冒泡演算法仍然會繼續進行下一輪的比較，直到arr.length-1次，後面的比較沒有意義的。

方案

設定標誌位flag，如果發生了交換flag設定為true；如果沒有交換就設定為false。

這樣當一輪比較結束後如果flag仍為false，即：這一輪沒有發生交換，說明資料的順序已經排好，沒有必要繼續進行下去。

例項

二. 選擇排序(SelctionSort)

基本思想：

在長度為N的無序陣列中，第一次遍歷n-1個數，找到最小的數值與第一個元素交換；

第二次遍歷n-2個數，找到最小的數值與第二個元素交換；

。。。

第n-1次遍歷，找到最小的數值與第n-1個元素交換，排序完成。

過程：

平均時間複雜度：

O(n2)

java程式碼實現：

三. 插入排序(Insertion Sort)

基本思想：

在要排序的一組數中，假定前n-1個數已經排好序，現在將第n個數插到前面的有序數列中，使得這n個數也是排好順序的。如此反覆迴圈，直到全部排好順序。

過程：

平均時間複雜度：

O(n2)

java程式碼實現：

四. 希爾排序(Shell Sort)

前言：

資料序列1： 13-17-20-42-28 利用插入排序，13-17-20-28-42. Number of swap:1;

資料序列2： 13-17-20-42-14 利用插入排序，13-14-17-20-42. Number of swap:3;

如果資料序列基本有序，使用插入排序會更加高效。

基本思想：

在要排序的一組數中，根據某一增量分為若干子序列，並對子序列分別進行插入排序。

然後逐漸將增量減小,並重覆上述過程。直至增量為1,此時資料序列基本有序,最後進行插入排序。

過程：

希爾排序

平均時間複雜度：

O(n1.5)

java程式碼實現：