【数据结构】插入排序，希尔排序，选择排序，堆排序，冒泡排序
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;
}
}
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
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)