算法基本知识铺垫

有些人可能不知道什么是稳定排序、原地排序、时间复杂度、空间复杂度，我这里先简单解释一下：

1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序

2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储 空间进行比较和交换的数据排序。

4、非原地排序：需要利用额外的数组来辅助排序。

5、时间复杂度：一个算法执行所消耗的时间。

6、空间复杂度：运行完一个算法所需的内存大小

十大排序一览图

十大排序中的稳定排序

冒泡排序（bubble sort） — O(n2)

插入排序 （insertion sort）— O(n2)

归并排序 （merge sort）— O(n log n)

十大排序中的非稳定排序

面试考察中一般问快排，选择，希尔，堆这几种非稳定排序

选择排序 selection sort）— O(n2)

希尔排序 （shell sort）— O(n log n)

堆排序 （heapsort）— O(n log n)

快速排序 （quicksort）— O(n log n)

插入排序基本思想：

1.从第一个元素开始，该元素可以认为已经被排序 2.取下一个元素tem，从已排序的元素序列从后往前扫描 3.如果该元素大于tem，则将该元素移到下一位 4.重复步骤3，直到找到已排序元素中小于等于tem的元素 5.tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置 6.重复步骤2~5

 在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。   但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

（1）我们用一个变量tmp存放关键字，因为我们先确定第一个元素是暂时有序的，所以tmp存放无序序列的第二个元素，然后i开始也为第二个元素的下标，j则为i-1，因为j要用有序的区域元素来与无序的区域元素比较。那么一开始i=1，tmp=6，j=0，因为6>4，所以6就不用进行插入；然后i向右走，i=2，tmp=arr[2]=8，j=i-1=1，8>6>4也不用插入。

（2）i继续向右走，i=3，tmp=arr[3]=5，j=i-1=2，5<8则要将8给5所在的元素数据，j向左走继续遍历有序区域。

（3）当j向右走到6时发现6>tmp=5，所以将6给它右边的第一个值(j+1的位置)，再继续遍历有序区域，j=0时发现4<5则j+1的位置就是5该在的位置那么就将tmp的值5给j+1的位置的元素的值

（4）再继续上面的操作，i最后到9发现比前面有序区域的元素都大，则不用再插入了，这样就得到了一个有序序列{4，5，6，8，9}

代码实现 

#include<iostream>
using namespace std;

void insertSort(int arr[], int length) {
	for (int i = 1; i < length; i++) {
		int temp = arr[i];  //待排序元素
		int j = i - 1;
		while (j >= 0 && arr[j] > temp) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = temp;

	}

}

int main() {

	int arr[9] = { 4, 6, 5, 8, 2, 3, 7, 1, 9 };
	int length = sizeof(arr) / sizeof(arr[0]);
	insertSort(arr, length);
	
	for (int i = 0; i < length; i++) {
		cout << arr[i] << " ";
	}

	return 0;
}