插入排序算法的分析与比较

来源:用户上传      作者:李萍

　　摘要：排序算法作为计算机程序设计、数据库及操作系统等课程的重要基础，广泛应用于各种领域。该文介绍了直接插入排序、二分法插入、希尔排序的基本思想，实现代码，并针对不同数据进行比较。
　　关键词：直接插入;二分法插入;希尔排序
　　中图分类号：TP312 文献标识码：A
　　文章编号：1009-3044（2020）01-0289-02
　　1概述
　　排序是将一个数据元素的任意序列，重新排列成一个按关键词有序的序列。根据排序过程中依据不同的原则，将排序算法分为：插入排序、交换排序、选择排序、归并排序和计数排序五类。在不同环境下，每种算法都有各自的优缺点。我们从算法实现，不同数据进行运算比较，说明不同算法的优缺点。
　　2算法的基本思想
　　2.1直接插入排序
　　直接插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动，其代码实现如下：
　　2.2二分法插入排序
　　与直接插入排序相比较，基本思想是一致的，区别在于在查找待插入位置时，不再是从前往后或者从后往前依次相比较，而是和前面的有序表中间位置的元素相比较，如果待插入元素大，则直接和有序表的后半部分再次进行比较，否则缩至有序表的前半部分。其代码如下：
　　2.3希尔排序
　　希尔排序又称为“缩小增量排序”，将待排序记录按增量分成不同小组，在组内进行直接插入排序。其代码如下：
　　3结果分析
　　原始数据为：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
　　原始数据为：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
　　原始数据为：
　　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結论
　　对于无序数据希尔排序算法的移动次数明显小于其他，直接插入排序算法比较次数最多，希尔排序算法的运行时间比其他算法均长;对于递增数据希尔排序算法的比较次数和移动次数都小于其他算法，二分法算法的比较次数最多;对于递减数据直接插入算法比较最多，二分法插入算法比较次数最少，希尔算法的移动次数最少。
转载注明来源:https://www.xzbu.com/8/view-15143727.htm