1.冒泡排序
冒泡排序将一个列表中的两个元素进行比较,并将最小的元素交换到顶部。两个元素中较小的会冒到顶部,而较大的会沉到底部,该过程将被重复执行,直到所有元素都被排序。
冒泡排序示意图
以如图所示的冒泡排序为例,每次比较相邻的两个值,值小的交换到前面,每轮结束后值最大的数交换到了最后。第一轮需要比较4次;第二轮需要比较3次;第三轮需要比较2次;第四轮需要比较1次。
那么如何用二重循环将5个数排序呢?5个数存放在一维数组中,外层循环控制比较多少轮,循环变量i;内层控制每轮比较多少次,循环变量就,如下图所示:
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <stdio.h> #define NUM 5 void arrsort( int [], int ); void arrout( int [], int ); main(){ int a[NUM]={16,25,9,90,23}; arrout(a,NUM); //输出a数组中原始数据 arrsort(a,NUM); //对a数组中的数进行排序 arrout(a,NUM); //输出排序后a数组中的数据 } void arrsort( int a[], int n){ for ( int i=0;i<n-1;i++){ for ( int j=0;j<n-1-i;j++){ if (a[j]>a[j+1]){ int temp =a[j+1]; a[j+1] = a[j]; a[j] = temp; } } } } void arrout( int a[], int n){ int i; for (i=0;i<n;i++){ printf ( "%3d" ,a[i]); } printf ( "\n" ); } |
输出结果为:
2.选择排序
在介绍选择排序法之前,凭介绍一种把最小的数放在第一个位置上的算法,当然也可以用前面所讲的冒泡排序法,现在我们改用一种新的算法: 其指导思想是先并不急于调换位置,先从a[0]开始逐个检查,看哪个数最小,就记下该数所在的位置p,等一躺扫描完毕,再把a[p]和a[0]对调,这时a[0] a[9]最小的数据就换到了最前面的位置。算法的步骤如下。
(1)先假设a[0]的数最小,记下此时的位置p。
(2)依次把a[p]和a[i](从2变化到9)进行比较,每次比较时,若a[j]的数比a[p]中的数小,则把i的值赋给p,使p总是指向当前所扫描过的最小数的位置,也就是说a[p]总是等于所有扫描过的数中最小的那个数。在依次一一比较后,p就指向 10个数中 最小的数所在位置,即a[p]就是10 个数中最小的那个数。
(3)把a[p]和a[0]的数对调,那么最小的数就在a[0]中了,也就是在最前面了。
如果现在重复此算法,但每重复一次, 进行比较的数列范围就向后移动一个位置,即第二遍比较时范围就从第2个数一直到第 n个数,在此范围内找最小的数的位置p,然后把a[p]与a[2]对调,这样从第2个数开始到第n个数中,最小数就在a[2]中了,第三遍就从第个数到第n 个数中去找最小的数,再把a[p]与a[3]对调..此过程重复n-1次后,就把a组中n个数按从小到大的顺序排好了。这种排序的方法就是选择排序法。
下面我们定义一个临时变量temp代替a[p],进行排序。
选择排序修改为:从键盘输入的十个整数按升序排列输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <stdio.h> void main(){ int i,j,k; int a[10]; for (k=0;k<10;k++){ scanf ( "%d" ,&a[k]); } for (i=0;i<9;i++){ for (j=i+1;j<10;j++){ if (a[i]>a[j]){ int temp = a[j]; a[j] = a[i]; a[i] = temp; } } } for (i=0;i<10;i++){ printf ( "%d " ,a[i]); } } |
区别
1.冒泡排序是比较相邻位置的两个数,而选择排序是按顺序比较,找最大值或者最小值;
2.冒泡排序每一轮比较后,位置不对都需要换位置,选择排序每一轮比较都只需要换一次位置;
3.冒泡排序是通过数去找位置,选择排序是给定位置去找数;
冒泡排序优缺点
1.优点:比较简单,空间复杂度较低,是稳定的;
2.缺点:时间复杂度太高,效率慢;
选择排序优缺点
1.优点:一轮比较只需要换一次位置;
2.缺点:效率慢,不稳定(举个例子5,8,5,2,9 我们知道第一遍选择第一个元素5会和2交换,那么原序列中2个5的相对位置前后顺序就破坏了)。
总结
到此这篇关于c语言冒泡排序和选择排序使用的文章就介绍到这了,更多相关c语言冒泡排序和选择排序内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!
原文链接:https://blog.csdn.net/lbqlzch/article/details/84754826