引言：
今天天气还是依然的冷，码字越来越不容易了，本来上次写了一个比较好的引言，但是因为电脑第二天没电，并且我没有保存，现在找不到了，所以今天我们的引言就这样吧！今天给大家介绍一下有关数据结构中的排序的内容，因为来不及一口气把所有的排序学完并且学明白，我们就把这些排序给分开进行讲解。所以今天我们学的是直接插入排序和希尔排序相关的知识分析和代码的实现。
1.排序的概念及其应用
1.1 排序的概念
排序：所谓的排序就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j],并且r[i]在r[j]之前，而在排序后的序列中，r[i]任然在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的
内部排序：数据元素全部在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序的过程的要求不能在内存之间移动数据的排序
1.2 排序的应用（此时就可以去淘宝上截图一下，就是价格的排序之类的）（可以很好的充当一个筛选的作用）
1.3 常见的排序：插入排序（直接插入排序、希尔排序） 选择排序（选择排序、堆排序） 交换排序（冒泡排序、快速排序）归并排序
2.直接插入排序的实现及分析
2.1 基本思想：
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按期关键码值的大小逐个插入到一个已经排好的有序序列中，直到所有的记录插入完为止，然后就得到一个新的有序序列。
2.2 生活中的实例：我们玩扑克牌的时候，就是用了插入排序的思想，如图：
2.3 具体的实现原理：当我们想要插入第i（i>=1）个元素时，前面的arr[0],arr[1],arr[2],……,arr[i-1]已经排好序，此时用arr[i]的排序码值与arr[i-1],arr[i-1],……，的排序码值进行比较，找到合适的位置将arr[i]插入，原来位置上的元素按照顺序向后移动
2.4 具体代码的实现（最详细的注释）
void InsertSort(int* arr, int n)
{
int i = 0;
for (i = 0; i < n - 1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
2.5 直接插入排序的测试
void PrintArr(int* arr, int sz)
{
int i;
for (i = 0; i < sz; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
void TestInsertSort()
{
int arr[] = { 6,3,7,4,10,9,2,1,5,8 };
InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
PrintArr(arr, sizeof(arr) / sizeof(arr[0]));
}
#include
int main()
{
TestInsertSort();
return 0;
}
3.希尔排序的实现及分析
希尔排序又称为缩小增量法。
3.1 希尔排序的基本思想：先选定一个整数，把待排序文件中所有记录分成一个组，所有距离为1的记录在用一个组内，并对每一组的记录进行排序。然后，取，重复上述分组和排序的工作。当到达距离=1时，所有记录在统一组内排好序。
就是一个直接插入排序的优化（但是好像很高级）
此时这个希尔排序进行排序是将排序过程分为了两步
3.1.1.先进行预排序，让数组接近有序
3.1.2.然后再进行直接插入排序
3.2 此时就会涉及到一个叫gap的变量，我们可以对数组中间隔为gap的元素先进行一个预排序，gap由大变小。
特点：gap越大，大的数可以越快的到后面，小的数可以越快的到前面，gap越小，越接近有序，gap=1时就是我的直接插入排序
代码实现：（具体原理就是直接插入排序的原理，重点就是如何理解这个gap）
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 2;
}
int i = 0;
for (i = 0; i < n - gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end = end - gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
Original: https://blog.csdn.net/weixin_74004489/article/details/128425304
Author: 今天还要努力
Title: 数据结构之排序【直接插入排序和希尔排序的实现及分析】
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/805959/
转载文章受原作者版权保护。转载请注明原作者出处！