(61)王道数据结构-排序的基本概念
基本概念
排序就是重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程。
严格定义
输入: n个记录R1,R2,…,Rn，对应的关键字为ki,k2,…,kn
输出: 输入序列的一个重排R1’,R2’,…,Rn’，使得有ki≤k2’≤…≤kn’， (其中“≤”可以换成其他的比较大小的符号)
评价指标
内部排序算法的性能取决于算法的时间复杂度和空间复杂度，而时间复杂度发般是由比较和移动的次数决定的。
算法的稳定性。若待排序表中有两个元素Ri和Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj的前面，若使用某一排序算法排序后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。需要注意的是，算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。
示例一:
排序前:6, 3, 2, 5, 1, 4, 3
排序后:1, 2, 3, 3, 4, 5, 6
排序前后，红色的三和蓝色的三顺序没变，所以稳定
示例二:
排序前:6, 3, 2, 5, 1, 4, 3
排序后:1, 2, 3, 3, 4, 5, 6
排序前后，红色的三和蓝色的三顺序变了，所以不稳定
注意: 对于不稳定的排序算法，只需举出一组关键字的实例，说明它的不稳定性即可
算法分类
内部排序
是指在排序期间元素全部存放在内存中的排序。关注的是如何使算法时间空间复杂度更低
外部排序
是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。除了关注时间空间复杂度以外还要关注如何使读/写磁盘次数更少
一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。通过比较两个关键字，确定对应元素的前后关系，然后通过移动元素以达到有序。当然，并非所有的内部排序算法都要基于比较操作，事实上，基数排序就不基于比较。
学习网站:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html