今天讲一下最基本的排序方法——冒泡排序。
基本思想:每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来。
例如我们需要将一组数据1 67 87 22 0,由小到大排列。即:越大的越往后。
首先,将第一位的1 和 67比较,发现67 比1 大,所以不用交换,之后在比较67 和 87作比较,与前面同理,因为大的刚好在后面,所以不用交换。在将87 和 22比较,发现后一位小于前一位,所以将它俩交换,交换后的顺序是:1 67 22 87 0。在进行最后一次比较87 和 0,0 比 87 小,故交换得:1 67 22 0 87。
所以经过4次比较后,我们将最大的放在了最后了。每将一个数归位我们将其称为“一趟”。
我们再试试将第二大的放在87前面,重复之前的步骤,首先比较1 和 67,不用交换,比较 67 和 22,交换得:1 22 67 0 87。比较67 和 0,交换得:1 22 0 67 87。
我们比较一下第一趟和第二趟,发现了第二趟比第一趟少了一次比较,很明显是因为第一趟已经将最大的放在了最后面,所以第二趟会少一次比较,以此类推,第三趟比第二趟少一次……
总结:如果有 n 个数进行排序, 只需将 n-1 个数归位,也就是要进行 n-1 趟操作。而“每一趟”都需要从第一位开始进行相邻两个数的比较,若前一位大于后一位,完成交换即可,如无需交换,进行下次比较,一直重复此操作,直到第 n-1 次,此时该 n 个数已经完成排序。
ps:我只是以从小到大为例,当然冒泡是可以从大到小排序的,类比一下即可。
图解:
C语言代码:
#include <stdio.h>
int main(void)
{
int a[100];
int i, j, t, n;
scanf("%d", &n); //输入一个数n,表示待排序数的个数
for (i = 0; i < n; i++) //读入待排序的n个数
{
scanf("%d", &a[i]);
}
/* 排序核心 */
for (i = 0; i < n; i++)
{
for (j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
for (i = 0; i < n; i++) //输出结果
{
printf("%d ", a[i]);
}
return 0;
}