【数据结构】--排序算法

我们在学习c语言的时候就已经接触过排序了的，我们当时学习数组的时，就学习过冒泡排序，我们的排序算法主要分为下面几种：

 我们先复习一下我们的冒泡排序：

我们看看其时间复杂度，其两个循环嵌套，然后其最坏的情况就是其完全是逆序的，那么每一次都需要进行交换，那么我们的时间复杂度最坏的情况就是O(n*n)，那么最好的情况就是其已经是升序的，那么我们的时间复杂度就为O(n)，那么其平均情况下时间复杂度就为O(n^2)。 

一、直接插入排序

相信我们都有打过扑克牌，我们在摸牌的时候总是会将已经摸到的排先进行排序，然后后面摸到的排就会找到其合适的位置然后再进行插入。

那么我们的直接插入排序是如何的呢？

其算法的原理如下：

当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时 ⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较，找到插⼊位置 即将 array[i] 插⼊，原来位置上的元素顺序后移。

如下图所示：

 那么我们在代码中要如何进行实现呢？

首先我们在一个乱序的数组中，认为第一个元素其是有序的，然后我们将其和后续的元素进行比较然后进行排序，那么我们可以创建两个变量，一个变量表示当前数组已经排好序的位置，然后一个变量进行存储要进行排序插入的元素，那么这个要进行排序插入的元素的下标就应该为已经排好序的这个位置的下一个元素。

然后我们就可以进行排序了，我们可以从已经排好序的这个位置开始往前找，然后找到合适的位置那么我们就插入，那么我们要如何找呢？

我们看上面的图，其要插入的元素和已经排序好的部分数组一个一个进行比较，然后当其比比已经排序好的数组的元素大的时候，那么其就在其后面一个位置进行插入，然后如果要插入的元素比已经排序好的数组的元素要小，那么我们的排序好的数组的元素就往后移动一位，而且也不会产生将后面的元素覆盖的情况，因为我们后面的元素已经保存到一个变量中了。

那么我们的循环要上面条件下可以结束呢？

首先我们第一层循环就是一个，按照数组的元素个数来决定，然后内层的话就是，其比较到最后，数组的下标都走到-1了，那么此时就不再需要进行比较了，这个要插入的元素就是最小的，那么我们就直接将其插入即可，不过要注意的是，我们要插入到下标为0的位置。

代码如下：

下面我们测试一下：

 

运行结果：

 

我们看看这个算法的时间复杂度：

最坏情况：当数组是乱序的时候，那么此时每个元素都需要进行比较排序，此时的时间复杂度为1+2+3+4+5+6 +.......+(n-1)=n*(n-1)/2=O(n^2)。

最好情况：数组是有序的，那么就只需要进行遍历，那么时间复杂度为O(n)。

我们这个算法其时间复杂度要比堆排序差，然后其比冒泡排序要好一点，其就最坏的情况下时间复杂度会和冒泡排序一样。

不过其代码比堆排序的要简单，然后其算法比较稳定，后面我们再讲算法的稳定性。

 二、希尔排序

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

其实现步骤如下：

 其实际上就是将数组分成几组，然后其组内先进行排序，然后再将这个数组的分组的数量减少，然后再进行排序，直到其分组的数量为1的时候，那么我们就再进行一次排序，那么此时我们的数组的排序就完成了。

我们的分组就是一个数组，我们将其从头开始每隔gap分到一组。

我们的分组一般是为gap/3+1。为啥要加1呢？

保证最终 gap=1：如果没有 +1，当 gap=2 时，2/3=0，会导致排序提前终止（未完成）。

平滑递减：+1 确保 gap 不会跳过某些关键值（如 2、1）。

那么我们的代码要如何写呢？

首先我们第一个循环，应该就为数组的组数，不过我们在循环前，要先记录下数组的元素个数，然后我们进入循环后，首先就改变gap，将其/3+1,然后我们使用一个for循环进行遍历比较。那么我们的循环条件是啥呢？

其不可以越界进行访问数组，那么我们的条件就为数组的长度-gap。

然后，就是直接插入排序了。

代码如下：

运行如下：

希尔排序的时间复杂度目前我们的数学的计算方法暂时没法计算，不过根据严蔚敏书中给出的时间复杂度为：O(n^1.3)。

三、选择排序

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

 首先我们默认这个数组是无序的，然后我们遍历数组找这个数组的最小的元素，然后将这个最小的元素放在数组的前面，然后，我们继续如此操作，要注意的是，每执行一次这个操作，我们遍历的起始位置就要进行更新。直到其最后只剩一个数据，就可以结束排序了。那么我们为了更快完成排序，那么我们可以最大的和最小的一起找，找到后，大的往后放，小的往先放。

代码如下：

运行如下：