详解C语言的四种排序：冒泡排序、选择排序、插入排序、快速排序
时间：2024-04-01 14:10:44 来源：网络cs 作者：欧阳逸 栏目：卖家故事 阅读：
目录
前言
一、冒泡排序
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;i<=5;i++) for(int j=0;j<=6-i-1;j++) if(a[j]>a[j+1]) { a[j]与a[j+1]调换位置 }这里为了让思路更明确：i就是指第i轮，但数组是从a[0]开始，故循环j的上街是6-1-i。
2.代码实现
所以有了上面的思路，冒泡排序的实现就非常简单了，直接看代码
#include<stdio.h>#define N 6int main(){int a[N]={0};for (int i = 0; i < N; i++){scanf("%d", &a[i]);}int temp = 0;for(int i=1;i<=N-1;i++)for (int j = 0; j <= N - i-1; j++){if (a[j] > a[j + 1]){temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}for (int i = 0; i < N; i++)printf("%d ", a[i]);}由上可以知道，冒泡排序其实是一种非常慢的算法，它的最坏理论时间复杂度是O(n²) 。
3.应用
冒泡排序实现起来最简单，但因为其复杂度，通常只适用于数据量很小的排序场景。
冒泡排序的例题实在是太多，基本所有的比较简单的排序，在不考虑时间的条件下，都可以使用冒泡排序（甚至都可以使用上面写的代码，只需要把N改一下），故不在赘述。
二、选择排序
1.排序原理
选择排序的实质其实还是冒泡排序，它与冒泡排序的最显著区别是：选择排序大多数时间都在比较，而很少排序。
它的整体思路在于：第一次从待排序的中数据元素选出最小的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
我们还是假定有6个数，这6个数在数组a[ ]之中，选择排序为了便利我们直接将这6个数假设为：9、6、2、4、7、1.
第一轮：假设首元素9为最小的元素，然后用9去比较剩余的（6-1）数，一旦有比9小的就记住这个数，然后拿这个数继续比较，目的是寻找到最小的那个数，最后交换9与最小数的位置。第一轮排序完成得到1、6、2、4、7、9
第二轮：类似的，1已经在正确的位置了，则拿二号位的6作为最小元素，然后拿6去比较剩余的（（6-1）-1），个数，一旦有比6小的就记住这个数，然后拿这个数继续比较，找到最小的那个数，最后与6交换位置。第二轮排序完成得到1、2、6、4、7、9.
余轮类推，在最坏的情况下我么需要经过5轮排序
经过5轮我们就把最小的、第二小的、第三小的……放在了正确的位置
我们也可以根据这个思路写一个简短的核心代码
for (i = 0; i < N- 1; i++) { min = i;//因为是数组，只需要记录下标的值 for (j = i + 1; j < N; j++) { if (a[j] < a[min])//不断找寻最小的数 { min = j; } } { if(i!=min) {交换a[i]和a[min]的位置} }2.代码实现
同理，我们也能够很快地写出代码
#include<stdio.h>#define N 6int main(){int a[N]={0};for (int i = 0; i < N; i++){scanf("%d", &a[i]);} int i, j; int min = 0; int temp = 0; for (i = 0; i < N- 1; i++) { min = i;//因为是数组，只需要记录下标的值 for (j = i + 1; j < N; j++) { if (a[j] < a[min]) { min = j;//记录交换的元素下标值 } } if (i != min) { temp = a[i]; a[i] = a[min]; a[min] = temp; } }for (int i = 0; i < N; i++)printf("%d ", a[i]);}通过代码我们也可知道选择排序和冒泡排序的实质是一样的
需要注意的是，选择排序是不稳定的排序。关于稳定与否，用一句话来说：排序前后，相同大小的数字的相对顺序不变则是稳定的。
举个例子，6个数：arr[ ]={5、9、3、5、8、2}.这个数组中我们把第一个5记为5a，第二个5记为5b，即arr[ ]={5a、9、3、5b、8、2}。经过第一轮选择排序，数组顺序变成了{2、9、3、5b、8、5a}这就是两个5的相对顺序发生了改变。所以称选择排序是不稳定的。
3.应用
虽然选择排序与冒泡排序本质相同，且时间复杂度依旧较高（与冒泡排序一致为O(n²)），但是数据量大的时候，他的效率明显优于冒泡，而且数据移动是非常耗时的，选择排序移动次数少。所以选择排序可以适用于大多数场合。
三、插入排序
1.排序原理
依照笔者的观点：插入排序是我们现实生活中所用到的最常见的排序，也是最符合人思维的排序
它的整体思路为：将这些数分为有序区和无序区。（开始时有序区只有一个数，即数组最开头的那个数，无序区是后面的待排序的数）。前面n-1个数已经是排好顺序的（即前面的n个数都在有序区），现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。实现方法为将这第n个数从有序区序列从后往前比较，直到找到这第n个数的正确位置（即arr[i]<arr[n]<arr[i+1]）。
我们还是假定有6个数，直接将这6个数假设为：9、6、2、4、7、1.
第0轮：9位于有序区，6、2、4、7、1位于无序区
第1轮：取6，把6暂存起来，扫描比较有序区，有序区只有9，且9>6，9往前移，6已经到了有序区的边缘即在肯定正确位置。现在，有序区：6、9
无序区：2、4、7、1.
第2轮：取2，把2暂存起来，扫描比较有序区，2>9,9往前移，2>6，6又往前移，2放在最边缘，即正确位置。现在，有序区：2、6、9无序区：4、7、1.
余轮类推：下面的动图也可清楚的表达此过程。据此我们也易得出，插入排序的理论最坏时间复杂都依然为O(n²)。
2.代码实现
完全按照思路，很轻易的可以写出代码
#include<stdio.h>#define N 6int main(){int a[N]={0};for (int i = 0; i < N; i++){scanf("%d", &a[i]);} int i, j; int youxu = 0; int temp = 0;for (i = 0; i < N - 1; i++){youxu = i;//有序区的最后一个数的下标temp = a[youxu + 1];//暂存无序区的最开头一个数while (youxu >= 0){if (temp < a[youxu]){a[youxu + 1] = a[youxu];youxu--;}elsebreak;}a[youxu+1] = temp;}for (int i = 0; i < N; i++)printf("%d ", a[i]);}写完代码，我们来想想插入排序是稳定的吗
还是相同的例子，假设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 < N; i++)scanf_s("%d", &a[i]);quicksort(a, 0, N - 1);for (int i = 0; i < N; i++)printf_s("%d ", a[i]);return 0;}接着是控制递归框架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&&left<right)left++;if (right > left)//未碰面时就交换数值{int temp = a[right];a[right] = a[left];a[left] = temp;}}//交换基准数和相遇时所指的数a[start] = a[right];//这里写right或者left均可a[right] = stand;//这里写right或者left均可return right;//返回right或left均可}以上整个快速排列程序的三大板块就结束，下面是完整代码
#include<stdio.h>#define N 10int 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&&left<right)left++;if (right > left)//未碰面时就交换数值{int temp = a[right];a[right] = a[left];a[left] = temp;}}//交换基准数和相遇时所指的数a[start] = a[right];//这里写right或者left均可a[right] = stand;//这里写right或者left均可return right;//返回right或left均可}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);}int main(){int a[N] = { 0 };for (int i = 0; i < N; i++)scanf_s("%d", &a[i]);quicksort(a, 0, N - 1);for (int i = 0; i < N; i++)printf_s("%d ", a[i]);return 0;}通过代码，我们再来想想为什么开头会说“扫描一定要先从右往左，再从左往右”。
其原因就在于我们的基准数取的是最左边的数，最后的目的是使基准数左边的数全部比基准数小，回想我们的最后一步，我们交换了最左边的值（基准数值）和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个月，有诸多错误错误，望多多包涵，谢谢！
阅读本书更多章节>>>>
本文链接：https://www.kjpai.cn/gushi/2024-04-01/152057.html，文章来源：网络cs，作者：欧阳逸，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！