APP下载

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

2020-03-30李萍

电脑知识与技术 2020年1期

李萍

摘要:排序算法作为计算机程序设计、数据库及操作系统等课程的重要基础,广泛应用于各种领域。该文介绍了直接插入排序、二分法插入、希尔排序的基本思想,实现代码,并针对不同数据进行比较。

关键词:直接插入;二分法插入;希尔排序

中图分类号:TP312 文献标识码:A

文章编号:1009-3044(2020)01-0289-02

1概述

排序是将一个数据元素的任意序列,重新排列成一个按关键词有序的序列。根据排序过程中依据不同的原则,将排序算法分为:插入排序、交换排序、选择排序、归并排序和计数排序五类。在不同环境下,每种算法都有各自的优缺点。我们从算法实现,不同数据进行运算比较,说明不同算法的优缺点。

2算法的基本思想

2.1直接插入排序

直接插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动,其代码实现如下:

2.2二分法插入排序

与直接插入排序相比较,基本思想是一致的,区别在于在查找待插入位置时,不再是从前往后或者从后往前依次相比较,而是和前面的有序表中间位置的元素相比较,如果待插入元素大,则直接和有序表的后半部分再次进行比较,否则缩至有序表的前半部分。其代码如下:

2.3希尔排序

希尔排序又称为“缩小增量排序”,将待排序记录按增量分成不同小组,在组内进行直接插入排序。……

登录APP查看全文