目录

直接插入排序

希尔排序

​编辑

选择排序

堆排序

冒泡排序

快速排序

hoare版

挖坑法

前后指针法

非递归

归并排序

非递归

计数排序

---

直接插入排序

直接插入排序跟依次模扑克牌一样，将最后一张牌依次与前面的牌比较，最后将牌插入到指定位置

单趟排序：将最后一个数依次与前面的数比较，如果前面的数比最后一个数大，就依次将前面的数后移，知道最后一个数到达位置

整体排序：从第二个数开始，依次进行单趟排序直到最后一个数

注意控制结束应为n-1，因为最后一个数下标为n-1，而每次比较用的下标为end+1，所以当下标为n-2时即比较最后一个数

单趟循环结束应为end>=0，因为如果为end>0，无法与第一个数进行比较

希尔排序

希尔排序是对直接插入排序的优化

希尔排序先将数组按照gap间隔分为几组进行插入排序，然后依次减小gap，再分组对数据进行插入排序，当gap==1时进行排序，数据会变为有序

选择排序

选择排序就相当于一次性摸了一把扑克牌，然后从中依次取出最大和最小分别插在队头和队尾，直到扑克牌有序

单趟排序：令最大和最小的下标为开头的数，然后从第二个数开始遍历直到最后一个数，在此过程中进行比较，改变maxi和mini的值，最后将mini和第一个数进行交换，maxi和最后一个数进行交换

整体排序：进行单趟排序后，改变begin和end的值，直到begin=end结束

注意：在单趟排序结束进行交换时，要注意maxi的下标，如果maxi==begin，那么先进行mini和begin两个数的交换就会将最大值交换到mini位置上，所以要进行判断，如果相等，那要令maxi=mini

堆排序

用向下建堆建大顶堆，然后依次将第一个最大的于最后一个交换

冒泡排序

每趟将一个最大的数排到数组末尾，然后将数组结束下标向前减一，注意控制结束下标

快速排序

hoare版

挖坑法

前后指针法

非递归

归并排序

1.把长度为n的输入序列分成两个长度为n/2的子序列；

​ 2.对这两个子序列分别采用归并排序；

​ 3.将两个排序好的子序列合并成一个最终的排序序列。

非递归

一一归，二二归，四四归

注意控制begin2和end2

计数排序

首先先找出待排序数组中的最大值和最小值，然后创建两者范围的数组，并将这个数组置为全0，然后根据每个数-min得到的值为下标存入创建的数组中，最后根据创建的数组下标+min存回a数组中