详解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个月,有诸多错误错误,望多多包涵,谢谢!

 

 

转载请说明出处内容投诉
CSS教程_站长资源网 » 详解C语言的四种排序:冒泡排序、选择排序、插入排序、快速排序

发表评论

欢迎 访客 发表评论

一个令你着迷的主题!

查看演示 官网购买