数据结构实战

        从本章开始我们就来一起实现内部排序算法。当然我们为了抓住算法的本质而抛开其实际的应用，我们为了排序算法的简明扼要，排序算法本身所涉及到的数据结构中只是单纯的整数，在实际应用中可能是任何数据类型做为其关键字，并有一个存放数据的指针。而我们所使用的数据结构也是比较常见的线性表。数据存放在地址连续内存中的线性表，对其排序需要移动元素的位置，从而使线性表有序；而对于动态的线性表是通过指针来指向下一个元素的位置，那么需要修改其地址，从而使其有序。

        现在我们来实现第一个排序算法——插入排序。插入排序是一种简单的排序方法，它的思想是从头到尾遍历线性表，将元素插入一个有序的子表中，从而得到一个有序表。在将元素插入一个有序表的时候，首先要找到其在有序子表中的插入位置。这其实是一个“查找”的过程，我们在第七章中实现了很多查找的算法，完全可以用在这里，比如利用折半查找来实现插入排序。在这里为了代码简洁明了只使用顺序查找。

#include <stdio.h>

#define SIZE	(10)

//插入排序
void insert_sort(int *array, int size)
{
	//从第2个元素开始
	for (int i = 1; i < size; i++)
	{
		//取得当前元素值到t
		int t = array[i];
		//如果小于有序子表的最大值
		if (t < array[i - 1])
		{
			//插入有序子表
			for (int j = i; j > 0; j--)
			{
				//依次后移一个元素
				array[j] = array[j - 1];
				//如果找到插入位置
				if (t >= array[j - 1])
				{
					//插入t到有序子表
					array[j] = t;
					break;
				}
				//如果t大于有序子表的第1个元素
				if (j == 1 && t < array[0])
				{
					//插入t到有序子表的第1个位置上
					array[0] = t;
					break;
				}
			}
		}
	}
}

//显示数组
void display(int *array, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
}

int main(int argc, char **args)
{
	int array[SIZE] =
	{ 9, 3, 1, 2, 5, 8, 7, 0, 6, 4 };
	//显示数组
	display(array, SIZE);
	//插入排序
	insert_sort(array, SIZE);
	//显示数组
	display(array, SIZE);

	return 0;
}

        运行结果：

9 3 1 2 5 8 7 0 6 4 
0 1 2 3 4 5 6 7 8 9 

        本例代码：

code path   chapter.02/e.g.8.1/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure