插入排序——重温排序(一)

avatar
在这个系列,我会逐一介绍几种常见的排序。介绍的内容包括:排序的思想、复杂度分析、代码实现等。首先来了解一下插入排序。

前言

有句话说,只有能把学过的东西用自己的话讲给别人听,才能算是真正掌握了。我对此深以为然,于是下定决心开始写技术博客,提升自身技术水平。至于选择写排序的原因有三个:第一个是刚开始写东西,想选比较简单的东西来锻炼一下表达能力,为后续的写作打下基础;第二个是虽说排序比较简单,但是在面试中还是挺多被问到(我就曾经在面试生涯中被问过两次快速排序),可在实际工作中却并不怎么常用,因此时间一久难免生疏,所以刚好也做一下复习;第三个是把知识点重新整理之后,会更方便自己后续的回顾。

一、排序概述

首先简单介绍一下一些排序中的基本概念。

1. 分类

内部排序:整个排序过程都在内存中进行的排序。
外部排序:由于数据量过多,不可能将所有数据都读入内存,因此需要借助磁盘等存储媒介来进行的排序。

2. 基本操作

排序的两个基本操作:比较、移动。

3. 时间复杂度

时间复杂度的衡量标准:比较次数、移动次数。

4. 稳定性

稳定性判断标准:两个相等的元素,排序前后在序列中的顺序是否一致。

二、插入排序

下面步入正题,开始介绍插入排序。插入排序的思想用一句话来描述就是,每一步将一个待排序的元素,按照其关键字的大小,插入到前面已经排好序的有序表的正确位置,直到所有元素插入结束为止

1. 算法描述

插入排序的算法可以归结为下面3句话。

  • 当插入第i(i>=1)个元素时,前面的r[1]、r[2]、…、r[i-1]已经排好序。
  • r[i]的关键字与r[i-1]、r[i-2]的关键字顺序进行比较,如果小于,则将r[x]向后移动,否则说明已经找到插入位置。
  • 找到插入位置即将r[i]插入。

2. 简单图示

这是一个完整的插入排序例子,其中有两个关键字为25的元素,注意观察它们在排序前后的位置关系。

avatar

3. 算法实现

下面是简单的C语言实现版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
void insertSort(int list[], int count) {
int temp, i, j;
for (i = 1; i < count; ++i) {
temp = list[i];
for (j = i - 1; j >= 0; --j) {
if (list[j] <= temp) {
break;
}
list[j+1] = list[j];
}
list[j+1] = temp;
}
}

4. 算法分析

从上面的例子可以看出,如果排序前数组已经有序,则每次只需要与有序序列的最后一个元素比较,总比较次数为n-1,不需要移动。
而最坏的情况,每一趟每个关键字每次比较都需要移动,总的比较次数和移动次数都约为 n^2 / 2
在平均情况下,比较次数和移动次数都约为 n^2 / 4,因此插入排序的时间复杂度是O(n^2)

从上面图示的例子可以看到,带*的关键字为25的元素,排序前后都在另一个关键字为25的元素后面,因此插入排序是一种稳定的排序

5. 总结

  • 插入排序的时间复杂度为O(n^2)
  • 插入排序是一种稳定的排序。

从插入排序可以看出,当待排序列为正序时,时间复杂度为O(n),当基本有序的时候,排序的效率也会快很多。
所以有没有一种方法,可以先让序列先变得基本有序,然后再进行插入排序,以此来提高效率呢?

答案是肯定的,那正是下节要介绍的内容 —— 希尔排序