插入排序算法的分析與比較

李萍

摘要：排序算法作為計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫(kù)及操作系統(tǒng)等課程的重要基礎(chǔ)，廣泛應(yīng)用于各種領(lǐng)域。該文介紹了直接插入排序、二分法插入、希爾排序的基本思想，實(shí)現(xiàn)代碼，并針對(duì)不同數(shù)據(jù)進(jìn)行比較。

關(guān)鍵詞：直接插入;二分法插入;希爾排序

中圖分類(lèi)號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）01-0289-02

1概述

排序是將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵詞有序的序列。根據(jù)排序過(guò)程中依據(jù)不同的原則，將排序算法分為：插入排序、交換排序、選擇排序、歸并排序和計(jì)數(shù)排序五類(lèi)。在不同環(huán)境下，每種算法都有各自的優(yōu)缺點(diǎn)。我們從算法實(shí)現(xiàn)，不同數(shù)據(jù)進(jìn)行運(yùn)算比較，說(shuō)明不同算法的優(yōu)缺點(diǎn)。

2算法的基本思想

2.1直接插入排序

直接插入排序是一種最簡(jiǎn)單的排序方法，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而一個(gè)新的、記錄數(shù)增1的有序表。在其實(shí)現(xiàn)過(guò)程使用雙層循環(huán)，外層循環(huán)對(duì)除了第一個(gè)元素之外的所有元素，內(nèi)層循環(huán)對(duì)當(dāng)前元素前面有序表進(jìn)行待插入位置查找，并進(jìn)行移動(dòng)，其代碼實(shí)現(xiàn)如下：

2.2二分法插入排序

與直接插入排序相比較，基本思想是一致的，區(qū)別在于在查找待插入位置時(shí)，不再是從前往后或者從后往前依次相比較，而是和前面的有序表中間位置的元素相比較，如果待插入元素大，則直接和有序表的后半部分再次進(jìn)行比較，否則縮至有序表的前半部分。其代碼如下：

2.3希爾排序

希爾排序又稱(chēng)為“縮小增量排序”，將待排序記錄按增量分成不同小組，在組內(nèi)進(jìn)行直接插入排序。其代碼如下：

3結(jié)果分析

原始數(shù)據(jù)為：80 33 25 4 13 92 68 75 30 38 46 42 1526 8 23 37 98 83 72 65 3 18 22 34 44 55 85 70 60

原始數(shù)據(jù)為：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1819 20 21 22 23 24 25 26 27 28 29 30

原始數(shù)據(jù)為：

30 29 28 27 26 25 24 23 22 21 20 19 18 171 16 15 14 13 1211 10 9 8 7 6 54 3 21

4結(jié)論

對(duì)于無(wú)序數(shù)據(jù)希爾排序算法的移動(dòng)次數(shù)明顯小于其他，直接插入排序算法比較次數(shù)最多，希爾排序算法的運(yùn)行時(shí)間比其他算法均長(zhǎng);對(duì)于遞增數(shù)據(jù)希爾排序算法的比較次數(shù)和移動(dòng)次數(shù)都小于其他算法，二分法算法的比較次數(shù)最多;對(duì)于遞減數(shù)據(jù)直接插入算法比較最多，二分法插入算法比較次數(shù)最少，希爾算法的移動(dòng)次數(shù)最少。