欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排序算法——插入排序

程序员文章站 2024-02-28 23:54:58
...

插入排序

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

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

时间复杂度

平均情况 最好情况 最坏情况
O(N2)O(N^2) O(N)O(N) O(N2)O(N^2)

空间复杂度

辅助存储
O(1)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;
	}
};
相关标签: 算法和数据结构