【数据结构】插入排序，希尔排序，选择排序，堆排序，冒泡排序

1.插入排序

思路：插入排序将一个数插入一个有序的数组里面，将这个数和数组元素挨着比较，直到他插入到合适的位置。
动画演示：

步骤：1.定义一个变量tmp保存要插入的数据
2.在循环中用tmp和有序数组中的元素比较（比方说要和a[end]比较，如果tmp<a[end]的话，就将a[end]右移动到a[end+1],如果tmp>a[end]的话就直接结束循环，因为已经找到了自己的位置，就是a[end+1].
3.当循环结束则表明已经找到了tmp的位置，下标为end+1,将tmp赋值给a[end+1]即可。
代码实现

void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){int end = i;int tmp = a[end + 1];while (end >=0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

2.希尔排序

希尔排序( 缩小增量排序 )
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。相当于分组的插入排序。

步骤：
1.将要排列的数据分为几组
2.每一组内进行插入排序。
3.缩小组数，当组数为1时，相当于直接插入排序。

void ShellSort(int* a, int n)
{int gap = 3;for (int i = 0; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}

上面代码为单组的排序，只有一组。

void ShellSort(int* a, int n)
{int gap = 3;for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}

加了循环，将每组都排好序，但是整体没有有序。当gap!=1时，属于预排序。每次循环减小gap的值。说明分组在变，然后在每一组里面继续排序，当gap等于1时，相当于插入排序。

void ShellSort(int* a, int n)
{int gap = 3;while (gap >= 1){gap /= 2;for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}}

上面这种是一组排，会多套一层循环。如果使用下面的代码是一组没排完，就进行排下一组，一组中先把前两个元素排好，在排第二组的前两个元素，当排完每一组的前两个元素，又回到第一组，排第一组的前三个元素，排好前三个元素，接着排第二组的前三个元素，依次类推。

时间复杂度平均：O(N^1.3)
空间复杂度：O(1)

3.选择排序

基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的
数据元素排完 。
步骤：1.定义两个变量maxi,mini分别记录要排序数据的最大值和最小值的下标。初始将·maxi,mini等于起始下标。
2.循环遍历要排序的数据，更新下标，如果有数据大于a[maxi],maxi更新为当前的i;如果有数据小于a[mini],mini更新为当前的i;
3.交换此时最小值和第一个数据的位置，最大值和最后一个数据的位置，已经保证了两个数据到他该有的位置。起始位置下标++，结束位置下标–；
4.然后就要排除已经排好的两个元素，现在maxi与mini起始下标就为第二个元素下标了。
5.循环条件起始位置下标小于结束位置下标。

动画演示：

代码实现：

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int maxi = begin;int mini = begin;for (int i = begin + 1; i <=end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}swap(&a[begin], &a[mini]);swap(&a[end], &a[maxi]);begin++;end--;}}

如果你要排序的数据里面最大的数据不是第一个的话，上面的代码你会觉得是正确的，如果第一个数据是最大的，排序就不对了，到底是为什么呢？我们可以调试调试

修改代码为：

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int maxi = begin;int mini = begin;for (int i = begin + 1; i <=end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}swap(&a[begin], &a[mini]);if (maxi == begin){maxi = mini;}swap(&a[end], &a[maxi]);begin++;end--;}}

直接选择排序的特性总结：
时间复杂度：O(N^2)
空间复杂度：O(1)

4.堆排序

堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

void AdjustDwon(int* a, int n, int root)//向下调整建立大堆。
{int child = root * 2 + 1;while (child < n){if (child+1<n &&a[child] < a[child + 1]){child = child + 1;}if (a[child] > a[root]){swap(&a[child], &a[root]);root = child;child = root * 2 + 1;}else{break;}}}

上图为建立的大堆。

堆排序演示

5.冒泡排序

思路：
左边大于右边交换一趟排下来最大的在右边

代码实现：

void BubbleSort(int* a, int n)
{for (int i = 0; i < n-1; i++){for (int j = 0; j < n - i-1; j++){if (a[j + 1] < a[j]){swap(&a[j], &a[j + 1]);}}}}

时间复杂度：O(N^2)
空间复杂度：O(1)