王佳林

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

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

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

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

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

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

（二）插入排序的分類

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

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

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

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

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

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

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

時間復(fù)雜度分析：

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

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

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

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

空間復(fù)雜度分析：

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

算法穩(wěn)定性分析：

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

（四）直接插入排序的改進(jìn)

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

三、希爾排序（Shell Sort）

（一）希爾排序基本原理

希爾排序是在直接插入排序的基礎(chǔ)上的一種改進(jìn)，實(shí)際上是將待排序序列分組進(jìn)行直接插入排序，在分組時會出現(xiàn)增量這個概念，增量其實(shí)就是同一組數(shù)據(jù)中相鄰元素的下標(biāo)相隔距離。希爾排序利用了在數(shù)據(jù)量小、元素基本有序時直接插入排序的效率高的特點(diǎn)，大大提高了排序的效率。

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

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

時間復(fù)雜度分析：

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

希爾排序算法是不穩(wěn)定的，這一點(diǎn)在其程序代碼中也能發(fā)現(xiàn)，在進(jìn)行分組時兩個排序碼相同的元素的相對位置可能發(fā)生變化。

四、結(jié)語

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

參考文獻(xiàn)：

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

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