- 交换排序 -- 冒泡排序
- 交换排序 -- 快速排序
- 选择排序 -- 简单选择排序
- 选择排序 -- 堆排序
- 插入排序 -- 简单插入排序
- 插入排序 -- 希尔排序
- 归并排序
- 基数排序
1.冒泡排序
指定一个元素和第二个元素进行比较，将下的放在前面，然后再让第二个和三个进行比较，
将最小的放在前面，每次对应的（i和j+1），直到最后只剩下一个元素，则结束，每次也要固定最大的元素
2.快速排序
是对冒泡排序的改进
在排序数组中随机找出一个数，一般取第一个或最后一个，称为基准数。
然后将比基准数小的排在左边，大的排在右边。和基准数进行交换，交换完后左边都是比基准数小的，
右边都是比基准数大的，这样就相当于将一个数组分成了两个子数组，
然后按同样的方法把子数组分成更小的数组，直到不能分解为止
- 选择一个基准位
- 从后往前遍历找到小于基准位的值
- 从前往后遍历找到大于基准位的值
- 将两个值交换
- 继续从两个位置从后往前找，从前往后找，交换
- 直到相遇，将碰头的值与基准值交换，将交换后中间的那个值固定
- 这时就分成分成了两个子序列，重复上面的操作
3.简单选择排序
- 从原始数据中选择最小的数字，将其和位于第一个位置的数据交换位置
- 从剩下的n-1个数据中选择次小的一个与第二个位置的数据交换位置
- 然后不断的重复，直到最后两个数据完成交换
4.堆排序
利用堆这种数据结构而设计的一种选择排序算法，难点在于二叉树的顺序数组存储到大顶堆（小顶堆）的转换
例如数组arr[1,2,5,4,6,3,7]
1.构建初始堆
2.转换成大顶堆
3.交换堆顶和末尾元素，取出最大元素
4。继续调整堆为大顶堆，然后重复上述，取出次大元素
5.继续重复，取出第三大元素，一直到取完所有元素
5.简单插入排序
1.把数组分为三个部分，有序段、待插入元素和无序段，最开始有序段只有第一个元素
2.把待插入元素放入有序段的段尾，进行依次比较大小，然后交换位置
优化措施：并没有降低算法的时间复杂度，但是减少了许多无谓的交换
例如这里的第四次插入，3与6先交换，3与5再交换，3与4又交换
我们可以把3保存起来，把4，5，6逐一复制到交换后的位置，然后再将3插入到交换后的位置，这样就不用三次交换了
6.希尔排序
希尔排序是简单插入排序的升级版
1.设置一个增量n/2（n为数组长度），将间隔为n/2的元素视为一组，然后组内进行简单插入排序
2.然后将增量缩小为n/4，再在组内进行简单插入排序
3.重复，直到增量为1，所有的元素为一个组，再次进行简单插入排序
7.归并排序
将一个数组的进行两两分组，进行组内排序，排好序后两个数为一个元素，两两元素内的所有数进行比较排序，
然后重复，最后只有两个元素，合并之后再比较排序
8.基数排序
基数排序是桶排序的推广，适合有不同的数字进行比较，
1.先到10个桶，0~9
2.第一轮排序按照个位数字大小排序，然后再按照十位排序，把未放入桶中的取出来，按顺序保存
3.然后千位排序，把未放入桶中的取出来，按顺序保存
4.重复到没有位数，把保存好的数字取出来就排序好了