排序算法2 - 直接插入排序

什么是直接插入排序算法？

  直接插入排序算法（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

解析：

  划重点 必须是排好序的有序表，插入数据后得到一个新的、记录数增加1的有序表。

  什么是有序表，无序表？如图：

  代码实现 把6插入到数组{ 1, 2, 3, 4, 5, 7, 8, 9, 10 }中，实现方法可以从前面开始遍历数组，找到合适的位置然后插入，

  也可以从后面开始遍历数组，找到合适的位置然后插入（前提是数组大小能容纳插入后的数据）， 现假设数组够大，然后使用

  "0"来表示空元素。

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

int main(void)
{
	int arr[10] = { 1, 2, 3, 4, 5, 7, 8, 9, 10, 0}; // 0表示空
	int num = 6, i;
	
	// 插入前
	for(i=0; i<10; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	// 从后面遍历寻找位置，并把数据进行移位
	for(i=9; arr[i]>num || arr[i]==0; i--) // 0表示空
	{
		arr[i] = arr[i-1]; // 把前面的数据后移
	}
	arr[i+1] = num; // 找到位置，把数据插入


	// 插入后
	for(i=0; i<10; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	return 0;
}

  如果现有数组 arr[10] = {5, 2, 6, 1, 3, 9, 10, 7, 4, 8}; 使用直接插入排序怎么实现呢？

  解决2个前提 1. 有序表，2. 待插入的数据。

  第1步：把数组的第0个元素看做一个有序表 {5}， 第1个元素看做待插入数据 2 ，插入后数组arr[10] = {2, 5, 6, 1, 3, 9, 10, 7, 4, 8};

  第2步：把数组的前2个元素看做一个有序表 {2，5}， 第2个元素看做待插入数据 6 ，插入后数组arr[10] = {2, 5, 6, 1, 3, 9, 10, 7, 4, 8};

  第n步...... 如图：

  动图：

  代码：

#include <stdio.h>

void InsertSort(int k[], int n)
{
	int i, j, temp;

	for( i=1; i<n; i++ )
	{
		if( k[i-1]>k[i] )
		{
			temp = k[i];
			for( j=i-1; k[j]>temp; j--)
			{
				k[j+1] = k[j];
			}

			k[j+1] = temp;
		}
	}
}


int main()
{
	int i, a[10] = {5,2,6,1,3,9,10,7,4,8};

	InsertSort(a, 10);

	printf("排序后的结果是：");
	for(i=0; i<10; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}