基于c語言對插入排序算法的分析研究

王佳林

摘要：數據處理是計算機編程中經常會遇到的問題，而數據排序又是數據處理中的重要組成部分，其中排序算法是數據排序中的核心技術。在很多情況下，排序算法決定著一個程序的執行效率，在實際的編程開發中如何根據具體的問題環境選擇合適有效的排序算法就顯得尤為重要。本文針對插入排序算法展開研究，對其排序算法原理和特點進行了分析，希望能給相關領域的學者帶來幫助。

關鍵詞：c語言;排序算法;直接插入排序;二分查找;希爾排序

隨著大數據時代的到來，數據量爆炸式增長，數據排序越顯重要。排序好的數據在進行各種操作時都會更加便捷，處理效率也會更高效。排序算法是數據排序的靈魂，決定著所用時間的多少，以及所占空間的大小。下面對基于c語言的插入排序進行詳細的分析研究。

一、插入排序的基本原理及分類

（一）插入排序的基本原理

插入排序是內部排序算法的一種，其基本原理是在一次插入操作中，按照排序碼的大小，將一個待排序元素插入到一組有序元素的適當位置上去，直到元素全部插入為止。

（二）插入排序的分類

在執行具體插入操作時，根據插入方法的不同，主要分為三種插入排序算法，分別是直接插入排序、帶二分查找的直接插入排序和希爾排序。下面對這三種插入排序算法進行詳細分析。

二、直接插入排序（Straight Insertion Sort）

（一）直接插入排序的基本思想

直接插入排序的基本思想是在一組待排序的元素中，按一定的順序取出一個元素，將這個元素按排序碼的大小插入到排好序了的元素序列中，進而得到一個新的有序的總元素數目加一的有序表，直到所有的元素都插入到這個有序表中為止。

（二）直接插入排序詳細過程及c語言程序代碼

下面舉例說明，假設有一個N=6個的待排序元素，排序碼相同的用*加以區分。其中的臨時變量temp起暫存的作用。

（三）直接插入排序算法的性能分析

時間復雜度分析：

初始元素的序列是是影響直接插入排序效率的主要因素，根據初始元素序列的不同其時間復雜度有很大區別。

（1）初始序列是順序排列時，比較N1次即可完成排序，時間復雜度O（N）。

（2）初始序列是逆序排列時，需比較N*（N1）/2次，時間復雜度O（N^2）。

（3）初始序列雜亂無序時，平均時間復雜度O（N^2）。

空間復雜度分析：

在直接插入排序中，臨時變量temp暫存待插入元素，空間復雜度O（1）。

算法穩定性分析：

所謂算法穩定性指的是如果待排序記錄中有重復元素，在排序后這些元素的相對位置如果保持不變，那么這個排序算法就是穩定的。反之則不穩定。在圖（a）中容易發現排序碼相同的記錄的相對位置沒有變化，可見直接插入排序算法是穩定的排序算法。

（四）直接插入排序的改進

直接插入排序算法在進行位置查找操作中可以進行性能改進，那就是在尋找合適的插入位置時，使用二分查找算法，但插入操作的基本原理不變，這樣就可以大大減少元素比較次數，提高算法效率。這種改進之后的算法又叫帶二分查找的直接插入排序。

三、希爾排序（Shell Sort）

（一）希爾排序基本原理

希爾排序是在直接插入排序的基礎上的一種改進，實際上是將待排序序列分組進行直接插入排序，在分組時會出現增量這個概念，增量其實就是同一組數據中相鄰元素的下標相隔距離。希爾排序利用了在數據量小、元素基本有序時直接插入排序的效率高的特點，大大提高了排序的效率。

（二）希爾排序c語言程序代碼

（三）希爾排序算法性能分析

時間復雜度分析：

希爾排序算法的時間復雜度分析較復雜，整個過程中元素的比較次數和移動次數因所選擇的增量的不同而有較大差異。整體上來看希爾排序的時間復雜度是O（N*logN）。步長gap不同時間復雜度會受影響，根據現有研究隨著步長變化希爾排序時間復雜度在O（N*logN）與O（N^2）之間，具體詳細的時間復雜度與步長gap的關系還在研究中。

希爾排序算法是不穩定的，這一點在其程序代碼中也能發現，在進行分組時兩個排序碼相同的元素的相對位置可能發生變化。

四、結語

在這個數據時代中，數據處理是經常會遇到的問題，數據排序是數據處理中很重要的一環，研究排序算法具有重要的意義。本文主要研究了基于c語言的插入排序算法，并對三種插入排序算法進行了詳細的分析。明確各種排序算法的適用條件，熟練掌握算法思想，針對實際問題靈活運用，有助于我們更好的完成數據處理工作。

參考文獻：

[1]李晶.直接插入排序算法分析與實現[J].中國科技信息，2007（24）：347+349.

[2]劉模群.排序算法時間復雜度研究[J].軟件導刊，2012，11（06）：3538.