常见的基本排序算法（十大经典排序算法）
常见的基本排序算法（十大经典排序算法）1.5、图片名词解释1.4、算法总结1.1、排序分类1.2、排序的定义1.3、术语说明
vs code ppt
END
c /java
目录
1.1、排序分类
1.2、排序的定义
1.3、术语说明
1.4、算法总结
1.5、图片名词解释
1.6、比较类排序与非比较类排序的区别
2.选择排序(Select Sort)
2.1、说明
2.2、算法描述
2.3、普通类代码
2.4、推导过程
2.5、以多态、泛型编程和STL实现选择排序
2.6、总结
1.1、排序分类
对一序列对象根据某个关键字进行排序。
1.3、术语说明稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。
内排序：所有排序操作都在内存中完成。
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
时间复杂度：一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。
1.4、算法总结
1.5、图片名词解释：
- n: 数据规模。
- k: “桶”的个数。
- In-place: 占用常数内存，不占用额外内存。
- Out-place: 占用额外内存。
1.6、比较类和非比较类的区别
(1)比较类：1、比较类排序 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn) 因此也称为非线性时间比较类排序。
2、比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。
(2)非比较类排序：1、不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
2、非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
- 选择排序(Select Sort)
选择排序(SelectSort)是一种简单直观的排序算法 表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
它的工作原理：
①首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
②然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
③以此类推，直到所有元素均排序完毕。
2.3、普通类代码(java)：
2.4、推导过程：
2.5、以多态、泛型编程和STL实现选择排序(c )
*注：#include “sort.h”头文件已经在冒泡排序2.5中展示，这里不在描述。
2.6、总结
(1) 分析时间复杂度：
1. 在最好的情况下，也就是序列有序的情况下，选择排序需要比较0次，时间复杂度为O(n^2)。
2. 在最坏的情况下，选择排序需要比较n-1次，时间复杂度为O(n^2)。
3. 在平均的情况下，选择排序需要比较n(n-1)/2次，时间复杂度为O(n2^)。
它的最大特点就是，交换移动数据次数相当少，这样也就节约了相应的时间，我们发现无论是最好、最坏还是平均情况下，它的时间复杂度都为O(n2)，但它是一个不稳定的算法。
往期推荐：
- 十大经典排序算法——冒泡排序
