27.插入排序

自从上次小桂子发现了冒泡排序后，他开始相信自己的聪明才智比伴读小书童居然要高,所以他更加热衷于排序算法研究了，没事的时候，时不时找几个宫女演练一下，这时他又发现了一个新的排序方式，对于一下宫女们的队列：

1.首先，我们只考虑第一个元素，从第一个元素171 开始，该元素可以认为已经被排序；

2.取下一个元素161 并记录，并让161 所在位置空出来，在已经排序的元素序列中从后向前扫描；

3.该元素（171）大于新元素，将该元素移到下一位置；

4.171前已经没有最大的元素了, 则将161 插入到空出的位置；

5.取下一个元素163，并让163 所在位置空出来,在已经排序的元素序列中从后向前扫描；

6.该元素（171）大于新元素163，将该元素移到下一位置；

7.继续取171 前的元素新元素比较，直到找到已排序的元素小于或者等于新元素的位置；新元素大于161，则直接插入空位中；

8.重复步骤2~7，直到完成排序；

插入排序: 它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place 排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

具体算法描述如下：

1.从第一个元素开始，该元素可以认为已经被排序；

2.取出下一个元素，在已经排序的元素序列中从后向前扫描；

3.如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

4.将新元素插入到该位置；重复步骤2~5。

代码实现：

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

void swap(int* num1, int* num2)//交换两个指针保存的值
{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}

void InsertSort(int arr[], int len)
{
	int current = 0;
	int preIndex = 0;

	for (int i = 1; i < len; i++)
	{
		current = arr[i];
		preIndex = i - 1;

		while (preIndex >= 0 && arr[preIndex] > current)
		{
			arr[preIndex + 1] = arr[preIndex];
			preIndex--;
		}
		arr[preIndex + 1] = current;
	}
}

int main()
{
	int beauties[] = { 163, 161, 158, 165, 171, 170, 163, 159, 162 };

	int len = sizeof(beauties) / sizeof(beauties[0]);

	InsertSort(beauties, len);

	printf("美女排序以后的结果是：\n");
	for (int i = 0; i < len; i++)
	{
		printf("%d ", beauties[i]);
	}

	system("pause");
	return 0;
}

参考资料来源：

奇牛学院