排序演算法優化思考
最近行情很不好，公司這幾天的動作比較大，總的來說就是要與員工共同度過這段艱難時刻，雖然也沒看到有福同享，但是有難還是得一起來擔的。面對行業不景氣，作為一名勵志的程式猿也不能閑著，這不，為了將之前的基礎知識給補上，也為了今後的進一步發展，這段時間一直在學習C的數據結構與演算法，書是我浩哥推薦的，看完了近半內容，書的品質還是不錯的，知識正確性至少有保證，其傳授的思想也多是帶著讀者一步一步思考，如何改進、完善演算法。這些方面我認為挺好，學了不少，也收穫不小，感謝浩哥推書，行業十幾年經歷對我這種小萌新還是非常有借鑒作用，鏈接已放文末，有興趣的道友可以拜讀。
本期博文總結歸納幾種排序演算法，分別為選擇、插入、冒泡、希爾排序。老實說，在沒有學習之前雖知道有這幾種排序演算法，但就其差別還不是非常清楚。於是有了這篇博文，對四類排序演算法的思考。世界之大、演算法無盡，如果僅僅是照搬演算法的程式碼，可能花費你的一生也不一定能閱盡所有，所以在學習演算法之前必須先有一個正確的觀念——演算法被創造出來的目的是解決問題，問題的解決方法不只有唯一一種，我們學習的也僅僅是在一定條件下的最優解。接下來講解的幾種排序演算法都是比較經典且容易理解，適用小量數據排序
選擇排序
在介紹演算法之前我們聊一聊影響演算法效率的相關因素，我們不得不區分時間與空間的概念，空間即演算法佔用的系統記憶體，時間即演算法從開始執行到結束執行所花費的時間，這兩者在演算法中非常矛盾，一般的，如果想要演算法執行時間短，演算法就會越複雜，佔用的記憶體空間就越多，二者不可兼得，所以在演算法設計之初，就必須要提前規劃犧牲其中一部分。具體來說影響時間效率的本質是演算法中的內部循環，演算法中的變數、指針、結構體則影響演算法的佔用記憶體，所以提高演算法的效率需要從兩者入手。選擇排序中對從小到大排序設計思路是遍歷一遍所有數據，將最小數據選出來放在首位，接著遍歷一遍剩餘數據，選出次小數據並放入第二位，以此類推，最後的最大數據就被放在了數組尾部。演算法思路非常簡單，程式碼量也不大，但是犧牲了執行的時間，其執行時間與N^2成正比。
void selection(int *a,int n) //選擇排序 先選出最小的元素與前面元素交換
{
int i,j,temp;
for(i = 0;i < n-1;i++)
{
int min = i;
for(j = i+1;j < n;j++)
if(a[j] < a[min])
min = j;
{
temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
}
上面是這幾天學到的一種選擇排序的優化演算法，其設計思路沒有改變，對第二個for循環進行了優化，對比在第二個for循環中交換數據，極大提高了執行效率，將數據交換的次數減少到了一次。
插入排序
在我們打撲克的時候，為了便於出牌，我們會將手中撲克按照從小到大或是從大到小的順序依次排列，插入排序演算法的設計思想也是如此，在數組左邊依次排序，對右邊出現的數據依次與其左邊的數據做比較，直至確認其位置。演算法實現非常直接，但是不高效，對比常用與優化之後的用例，優化方案用三種方法來對演算法進行改善。（i）首先將數組中最小的元素放在第一位 （ii）在內部循環中只做一個簡單賦值，而不是執行交換操作 （iii）當元素插入到正確位置就終止內循環。
常用：
void insertion(int *a,int n) //兩兩互換
{
int i,j,temp;
for(i = 1;i < n;i++)
for(j = i;j > 0;j--)
if(a[j-1] > a[j])
{
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
優化：
void insertions(int *a,int n) //兩兩互換
{
int i,j,temp;
for(i = n-1;i > 0;i--) //將最小元素放在第一位
if(a[i] < a[i-1])
{
temp = a[i];
a[i] = a[i-1];
a[i-1] = temp;
}
for(i = 2;i < n;i++)
{
j = i;
temp = a[i];
while(temp < a[j-1]) //循環找出a[i]元素在左邊排序中的位置
{
a[j] = a[j-1];
j--;
}
a[j] = temp;
}
}
冒泡排序
冒泡排序非常簡單，其演算法思想為：遍歷文件，如果鄰近的兩個元素大小順序不對，就將兩者交換，重複這樣的操作直至所有數據排好序。可以發現冒泡演算法與常規的插入演算法類似，其主要差別在於冒泡演算法從右往左移動，插入是從左向右移動。
void bubble(int *a,int n)
{
int i,j,temp;
for(i = 0;i < n-1;i++)
for(j = n-1;j > i;j--)
if(a[j-1] < a[j]) //大數往前冒泡
{
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
一般來說，排序演算法的運行時間是和演算法執行的比較次數，元素移動或交換的次數成正比的。在選擇排序中，平均使用${N2}/2$次的比較，N次交換，插入排序中，平均使用${N2}/4$次比較與${N2}/4$次的交換，冒泡排序中，平均使用${N2}/2$次比較，${N2}/2$次交換。可以發現上述三種演算法執行時間都是與N2相關。
希爾排序
希爾排序是插入排序的擴展，其本質還是插入排序，希爾排序改進了插入排序只能進行相鄰比較的缺陷，允許一定步長間的比較與元素交換，如固定步長4，a[0]與a[4]比較交換，a[4]與a[8]可以比較交換，最終選出所有元素中以4為間隔的元素中的最值放入a[0],接著使步長為1，依次使用插入排序。研究表明就不同步長序列，其演算法執行時間不同，對於步長滿足3h+1規律的，其演算法執行時間與N^(3/2)成正比。較上述三類排序，希爾排序演算法明顯改善了執行時間。
void shellsort(int *a,int n)
{
int i,h;
for(h = 0;h <= (n-1)/9;h = h*3+1); //首次增量值
for(;h > 0;h /= 3)
for(i = h;i < n;i = i+h)
{
int j = i,item = a[i];
while((item < a[j-h])&&j >= h)
{
a[j] = a[j-h];
j -= h;
}
a[j] = item;
}
}
當然，演算法間的執行效率比較都是建立在N無窮大時，N越大，四類演算法間的時間差距越明顯
創作不易，白嫖不好，各位的支援和認可，就是我創作的最大動力，我們下篇文章見！
清風 | 文 【原創】
如果本篇部落格有任何錯誤，請批評指教，不勝感激 ！
