Insertion Sort 插入排序

Author:

419Labs@gmail.com

Last Updated:

May 16, 2006

Tags:

算法, C语言

本文假设读者有以下知识：

C语言基础

插入排序是最简单的排序算法之一，是排序算法的基础。如果需要排序的元素数量很少，插入排序的速度很快，但是随着元素数量的增多，它的速度明显减慢。它的最坏情形运行时间是O(N²)。关于它的算法分析请参阅本文末尾的参考资料。

现在我们通过一个例子来看看插入排序的过程。假设要把5个整数(85, 40, 79, 80, 92)从小到大排列。

1. 先把85放在第一个位置上(85)
2. 然后把40放在第二个位置上(85,40)，再拿40和85作比较，小的放在前面(40,85)
3. 然后把79放在第三个位置上(40,85,79)，79与85比较，小的放前面(40,79,85)，79再与40比较，小的放在前面大的放在后面(40,79,85)
4. 把80放在第四个位置上(40,79,85,80)，80与85比较，调整位置(40,79,80,85)，80再与79比较，因为80比79大，所以不用调整位置，也不用再往前比较了。
5. 把92放在第五个位置上，然后与前一个数比较，如果比前面的数小就调整位置，如果比前面的数大就停止比较。92比80大，排序结束。最后结果是(40, 79, 80, 85, 92)

整个排序过程就是这样，如果完全按照上述过程来写程序，就需要两个数组，一个用来储存排序前的数列，一个用来储存排序后的数列。下面的 insertsort() 函数对这个过程作了一点小改进，只用一个数组和一个整型变量就可以了。

下面我们用C语言实现这个过程。

#include <stdio.h>
#include <stdlib.h>

#define MAX 10		// 要排序的元素个数

void insertsort(int A[], int N);
void printarray(int A[]);

int main()
{
  int i, s[MAX];

  for (i = 0; i < MAX; i++)	// 用随机函数产生MAX个整数
    s[i] = 1+(int) (100.0*rand()/(RAND_MAX+1.0));

  printf("before:");		// 排序前
  printarray(s);
  insertsort(s, MAX);		// 排序
  printf("after :");		// 排序后
  printarray(s);

  return 0;
}

void printarray(int a[])
{
  int i;
  for (i = 0; i < MAX; i++)
    printf(" %3d", a[i]);
  printf("\n");
}

/* [CLRS] Chapter 2.1 */
void insertsort(int A[], int n)
{
  int i, j, key;

  for (j = 1; j < n; j++)	// 注意C语言数组下标从0开始，A[1]是第二个元素
    {
      key = A[j];
      i = j - 1;
      while (i >= 0 && A[i] > key)
	{
	  A[i+1] = A[i];
	  --i;
	}
      A[i+1] = key;
    }
}

上面的 insertsort() 函数是用 Introduction to Algorithms（算法导论）的伪代码直接改写而成的。下面再提供另一种大同小异的写法，出自 Data Structures and Algorithm Analysis in C（数据结构与算法分析－－C语言描述）。

/* [Mark Allen Weiss] p.166 图 7-2 */
void insertsort(int a[], int n)
{
  int j, p;

  int temp;
  for (p = 1; p < n; p++) {
    temp = a[p];
    for (j = p; j > 0 && a[j-1]>temp; j--)
	a[j] = a[j-1];
    a[j] = temp;
  }
}

如果原始数据本来就是正确排序的（例如 1, 2, 3, 4, 5），那么插入排序的运行时间是O(N)，如果原始数据大部分已经排序（例如 1, 2, 4, 3, 5），那么插入排序的速度也很快，因为需要移动的数据很少。－－这是插入排序的一个重要的特点！希尔排序（Shell Sort）就是基于这个事实对插入排序进行改进的一个非常成功的算法。