一. 算法描述
冒泡排序思想:依次比较相邻的数据,将小数据放在前,大数据放在后;即第一趟先比较第1个和第2个数,大数在后,小数在前,再比较第2个数与第3个数,大数在后,小数在前,以此类推则将最大的数”滚动”到最后一个位置;第二趟则将次大的数滚动到倒数第二个位置……第n-1(n为无序数据的个数)趟即能完成排序。
举个例子:5 7 9 3 6 2 8
第一趟: 5 7 9 3 6 2 8 第二趟:5 7 3 6 2 8 9 第三趟:3 5 6 2 7 8 9
5 7 9 3 6 2 8 5 3 7 6 2 8 9 ……..
5 7 3 9 6 2 8 5 3 6 7 2 8 9
5 7 3 6 9 2 8 5 3 6 2 7 8 9
5 7 3 6 2 9 8 5 3 6 2 7 8 9
5 7 3 6 2 8 9
二. 算法实现
#include<stdio.h>/*
* author:Knife
* time:2014.06.12 20:56
*/
void main_bubbleSort1(){
int intArr[] = {,,,,,,,,,};
int n = sizeof(intArr)/sizeof(intArr[]); // 计算整型数组的长度
int i,j,tmp;
//冒泡排序
for(i = ; i < n; i++){
for(j = ; j<n-i-; j++){
if(intArr[j]>intArr[j+]){
tmp = intArr[j+];
intArr[j+] = intArr[j];
intArr[j] = tmp;
}
}
}
//输出
for(i = ; i < n; i++){
printf("%d ",intArr[i]);
}
printf("\n");
}
三. 算法分析
- 平均时间复杂度:O(n^2)
- 空间复杂度:O(1) (用于交换)
- 稳定性:稳定
四. 算法优化
优化思路:还可以对冒泡排序算法进行简单的优化,用一个标记来记录在一趟的比较过程中是否存在交换,如果不存在交换则整个数组已经有序退出排序过程,反之则继续进行下一趟的比较。
#include<stdio.h>void main(){
void DataSwap(int* data1, int* data2);
void BubbleSort(int* pDataArray, int iDataNum); int intArr[] = {,,,,,,,,,};
int n = sizeof(intArr)/sizeof(intArr[]); // 计算整型数组的长度 BubbleSort(intArr, n); //输出
for(int i = ; i < n; i++){
printf("%d ",intArr[i]);
}
printf("\n");
}//交换data1和data2所指向的整形
void DataSwap(int* data1, int* data2)
{
int temp = *data1;
*data1 = *data2;
*data2 = temp;
}/********************************************************
*函数名称:BubbleSort
*参数说明:pDataArray 无序数组;
* iDataNum为无序数据个数
*说明: 冒泡排序
*********************************************************/
void BubbleSort(int* pDataArray, int iDataNum)
{
bool flag = false; //记录是否存在交换
for (int i = ; i < iDataNum - ; i++){ //走iDataNum-1趟
flag = false;
for (int j = ; j < iDataNum - i - ; j++){
if (pDataArray[j] > pDataArray[j + ]){
flag = true;
DataSwap(&pDataArray[j], &pDataArray[j + ]);
}
}
if (!flag){ //上一趟比较中不存在交换,则退出排序
break;
}
}
}
参考资料
[1] http://blog.csdn.net/cjf_iceking/article/details/7911027