前段时间也是结束了二叉树的知识梳理（大家想必满脑子都是递归了）
今天也要迈向全新的篇章了——排序。这次就先大概讲解一下排序，然后插入排序和希尔排序的介绍和实现
1.排序的概念和运用
1.1概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减(升序或降序)的排列起来的操作。对于排序算法，稳定性是一个重要的特性。
稳定性：描述了相同键值的元素在排序前后的相对位置是否保持不变，即在原序列中，有r[i]=r[j]，且r[i]在r[j]之前（i<j），而在排序后的序列中，r[i]仍在r[j]之前(次序保持不变)，则称这种排序算法是稳定的；否则称为不稳定的
内部排序：数据元素全部放在内存中的排序
外部排序：数据元素太多，无法一次性放入内存中，因此排序过程需要借助外部存储空间进行处理，根据排序过程的要求不能在内外存之间移动数据的排序
1.2运用
- 邮件和文件整理： 在办公室或个人生活中，整理文件或邮件时会按照日期、主题或重要性排序，这样可以更方便地管理和查找文件
- 成绩、学校排名：我们作为学生那肯定很熟悉了
- 音乐播放列表： 在音乐播放器或流媒体平台上，可以按照歌手、专辑、曲目或流行程度等因素对音乐进行排序，方便用户查找和播放喜欢的音乐
2.常见排序一览
3.直接插入排序
3.1基本思想
直接插入排序：它的基本思想是将待排序序列分为已排序和未排序两部分，然后逐步将未排序部分的元素插入到已排序部分的合适位置，最终完成整个序列的排序
打扑克牌时，我们不就这样吗
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
3.2具体实现
void InsertionSort(int* a, int n)//升序 { for (int i = 0; i <= n - 2; i++) { int end = i;//用来标记，<=end的都已经排好了，该end+1排了 int tmp = a[end + 1];//保存一下，后面可能会被覆盖 while (end >= 0)//用来把比tmp大的向后移，中间就有空位了 { if (a[end] > tmp) { a[end + 1] = a[end];//要是>tmp那就向后移动，也是覆盖发生 } else { break; } end--;//end往前走 } a[end + 1] = tmp;//放到空位， } } int main() { int a[10] = { 2,5,6,1,8,9,10,12,56,73 }; for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } printf("\n"); InsertionSort(a, 10); for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } printf("\n"); return 0; }
3.3过程示图
4.希尔排序
4.1思想、过程和性质
gap为间隔，隔几个间隔取一个元素放在同一个子序列内。
希尔排序：一种插入排序的改进版本，也被称为缩小增量排序。它通过将待排序的数组分割成若干个子序列，分别进行插入排序，然后逐步减小子序列的长度，最终将整个数组排序。当子序列长度到达1时，所有记录就排好序了（gap=1时就是插入排序了）
步骤：
选择一个增量序列（gap），通常为n/2、n/4、n/8…直到增量为1。
根据增量（gap，gap多大就能分几组）将数组分割成若干个子序列，对每个子序列进行插入排序(gap为t，一共n个数据。能分t组：每隔t个就取一个)
逐步减小增量，重复上述步骤，直到增量为1，此时对整个数组进行插入排序
这只是gap=3的过程，gap会继续减小再次经历次过程。直至gap=1是最后一次
希尔排序的特性总结：
希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算
稳定性：不稳定(分组在不同组，导致改变)
4.2代码实现
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> void ShellSort(int* a, int n) { int gap = n; while (gap > 1)//最外层循环用来减小gap { gap = gap / 3 + 1;//保证最后一个gap=1；1或2来除3是0 for (int i = 0; i < n - gap; i++)//第二层循环用来使整个数组以子序列为单位进行插入排序 { int end = i;//需要end最初指向各子序列的头 int tmp = a[end + gap];//储存下一个需要排的 while (end >= 0)//第三次循环是针对这个tmp，看插在哪内进行插入排序（找空位） { if (tmp < a[end]) { a[end + gap] = a[end];//end处的值后移到子序列中的下一个 end-=gap; } else { break; } } a[end + gap] = tmp;//放进空位 } } } int main() { int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 }; printf("排序前："); for (int i = 0; i < sizeof(a) / sizeof(int); i++) { printf("%d ", a[i]); } printf("\n"); ShellSort(a, sizeof(a) / sizeof(int)); printf("排序后："); for (int i = 0; i < sizeof(a) / sizeof(int); i++) { printf("%d ", a[i]); } printf("\n"); return 0; }
结果：
这次排序就先起个头，下次接着带来选择排序的内容，感谢大家支持！！！
