排序算法 C++实现（1）——直接插入法_设计直接插入排序的算法,输出每一趟排序结果。并用相关数据进行测试。

1，基本原理

     直接插⼊排序（Straight-Insertion-Sort）是⼀种最简单的排序⽅法，其基本操作是将⼀条记录插⼊到已排好的有序表中，从⽽得到⼀个新的、记录数量增1的有序表。
     通俗⼀点的讲，就是把数组中的元素⼀个个取出来，每取出⼀个就组成⼀个有序列表，直到将元素取完为⽌。例如：[20, 9, 14, 15, 30]这样⼀个数组，以升序为例，取第⼀个数时，组成有序列表20；取第⼆个数时，组成有序列表9,20；取第三个数时，组成9,14,20；取第四个数时，组成9,14,15,20；依次类推⾄取完元素为⽌。

2,原理动图演示:

3,代码实现

#include "stdafx.h"
#include<iostream>
//测试数组 正确顺序维 2，3,7,12,15,31,34，45,54,64,86
int data[] = { 12,45,2,64,54,31,86,34,15,3,7 };
 
void directInsert(int arr[], int count) {
	int tem = 0;
	for (int i = 1; i < count; i++) {
		tem = arr[i];
		for (int j = i - 1; j >= 0; j--) {
			if (tem< arr[j]) {
				arr[j + 1] = arr[j];
				arr[j] = tem;
			}
		}
	}
}
 
int main()
{
	std::cout << "原始数据   " << " ";
	for (int i = 0; i <11; i++) {
		std::cout << data[i] << " ";
	}
	std::cout << "   " << std::endl;
	directInsert(data, 11);
	std::cout << "排序数据    " << " ";
	for (int i = 0; i <11; i++) {
		std::cout << data[i] << " ";
	}
	std::cout << "   " << std::endl;
	system("echo 按回车继续...&pause>nul");
	return 0;
}

输出结果：

 代码实现的关键：从后向前比较，不满足添加对比数据二者调换位置，满足则该数的插入操作完成。还要要注意操作数的获取，需要在开始时用一个变量存起来。

4，时间复杂度和空间复杂度

 时间复杂度：O(n²)；

空间复杂度 ：O(1)；