基于c語(yǔ)言對(duì)插入排序算法的分析研究

王佳林

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

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

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

一、插入排序的基本原理及分類(lèi)

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

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

（二）插入排序的分類(lèi)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、希爾排序（Shell Sort）

（一）希爾排序基本原理

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

（二）希爾排序c語(yǔ)言程序代碼

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

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

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

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

四、結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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