初阶算法（1）：通过简单的排序算法来认识时间复杂度-Toy模板网

这篇具有很好参考价值的文章主要介绍了初阶算法（1）：通过简单的排序算法来认识时间复杂度。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

系列文章目录

第一章初阶算法（1）：通过简单的排序算法来认识时间复杂度

第二章初阶算法（2）：进行详细地介绍插入排序的细节和时间复杂度

第三章初阶算法（3）：二分法的讲解与实现（C语言），以及二分不止光在有序数组中的应用

系列文章目录

前言

一、时间复杂度是什么？

常数时间的操作：

时间复杂度：

排序：

二、额外空间复杂度是什么？

总结

前言

总所周知，算法是程序员必须要学习的一项内容，而小编是个菜鸟，所以将笨鸟先飞，在这一系列，我会将我学习算法的亲身经历描写下来，将所学内容都记录下来，希望看到这篇文章的小伙伴一起加油！

在网上进行搜索算法学习，有一个大佬（英雄哪里来）也是先从排序入手，我也会进行适当的借鉴大佬的笔记。

一、时间复杂度是什么？

在认识时间复杂度之前，我们先引出一个知识：常数时间的操作。

1.1 常数时间的操作：

我们在写代码的时候会写一些指令，这些指令与数据量无关，是一个固定时间的操作，这就是常数时间的操作。

下面是一些例子：

一些表达式操作，数组寻址，从数组中取一个数等等。

在认识完常数时间的操作后，我们来通过排序进行认识时间复杂度。

1.2 时间复杂度：

1.2.1 排序：

首先，先来讲解选择排序算法。选择排序应该是最简单的排序了，下面是一个动图，（是借鉴英雄哪里来大佬的）。（英雄从哪里来）

初阶算法（1）：通过简单的排序算法来认识时间复杂度,初阶算法,算法,排序算法

在计算时间复杂度时，一般是考虑最坏步骤（所有步骤都进行）。在选择排序中，

初阶算法（1）：通过简单的排序算法来认识时间复杂度,初阶算法,算法,排序算法

int main()
{
	int n = 0;
	scanf("%d", &n);
	int arr[10000];
	int minIndex = 0;
	int temp = 0;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	for (int i = 0; i < n; i++)
	{
        minIndex = i;
		for (int j = i + 1; j < n; j++)
		{
			if (arr[minIndex] > arr[j])
			{
				minIndex = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = temp;
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}