插入排序

拥有一个无序的数组，我们只需先拿一个数（一般拿第一个），把它先当作一个有序的数组。然后把这个无序数组中其它数分别插入到已经有序的数组中即可。

代码构造思路：首先得考虑要用什么数据结构，是链表还是顺序表。在下面的代码中，我使用的是顺序表，其实就是普通的数组。然后因为我拿第一个数做为已经有序的数组，剩下只需要把其它在无序数组中的数，插入到有序数组中即可，所以外循环其实只需要循环n-1次。而每次循环的nums[i]其实就是代rug表当前要插入的数，然后构造内循环，内循环所循环的其实就是已经有序的数组，从尾到头进行遍历，至于为什么是从尾到头，当然是因为在顺序表中执行插入操作，不管插入到哪里，插入位置后面的数组自然都需要往后移一个位置，而在插入排序中，从尾到头的遍历的时候，在比较的同时，也在移动数组中数的位置。就是需要插入的数需要排在当前遍历到的有序数组的数的前面，自然需要把这个数后移，而因为是从尾到头的遍历，所以每一次的比较的位置不是正确的位置，都会把当前有序数组的数往后一位，直到找到合适的位置，进行插入。而这个合适的位置就是nums[j + 1] = insertNum。

时间复杂度：

平均情况	最好情况	最坏情况
$O (N^{2})$	$O (N)$	$O (N^{2})$

空间复杂度：

辅助存储
$O (1)$

class Solution {
public:
	Solution() {}
	~Solution() {}
	vector<int> sortArray(vector<int>& nums) {
		int len = nums.size();
		for (int i = 1; i < len; ++i) {
			int insertNum = nums[i];
			int j;
			for (j = i - 1; j >= 0 && insertNum < nums[j]; --j) { 
				nums[j + 1] = nums[j];
			}
			nums[j + 1] = insertNum;
		}
		return nums;
	}
};

排序算法——插入排序

插入排序