排序1 （入门）

        直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的⼤⼩逐个插 ⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列 。

        

当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时

⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较，找到插⼊位置即将 array[i] 插⼊，原来位置上的元素顺序后移。

        

        我们拿这个数组来讲一下，开始让end存下第一个的下标，tmp存下数组end+1的位置。

如果小于的话，让arr[end+1]存入arr[end]的值，此时让end--，end<0了，出循环了，此时，再让arr[end]的位置放入我们tmp存的值。

        就为这样了。

        此时下次循环end指向了6的位置，tmp存下2的值。

        此时就比较，2<6.

        此时就成了这样了，1<2直接break了，此时让arr[end+1]的位置放入咱的tmp的值，循环往复，就完成了排序。

        

---

        2.2 希尔排序

        

        希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n/3+1），把 待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排 序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于 直接插⼊排序。

        它是在直接插⼊排序算法的基础上进⾏改进⽽来的，综合来说它的效率肯定是要⾼于直接插⼊排序算 法的。

        

        大概就是这么一个过程，类似于分组，先分几个组，然后再排序，话不多说，上代码。

        

        通过空值gap的值来分组，我是先除的三，相当于，第1个元素和第五个一组，第二个和第六个一组，最后一定gap是等于1的，相当于直接插入排序了，这个排序的思想就是先让一组无序的数变得基本有序，这样再用直接插入排序效率就很高了，然后按照直接插入排序的思想，再插入就行了。gap一定要>1，因为它一直都不会小于1，i要<n-gap，否则再取到gap-1后面的数组是，进行end+gap此时就越界了，通过外部的for循环从第一个开始，先找到他那一组的数，比较交换。此时就不需要和前面的全部都比较了，效率比较高，排成基本有序的之后，使用直接插入排序和前面，这个排序也很好理解，想学好排序自己一定要多找一些数组来模拟一下。

        

希尔排序的时间复杂度估算： o（n*logn）

---

---

        2.3 选择排序

选择排序的基本思想：

每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

2.2.1 直接选择排序

1. 在元素集合 array[i]--array[n-1] 中选择关键码最⼤(⼩)的数据元素

2. 若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素

交换

3. 在剩余的 array[i]--array[n-2]（array[i+1]--array[n-1]） 集合中，重复上述步

骤，直到集合剩余 1 个元素。

代码实现

        

        这个很简单，先通过min和max存下最小值的下标和最大值的下标，通过swap来交换，把最小的放在arr[min]处，最大的放在arr[max]中，此时就不要访问它俩了，让begin++和end--，再让i从begin+1开始，再次找到第二小和第二大的放入。

        我来解释一下为什么max==begin，max=min

        

        我们来看这个，此时我们该让min和begin交换了，但是此时再让max和end又交换了，但是此时3就被交换到end的位置了，此时begin位置放的就不是最小值了。这个排序也是很好理解的一个排序。

        2.4 冒泡排序

        

        这个就是我们常用的冒泡排序了，一次次的把大的往后挪。

        

        2.5 堆排序

        这个我在之前的博客中有详细的讲解过程，这里就不详细说了，可以看我前面的博客。

        

三.结束语

   感谢大家的查看，希望可以帮助到大家，做的不是太好还请见谅，其中有什么不懂的可以留言询问，我都会一一回答。  感谢大家的一键三连。