八大排序算法

1. 交换排序 -- 冒泡排序
2. 交换排序 -- 快速排序
3. 选择排序 -- 简单选择排序
4. 选择排序 -- 堆排序
5. 插入排序 -- 简单插入排序
6. 插入排序 -- 希尔排序
7. 归并排序
8. 基数排序

1.冒泡排序

指定一个元素和第二个元素进行比较，将下的放在前面，然后再让第二个和三个进行比较，

将最小的放在前面，每次对应的（i和j+1），直到最后只剩下一个元素，则结束，每次也要固定最大的元素

 2.快速排序

是对冒泡排序的改进

在排序数组中随机找出一个数，一般取第一个或最后一个，称为基准数。

然后将比基准数小的排在左边，大的排在右边。和基准数进行交换，交换完后左边都是比基准数小的，

右边都是比基准数大的，这样就相当于将一个数组分成了两个子数组，

然后按同样的方法把子数组分成更小的数组，直到不能分解为止

1. 选择一个基准位
2. 从后往前遍历找到小于基准位的值
3. 从前往后遍历找到大于基准位的值
4. 将两个值交换
5. 继续从两个位置从后往前找，从前往后找，交换
6. 直到相遇，将碰头的值与基准值交换，将交换后中间的那个值固定
7. 这时就分成分成了两个子序列，重复上面的操作

 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.重复到没有位数，把保存好的数字取出来就排序好了

八大排序算法

原文：https://www.cnblogs.com/enjoyC/p/15152370.html