详解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;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 6
int 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 6
int 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 6
int 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--;
			}
			else
				break;
		}
		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 10
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均可
}
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个月，有诸多错误错误，望多多包涵，谢谢！