- 比较排序，时间复杂度为O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等
- 非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等
原理：比较两个相邻的元素，将值大的元素交换到右边
分析：N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次
时间复杂度：
如果我们的数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)
如果很不幸我们的数据是反序的，则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值
综上所述：冒泡排序总的平均时间复杂度为：O(n2) ,时间复杂度和数据状况无关
选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
优点：无需额外的空间
时间复杂度：
无论数据怎样，时间复杂度都是O（n2),因此数据规模越小越好。
插入排序
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
假设对n个元素进行插入排序，则需要进行n-1趟排序。
- 最好情况：元素升序有序。那么我们只需要进行n-1次元素比较，0次元素移动即可。
- 最坏情况：元素降序有序。那么我们需要进行n*(n-1) /2 次元素比较，同样次数的元素移动。
插入排序法的平均时间复杂度是 O（n2)
插入排序适合于小序列的排序，当序列长度小于等于20或20左右时，使用插入排序效率更高。
插入排序的特点是：基于比较、数据移动完成排序
一次比较操作后不发生数据移动或仅仅交换一对相邻的数据元素。
所以插入排序的时间复杂度
最坏情况：O(n2) 最好情况O(n) 平均情况O(n2)
归并排序
几个关键点：
1. 建立在归并操作上的有效排序算法。
2.采用分治法
3.和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
算法过程：
-
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
-
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
-
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
-
重复步骤 3 直到某一指针达到序列尾；
-
将另一序列剩下的所有元素直接复制到合并序列尾。
堆排序
【图示全过程】数据结构与算法 - 堆排序_ZUCK的博客-CSDN博客
快速排序
数据结构与算法 - 快速排序_ZUCK的博客-CSDN博客
