声明:编译环境为VS2017 语言:C language
思路分析: 经典的bubble sort(冒泡排序)原理类似于气泡上升过程,到自身的密度小于上一层介质则上升,排序同理。 以数组{5,4,3,2,1}为例: 第一轮: 由于5大于4,则5右移一位,5大于3,则继续右移,5>2右移一位,5>1右移一位,最终数组变为{4,3,2,1,5},比较次数为4 第二轮: 由于4大于3,则4右移一位,4大于2,则继续右移,5>1右移一位,4<5,停止右移,最终数组变为{3,2,1,4,5},比较次数为4 ........ 经过第4轮数组最终变为{1,2,3,4,5}。 由上可以总结出,对一个具有n个元素的数组进行排序,需要进行(n-1)轮(n-1)次比较,复杂度为(n-1)的平方。 代码实现: 编写了一个头文件和.c文件,在.c文件中调用头文件中的sort()函数即可对任意个元素数目的数组的元素进行排序。
#pragma once
#IFndef _SORT_H_
#define _SORT_H_
void sort(int *array,int length)
{
for (int j = 0; j < length - 1; j++)
{
for (int i = 0; i < length - 1; i++)
{
int temp = 0;
if (array[i] > array[i + 1])
{
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
#endif // !_SORT_H_
sort()函数的传入参数为数组地址和数组元素数目,为了实现对含有任意元素数目的数组进行排序,主函数中调用sizeof()函数计算元素数目。
#include<stdio.h>
#include"sort.h"
void main()
{
int array[] = { 5,8,9,4,2,4,6,4,3,2,1 };
int m=sizeof(array)/sizeof(int);
printf("元素数目为:%d \n",m);
sort(array,m);
printf("The sorted number sequence is:\n");
for (int n = 0; n < m; n++)
{
printf("%d", array[n]);
printf("\t"); //空格一次
}
return 0;
}
运行结果
上述代码没有问题,但是如果数组是类似{1,2,3,5,4}这样的类型就多进行3x4次排序,为了解决这个问题,对冒泡排序法进行进一步优化,将在冒泡排序法三部曲の二、冒泡排序优化中解决这个问题。