摘要：想快速入门数据结构，推荐订阅作者的初阶数据结构专栏此专栏预计更新顺序表，链表，栈，队列，二叉树，排序算法等等初阶数据结构我们通过语言实现，所以此专栏也可以帮助大家巩固大家的语言知识源代码已上传至我的码云前言非常感
??想快速入门数据结构，推荐订阅作者的初阶数据结构专栏！此专栏预计更新：顺序表，链表，栈，队列，二叉树，排序算法等等
??初阶数据结构我们通过c语言实现，所以此专栏也可以帮助大家巩固大家的c语言知识
??源代码已上传至我的码云
前言
非常感谢各位小伙伴的支持，我们的初阶数据结构系列在经过这篇文章后，也迎来了它的完结！
这个系列我们使用纯c语言实现了一些简单的数据结构，用它们解决了一些简单的问题
当年，可能有的小伙伴会问了：为啥作者没有收录图或者其它的数据结构啊？
别急，作者在下个月开始后，会开一个c++的新坑，不仅会介绍基础语法，还会介绍一些类啊，STL和一些只能使用c++实现的数据结构，感谢各位小伙伴的持续关注哦！
毕竟，c语言还是有局限性的，使用c语言来写会非常麻烦
好！接下来开始我们今天的内容！
我们在生活中，会遇到各种各样的排序
比如我们在淘宝进行网购的时候
我们网购手机，将价格啊，销量啊进行排序，方便我们对商品的筛选
大家应该好奇了，这种排序在背后是咋实现的啊？别担心，今天我帮你们揭开排序神秘的面纱
排序算法按数据交互方式分，可分为以下几种
一种简单的插入算法，基本思想：
把待排序数据关键字插入到一个有序序列中的特定位置
画图求解：
我们从后往前检查，3-6都比2大，当发现1比2小了的时候，将2插入到1的后面
具体操作方法：
我们学过顺序表的插入，知道如果要插入数据的话，最好挪动关键字位置后面的数据，防止数据的覆盖
单趟排序的演示：
将已经排好序的序列的末尾开始，往后面扫描，当发现比待排序关键字小的数据后，挪动后面的数据，将待排序插入到选定数据的后面
动图演示：
代码：
int end = i;//有序序列的末尾 int x = a[end + 1];//待排序 while (end >= 0) { if (a[end] > x) { a[end + 1] = a[end];//挪动数据 end--; } else { break; } } a[end + 1] = x;//插入将其组合为插入排序？
我们可以从前往后遍历待排序数组，将已经遍历的数组看做是有序数组，而后面的数据是我们待排序的数据
动图展示：
代码实现
void InsertSort(int* a, int n){ assert(a); for (int i = 0; i < n - 1; i++) { int end = i; int x = a[end + 1]; while (end >= 0) { if (a[end] > x) { a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = x; }}性能分析：
时间复杂度：O(n2)，最坏情况为逆序，扫描数组需要n次，而挪动数据又需要n次
空间复杂度：O(1)
而在最好情况，复杂度为O(n)，有序数组的情况
而我们可以利用在有序或者接近有序的情况下，插入排序效率较高这一特征，对插入排序进行优化，而这个优化方式就叫希尔排序
希尔排序是对插入排序的优化，此排序算法分为以下两个阶段：
这个算法的重点就是预排序过程，
以下是预排序的思路：
选定一个整数gap，把待排序数组按每gap一步分组进行排序，对每一组的数据进行排序
重复，当gap=1时，就变成了直接插入排序
例如，当gap=5时的分组
我们只需要对9,4；1,8。。。进行排序即可
gap=2时
这样的预处理，我们可以使序列尽量有序，可以将较大的数据尽快挪动在数组末尾
例如，将gap=2进行预排序（单趟）
其实与插入的思想相同，插入是一次挪动1个数据，这里1次挪动gap数据（也就是将gap=2组直接看做一个序列进行插入排序）
代码实现：
int end = i;//将插排的1换成了gap，其它无差别 int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = x;而我们要完成预排序的操作时，可以用插排的思想，遍历数组，对齐进行组间交叉的预排序
我们的操作组是以下的关系
而gap我们可以逐渐减小，作者这里是每次将gap/3，直到gap为1时，进行插入排序
代码实现
void ShellSort(int* a, int n){ assert(a); int gap = n; while (gap > 1) { gap = gap / 3 + 1; for (int i = 0; i < n - gap; i++) { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = x; } }}性能分析：
时间复杂度：O(n1.5)大约，因为希尔排序的时间复杂度不太好算
空间复杂度：O(1)
一个非常好理解的排序
我们可以定义两个指针，寻找最大值和最小值，再与左端和右端进行交换
动图展示：
代码实现：
void SelectSort(int* a, int n){ assert(a); int begin = 0; int end = n - 1; while (begin < end) { int imax = begin; int imin = begin; for (int i = begin; i <= end; i++) { if (a[i] > a[imax]) { imax = i; } if(a[i] < a[imin]) { imin = i; } } Swap(&a[begin], &a[imin]); if (imax == begin) imax = imin;//这里是防止imax被换走，对imax进行修正 Swap(&a[end], &a[imax]); begin++; end--; }}时间复杂度：O(n2)，无论什么情况都是O(n2)
空间复杂度：O(1)
我们在这篇文章中讲到了堆的实现，而堆的重要应用就是排序,点我直达文章
堆排序的步骤：
建大堆，我们可以方便选出每次待排序序列中的最大元素，方便与最后一个元素交换
过程演示：
建好堆后的操作：
代码实现：
void HeapSortDown(int* a, int n){ assert(a); int i = 0; for (i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n , i); }//建堆操作 for (i = n - 1; i > 0; i--) { Swap(&a[0], &a[i]); AdjustDown(a, i, 0); }//调整最大元素}时间复杂度：O(n*logn)，建堆消耗O(n),调整执行树的高度次，也就是(logn)次
空间复杂度：O(1)
冒泡排序是我们在初学c语言时就接触到的一种简单的排序算法
基本思想是：
每次通过两两相邻的元素交换，将最大的元素交换到数组的末尾，就想冒泡一样把最大元素冒在上面
动图演示：
一些优化：
我们可以定义一个标记变量，当我们遍历时没有发生交换操作，（即数组已经有序）则直接跳出循环
void BubbleSort(int* a, int n){ assert(a); int end = n; while (end >= 0) { int flag = 0; for (int i = 0; i < end - 1; i++) { if (a[i] > a[i + 1]) { flag = 1; Swap(&a[i], &a[i + 1]); } } end--; if (!flag) break; }}时间复杂度：O(n2)，但有序情况下复杂度为O(n)
空间复杂度：O(1)
**注意，划重点！**本文最重要的知识点，没有之一
快速排序是一种二叉树结构交换算法，基本思想是：任取一个待排序中的基准值（key）（本文取数组的最左边），通过交换操作，使序列左边的值比基准值小，而右边的值比基准值大，然后左右子列重复过程，直到整个序列有序
基本思想图解
所以，类似于二叉树，快速排序也使用递归实现
其中，交换方式有三种
这个方式是最开始发明快速排序的人提出的
步骤是：
先标记序列的最左边和最右边，从选定key位置相反一端开始遍历，本文也就是右端向左走，右端找到比key小的元素后停止，左边找到比key大的元素后停止，同时停止后交换，直到它们相遇，在相遇位置赋予关键字的值
这样，就能实现我们单趟排序的目的：左比key小右比key大
动图演示
单趟交换的代码：
int Partion1(int* a, int left, int right){ int key = left; while (left < right) { while (left < right && a[right] >= a[key]) { right--; } while (left < right && a[left] <= a[key]) { left++; } Swap(&a[left], &a[right]); } Swap(&a[left], &a[key]); return left;}
