一起学习交流~

排序-01-插入排序

算法 laomuji 12个月前 (10-07) 446次浏览 已收录 2个评论

一、什么是插入排序

插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动

二、插入排序的复杂度

时间复杂度
在插入排序中,当待排序数组是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较N- 1次,时间复杂度为O(N)
最坏的情况是待排序数组是逆序的,此时需要比较次数最多,总次数记为:1+2+3+…+N-1,所以,插入排序最坏情况下的时间复杂度为 O(N^2)
平均来说,A[1..j-1]中的一半元素小于A[j],一半元素大于A[j]。插入排序在平均情况运行时间与最坏情况运行时间一样,是输入规模的二次函数。
空间复杂度
插入排序的空间复杂度为常数阶 O(1)

三、插入排序的思路

思路一、交换思路

假设有一个有顺序的数组{0,1,2,3,4,5,6,8,9},需要把数字7插入进去

0123456897
0123456879
0123456789
0123456789

交换一:7和9比较,7小于9,7和9交换

交换二:7和8比较,7小于8,7和8交换

交换三:7和6比较,因为是有序数组,所以前面肯定都是小于6的,无需再比较

记录需要插入的数字,减少交换次数,实现插入排序的优化

012345689
0123456899
0123456889
0123456789

交换一:7和9比较,7小于9,9位置+1

交换二:7和8比较,7小于8,8位置+1

交换三:7和6比较,跳出循环,将7放入当前位置

思路二、分组思路

数组不可能都是排序好的,假设一个数组是{ 3,1,5,9,6,4,3,2,1,5 },显然不能直接排序

将该数组分组,比如0-1,0-2,0-3,0-n,此时就有了以下分组

31
315
3159
31596
315964
3159643
31596432
315964321
3159643215

第一次:假设数字1前面的是一个有序数组,要把1插入进去,进行思路一的交换,下标0-1变成有序

第二次:假设数字5前面的是一个有序数组,要把5插入进去,进行思路一的交换,下标0-2变成有序

第三次:假设数字9前面的是一个有序数组,要把9插入进去,进行思路一的交换,下标0-3变成有序

……

具体过程我写了个代码,效果如下:

经过9次交换后,得到正确的排序结果

四、具体代码

#include<iostream>
using namespace std;
void insertSort(int nums[], int length)
{
	//将数组分成n段
	//0-1,0-2,0-3,0-n
	//先把0-1设置为有序,再把0-2设置为有序...
	int i, j, temp;
	for (i = 1; i < length; i++)
	{
		//调试打印
		cout << "当前值:" << nums[i] << endl;
		cout << "交换前:";
		for (int k = 0; k <= i; k++)
		{
			cout << nums[k] << " ";
		}
		cout << endl;

		//首先记录需要插入的值
		temp = nums[i];
		//从后往前找合适的位置
		for (j = i - 1; j >= 0; j--)
		{
			//如果 前面的值比需要插入的值大
			//表示需要插入的值的位置不在当前位置
			//需要再往前找 并且 把值复制到后面
			//否则 前面的值比要插入的值小
			//就表示需要插入的值的位置在当前位置
			if (nums[j] > temp)nums[j + 1] = nums[j];
			else break;
			
		}
		nums[j + 1] = temp;

		cout << "交换后:";
		for (int k = 0; k <= i; k++)
		{
			cout << nums[k] << " ";
		}
		cout << endl << endl;
	}
}
int main()
{
	int nums[] = { 3,1,5,9,6,4,3,2,1,5 };
	insertSort(nums, 10);
	for (int i = 0; i < 10; i++)
	{
		cout << nums[i] << " ";
	}
	cout << endl;
	return 0;
}
喜欢 (0)
订阅评论
提醒
guest
2 评论
最旧
最新 最多投票
内联反馈
查看所有评论
姜世启
姜世启
11 月 前

老母鸡6666