常见排序算法之插入排序

Program
, ,

由这篇博文开始，来回顾一下常见的排序算法。算法实现主要以Python语言为主。

插入排序，对于少量的元素排序，它是一个有效的算法。插入排序的方式有点类似于打扑克牌的时候抓牌后，然后根据牌的大小插入到合适的位置。

插入排序的基本思想:

每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。

插入排序的工作过程的伪代码表示

1
2
3
4
5
6
7
8
9
10
11
12
13
INSERTION-SORT(A)
	for j = 2 to A.length
		#取当前位置元素作为待比较元素
	 	key = A[j]
		#获取到需要比较的元素的下标
		i = j -1
		#进行比较，如果待比较元素比当前元素大，则将待比较元素和当前元素进行交换（从当前元素开始，逐个向后移动一个位置，为待比较元素腾出个位置来）
		while i > 0 and A[i] > key
			A[i+1] = A[i]
			i = i -1
			#腾位置结束
		#将待比较的元素赋值给腾出来的位置，然后继续下一次循环，直到排序完成
		A[i+1] = key

插入排序的Python代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# -*- coding:utf-8 -*-

A = [5,2,4,6,1,3]

def insert_sort(Array_A):
    for j in range(1,len(Array_A)):
        key = Array_A[j]
        i = j - 1
        while i >= 0 and Array_A[i] > key:
            Array_A[i+1] = Array_A[i]
            i = i -1
        Array_A[i+1] = key
        print '第%s次插入：' % (j),Array_A
        
insert_sort(A)
print '插入排序结果：',A

运行结果：

1
2
3
4
5
6
第1次插入： [2, 5, 4, 6, 1, 3]
第2次插入： [2, 4, 5, 6, 1, 3]
第3次插入： [2, 4, 5, 6, 1, 3]
第4次插入： [1, 2, 4, 5, 6, 3]
第5次插入： [1, 2, 3, 4, 5, 6]
插入排序结果： [1, 2, 3, 4, 5, 6]

通过结果可以很清楚的看到每次排序过程。

插入排序算法的分析

  1. 最好的情况下，排序前对象已经按照要求有序。比较次数：n-1;移动次数:0。对应的时间复杂度为O(n)
  2. 最坏的情况下，排序前对象为要求的顺序的反序。第i趟时第i各对象必须与前面i个对象都做排序码比较，并且每做一侧比较就要做一次数据移动。时间复杂度为O(n2)
  3. 如果记录是随机的，时间复杂度为O(n2)

插入排序算法的特点

  1. 它是稳定排序，不改变相同元素原来的顺序
  2. 它是in-place排序，只需要O(1)的额外内存空间
  3. 它是在线排序，可以边接收数据边排序
  4. 它跟我们排扑克牌的方式相似
  5. 对小数据集是有效的