排序算法所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
排序算法，就是如何使得记录按照要求排列的方法。
排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。
一个优秀的算法可以节省大量的资源。
在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。
分类排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排列成一个关键字有序的序列。
稳定度(稳定性)一个排序算法是稳定的，就是当有两个相等记录的关键字R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。
然而，假设以下的数对将要以他们的第一个数字来排序。
(4,1)(3,1)(3,7)(5,6)在这个状况下，有可能产生两种不同的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有:(3,1)(3,7)(4,1)(5,6) (维持次序)(3,7)(3,1)(4,1)(5,6) (次序被改变)不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。
不稳定排序算法可以被特别地实现为稳定。
作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，就会被决定使用在原先数据次序中的条目，当作一个同分决赛。
然而，要记住这种次序通常牵涉到额外的空间负担。
在计算机科学所使用的排序算法通常被分类为:(a)计算的复杂度(最差、平均、和最好性能)，依据列表(list)的大小(n)。
一般而言，好的性能是O(nlogn)，且坏的性能是O(n^2)。
对于一个排序理想的性能是O(n)。
而仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(nlogn)。
(b)存储器使用量(空间复杂度)(以及其他电脑资源的使用)(c)稳定度:稳定的排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。
八大排序算法排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
我们这里说说八大排序就是内部排序。
基本思想:将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。
即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要点：设立哨兵，作为临时存储和判断数组边界之用。
直接插入排序示例：如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。
所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
算法的实现：1.void print(int a[], int n ,int i){2. cout<<i <<":";3.for(int j= 0; j<8; j++){4. cout<<a[j] <<" ";5. }6. cout<<endl;7.}8.9.10.void InsertSort(int a[], int n)11.{12.for(int i= 1; i<n; i++){13.if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。
小于的话，移动有序表后插入14.int j= i-1;15.int x = a[i]; //复制为哨兵，即存储待排序元素16. a[i] = a[i-1]; //先后移一个元素17.while(x < a[j]){ //查找在有序表的插入位置18. a[j+1] = a[j];19. j--; //元素后移20. }21. a[j+1] = x; //插入到正确位置22. }23. print(a,n,i); //打印每趟排序的结果24. }25.26.}27.28.int main(){29.int a[8] = {3,1,5,7,2,4,9,6};30. InsertSort(a,8);31. print(a,8,8);32.}效率：时间复杂度：O（n^2）.其他的插入排序有二分插入排序，2-路插入排序。
选择排序的原理
一、引言
选择排序是一种简单但效率较低的排序算法，它的原理是在待排序序列中选择最小（或最大）的元素，将其放到序列的起始位置，然后再从剩余未排序的元素中继续选择最小（或最大）的元素，放到已排序序列的末尾。
这个过程不断重复，直到所有元素都排好序为止。
二、算法步骤
1. 首先在未排序序列中找到最小（或最大）元素，并记录其位置。
2. 将该元素与未排序序列的起始位置交换。
3. 接着，在剩余未排序的元素中继续寻找最小（或最大）元素，并记录其位置。
4. 将该元素与已排序序列末尾的下一个位置交换。
5. 重复步骤3和4，直到所有元素都排好序。
三、时间复杂度
选择排序的时间复杂度为O(n^2)，其中n为待排序序列长度。
这是因为每次循环都需要遍历剩余未排序部分来寻找最小（或最大）值。
四、稳定性
选择排序是不稳定的。
例如，在一个数组中有两个相同值但位置不同
的元素，在第一次循环时可能会将靠后面那个元素提前，导致排序后它们的相对位置发生变化。
五、优化
1. 增加一个变量记录最小值的位置，避免每次循环都重新寻找。
2. 对于已经有序的部分，可以不再进行排序。
3. 可以使用堆排序来替代选择排序，从而获得更高效的算法。
六、总结
选择排序是一种简单但效率较低的排序算法。
它的原理是在待排序序列中选择最小（或最大）的元素，将其放到序列的起始位置，然后再从剩余未排序的元素中继续选择最小（或最大）的元素，放到已排序序列的末尾。
该算法时间复杂度为O(n^2)，不稳定。
为了提高算法效率，可以进行优化。
