AI_第一部分 数据结构与算法（10.排序简介）

第四阶段我们进行深度学习(AI)，本部分（第一部分）主要是对底层的数据结构与算法部分进行详尽的讲解，通过本部分的学习主要达到以下两方面的效果：

1.对开发中常见的算法能应用自如，让你在跳槽找工作中“算法题”不再是阻碍你“钱途”的拦路虎。

2.我们不需要调参数的调参攻城狮，我们要做正真的自己的AI模型。

3.本部分预计40篇左右。

今天我们聊聊排序，说起排序，对于工科的同学来说呢，首先想到的就是冒泡排序，哈哈我也是滴，记得上学学c语言的时候就学了那个冒泡排序，之前面试的时候也是让手写过冒泡排序。今天我们从大的概念来聊聊排序。

第一、如何分析一个排序算法

要分析一个算法，我们需要从一下几个方面来进行分析：

1.1.排序算法的执行效率

1.2.排序算法的内存消耗

1.3.排序算法的稳定性

第二、执行效率分析

2.1.最好、最坏、平均情况下时间复杂度

为什么要区分这三个时间复杂度呢？

其一、有些排序算法会区分，为了好对比，所以需要区分。 其二、对于需要排序的数据，有的接近有序，有的完全无 序。有序度不同的数据，对于排序的执行时间肯定是有影 响 的，我们要知道排序算法在不同数据下的表现。

2.2.时间复杂度的系数、常数、低阶

时间复杂度反映的是数据规模n很大的时候一个增长的趋势，所以它表示的时候会忽略系数、常数、低阶。但是在实际开发环境中，我们排序的可能只有100个、1000个这样的数据规模，所以对于同阶时间复杂度的排序算法性能对比的时候，我们也是需要把系数、常数、低阶都要考虑进去。

2.3.比较次数和交换（移动）次数

基于比较的排序算法的执行过程，会涉及到两种操作，一种是元素的比较大小，另一种是元素交换或者移动。所以，如果在分析排序算法的执行效率的时候，应该吧比较次数和交换（移动）次数也要考虑进去。

第三、排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量，排序算法也是不例外的，不过针对于排序算法的空间复杂度，我们引入一个概念：原地排序(sorted in place),原地排序算法，就是指空间复杂度是O（1）的排序算法。

第四、排序算法的稳定性

仅仅从执行效率和内存消耗来衡量排序算法好坏是不够的。稳定性这个概念就是说，当待排序的序列中存在值相等的元素，经过排序之后，相等的元素之间原有的先后顺序是不变的。

我们举一个简单的case:

我们有一组数据：1、4、5、4、7、2

排序后的顺序是：1、2、4、4、5、7

这个数据中有两个4，经过某种排序后，如果两个4的前后关系没有发生变化那就是稳定的排序，反之为不稳定的排序。

好了，今天我们对于排序的讨论就到此结束了，后续我们开始具体的排序算法的内容。