详解C语言的四种排序：冒泡排序、选择排序、插入排序、快速排序
目录
前言
一、冒泡排序
1.排序原理与思路
2.代码实现
3.应用
二、选择排序
1.排序原理
2.代码实现
3.应用
三、插入排序
1.排序原理
2.代码实现
3.应用
四、快速排序
1.排序原理
2.代码实现
3.应用
总结
前言
无论是处理数据还是单纯的做题，排序都是一个重要的处理点，C语言中有三种经典的简单排序：选择排序、冒泡排序、插入排序以及快速排序。今天笔者就来总结一下这四种排序，并适当适当分析其应用是的特点
一、冒泡排序
1.排序原理与思路
冒泡排序是经典的一维数组的应用，它的整体思路在于：相邻两个数相比较，将大的数放再后面小的数放在前面。
为了方便讲解，我们假设有6个数，这6个数在数组a[ ]中，我们要把它们从小到大排序，则排序一共分为（6-1）=5轮：
第一轮：6个数，两两对比，每当a[j]>a[j+1]（这里j从0一直到4）则交换位置，一共循环5次，注意，第一轮的交换结果为：我们把最大的那个数移到了整个数组的最右边，即已经到了正确的位置。
第二轮：因为最大的那个数已经在正确的位置了，故我们只需要排前五个数。我们基本重复第一轮的做法，5个数，两两对比，每当a[j]>a[j+1]（这里j从0一直到3）则交换位置，一共循环4次.和第一轮一致，我们把第二大的数移到了正确的位置
余次类推，我们第i轮，只需要排列6-i个数即可。
经过五轮我们依次把最大的、第二大的、第三大的……的数放再了正确的位置，就像下面的动图一样
这里，我们就可以按照思路，写一个小的主循环代码，就按照有6个数来排序
for(int i=1;i9,9往前移，2>6，6又往前移，2放在最边缘，即正确位置。现在，有序区：2、6、9无序区：4、7、1.余轮类推：下面的动图也可清楚的表达此过程。据此我们也易得出，插入排序的理论最坏时间复杂都依然为O(n²)。
2.代码实现
完全按照思路，很轻易的可以写出代码
#include #define N 6 int main() { int a[N]={0}; for (int i = 0; i = 0) { if (temp写完代码，我们来想想插入排序是稳定的吗
还是相同的例子，假设arr[ ]={5a、9、3、5b、8、2}。当把5b拿出来排序时，此时的arr'=[3、5a、9、5b、8、3].即有序区：3、5a、9。无序区：5b、8、3。显然，拿5b去比较是，是无法越过5a的，即插入排序是稳定的。
3.应用
插入排序是最简单的排序方法，虽然其最坏时间复杂度也为O(n²)，但是对于少量元素的排序，它是一个有效的算法。特别是在当已有有序的一组数，相对外来的其他数进行排列时，插入排序尤其适用。
四、快速排序
1.排序原理
快速排序是笔者认为，这几种中最难以理解，实现难度也较高的一种排序。快速排序的实质是对冒泡排序的改良。
快速排序可以说是递归的经典应用。
它的主要思路为：
1）设定一个分界值，将大于等于分界值的数集中在该分解值的右边，小于分解值的数集中在左边。
2）然后仿照第一步，仅对于左右部分独立排序，重复1）的步骤，对于左侧的数组数据，又取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的部分数据也做类似处理。
3）不停重复上述的过程。已经可以看出，这显然是一个递归的定义
我们还是假定有6个数，直接将这6个数假设为：5、6、2、4、7、1.
通常为了方便，我们会直接取第一个数为基准数。
现在问题来了：在初始状态下，数字5在序列的第1位。我们的目标是将9放到某个位置（把这个位置记为mid），该如何去找到这个mid且使得mid左边小于等于5，右边都大于等于5呢？
快速排序的处理办法是，分别从两端开始扫描，先从右往左找到第一个小于5的数，再从左往右找到第一个大于5的数（先从右往左，再从左往右。这一点很重要，我们接下来讲解）。
让我们借助图来理解
5，为基准数；我们借助标记left，和right充当‘探路人’。
最开始left指向最左边的5，right指向最右边的1.
第一大轮：
第1轮：从right开始’探路‘，从左至右（right--）找到第一个小于5的数，并停下，这里很特殊，right的初始所指就是目标数。接着，left开始‘探路’，从右至左（left++）找到第一个大于5的数，即6.此时变为下图
然后交换此时的left对应的值和right对应的值
第二轮：重新开始。又从right现在位置开始’探路‘，从左至右（right--）找到第一个小于5的数，并停下，这次right找到了4。接着，left开始‘探路’，从右至左（left++）找到第一个大于5的数，left这次的目标数是7.
但是遗憾的是在4处left与已经停在那里的right碰头了。我们可以理解为，两者碰头则整条路已经被‘探明’了,已经不需要再‘探路’，即整个搜索过程已结束。即下图
此时交换（right，left）所指数的值和基准数的值。
得到了
此时我们的第一大轮排列就完成，我们已经达成了目标即5左边的数都小于等于5，右边都大于等于5。
现在我们只需要将5左边的部分：4、1、2和其右边部分7、6仿照第一大轮再次快速排列。直到区间仅剩下一个元素为止。
2.代码实现
了解了上面的思路，我们来写代码。
代码分为三个部分：main()、quicksort()来进行快排递归、support()确定基准数的位置‘mid’
首先是把最简单的main()部分写出来
int main() { int a[N] = { 0 }; for (int i = 0; i接着是控制递归框架quicksort()
void quicksort(int* a, int left, int right) { int mid; if (left >= right) //只有一个元素递归结束 return; mid = support(a, left, right); quicksort(a, left, mid - 1); quicksort(a, mid + 1, right); }最后只需要按照上面的分析把support()写出来即可
int support(int* a, int left, int right) { int stand = a[left];//记录基准数 int start = left;//基准数的下标 while (left != right)//循环退出条件left和right碰面 { while (a[right] >= stand&&right>left)//始终要判断right>left的条件以防未找到目标数就碰面 right--; while (a[left] = stand&&right>left)//始终要判断right>left的条件以防未找到目标数就碰面 right--; while (a[left] = right) return; mid = support(a, left, right); quicksort(a, left, mid - 1); quicksort(a, mid + 1, right); } int main() { int a[N] = { 0 }; for (int i = 0; i通过代码，我们再来想想为什么开头会说“扫描一定要先从右往左，再从左往右”。
其原因就在于我们的基准数取的是最左边的数，最后的目的是使基准数左边的数全部比基准数小，回想我们的最后一步，我们交换了最左边的值（基准数值）和left与right相遇所指的值。为了满足目的，最后left与right共同所指的值必须比基准数要小。
而因为right即右边的‘探路者’只会在比基准数小的地方停下（当基准数是最小值时会在初位置停下），每次循环都从右边开始，这就确保了最后left与right共同所指的值必须比基准数要小。
3.应用
由上可知，
(1)若选择的基准值是数据中最大（小）的数，但是要排成降序（升序），快排的性能最低，时间复杂度为O(n²)
(2)理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过ln(n)趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为每次则时间复杂度为O(nln(n))
(3)可以证明，快速排序的平均时间复杂度也是O(nln(n))。因此，该排序方法被认为是目前最好的一种内部排序方法。应用的场景颇多
总结
以上即是c语言中常见最基础的四种排序方法的总结，希望对读者有所帮助
大一新生，才学c语言约2个月，有诸多错误错误，望多多包涵，谢谢！
