选择排序与冒泡排序

---

  本文将介绍选择与冒泡两种排序方法，并对这两种排序方法进行比较。

  在此之前，我们讨论一下为什么需要进行排序。举个例子： 在一副未拆封的

扑克牌中找到黑桃A与在打完斗地主的一堆牌中找到黑桃A，哪个更简单是显而易

见的。在有序的牌组中我们都知道黑桃A是第一张牌；而在无序的牌组中，我们可

能要找（1~n-1）次才能确定哪张是黑桃A。所以在此例中，我们能看出排序可以

提高查找的效率。

下面来分别介绍两种排序方法

冒泡排序

  首先定义一组数组a[5]：

a[1]	a[2]	a[3]	a[4]	a[5]
98	95	85	93	88

可以看出数组无序，下面我们用冒泡排序对其升序排序，冒泡排序的思路是：针对数组
一端为起点的一对数组元素进行比较，若为逆序，则两者互换（冒泡一次）。再到下一
对数组元素进行比较，数组中从第一对至最后一对数组元素的冒泡比较为一遍循环，n个
数组元素的数组中最多循环（n-1）遍，数组即成有序数组。
  下面对此实例进行冒泡排序：

数组元素	原始数组	第一遍	第二遍	第三遍	第四遍
a[1]	98	85	85	85	85
a[2]	95	98	88	88	88
a[3]	85	95	98	93	93
a[4]	93	88	95	98	95
a[5]	88	93	93	95	98

(比较方向为从右往左）

代码实现

#include<stdio.h>
int main()
{int a[5],i,j,t;a[1]=98;a[2]=95;a[3]=85;a[4]=93;a[5]=88;for(i=1; i<=4; i++){//排序加工的遍数for(j=5; j>=i+1; j--){//比较的方向if(a[j]<a[j-1]){//每一遍排序中的元素间比较t=a[j];a[j]=a[j-1];a[j-1]=t;}}
return 0;
}

让i从1到n-1循环
让j从n到i+1循环
若a(j)与左边相邻数据逆序，则两者互换（冒泡一次）

选择排序

  依然是上述数组a[5]，对数组升序排序。

a[1]	a[2]	a[3]	a[4]	a[5]
98	95	85	93	88

  选择排序的思路（升序）是：数组从第1项元素开始处理，设变量k用来保存第i位置
上最终需放置元素的下标。把第i（1~（n-1））项元素作为最小值（暂时的），然后把第
i项元素与第j（i+1）至n项元素进行比较，每当发现逆序元素，则刷新k=j，直至与第n项元
素比较完成后，排序中的一遍循环就完成了。此时比较下标k与i的值是否相等，若不相等则
交换第i项与第k项的值；若相等则不变。然后开始下一遍循环直至排序结束。
实例分析：

数组元素	原始数组	第一遍	第二遍	第三遍	第四遍
a[1]	98	85	85	85	85
a[2]	95	95	88	88	88
a[3]	85	98	98	93	93
a[4]	93	93	93	98	95
a[5]	88	88	95	95	98

代码实现

#include<stdio.h>
int main()
{int a[5];a[1]=98;a[2]=95;a[3]=85;a[4]=93;a[5]=88;int i,j,k,t;for(i=1; i<=4; i++){//让i从1到n-1循环k=i;//k用来保存第i位置上最终需放置元素的下标for(j=i+1; j<=5; j++){//比较第i+1到第n个数if(a[j]<a[k]){k=j;//把j值保存到k中（若有更小值，则更新k）}}if(i!=k){t=a[i];a[i]=a[k];a[k]=t;//若最小值不在前面，则交换}}return 0;} 

两个排序方法的比较

  我们了解了两种排序方法后，再对他们进行比较：
冒泡排序：

数组元素	原始数组	第一遍	第二遍	第三遍	第四遍
a[1]	98	85	85	85	85
a[2]	95	98	88	88	88
a[3]	85	95	98	93	93
a[4]	93	88	95	98	95
a[5]	88	93	93	95	98
	比较次数	4	3	2	1
	交换次数	3	2	2	1

选择排序

数组元素	原始数组	第一遍	第二遍	第三遍	第四遍
a[1]	98	85	85	85	85
a[2]	95	95	88	88	88
a[3]	85	98	98	93	93
a[4]	93	93	93	98	95
a[5]	88	88	95	95	98
	比较次数	4	3	2	1
	交换次数	1	1	1	1

  可以看出，选择排序相较于冒泡排序，节省了交换次数，效率更高。