冒泡排序思想:依次比较相邻的数据,将小数据放在前,大数据放在后;即第一趟先比较第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[] = {8,3,6,4,2,9,5,4,1,7}; int n = sizeof(intArr)/sizeof(intArr[0]); // 计算整型数组的长度 int i,j,tmp; //冒泡排序 for(i = 0; i < n; i++){ for(j = 0; j<n-i-1; j++){ if(intArr[j]>intArr[j+1]){ tmp = intArr[j+1]; intArr[j+1] = intArr[j]; intArr[j] = tmp; } } } //输出 for(i = 0; i < n; i++){ printf("%d ",intArr[i]); } printf("\n"); }
优化思路:还可以对冒泡排序算法进行简单的优化,用一个标记来记录在一趟的比较过程中是否存在交换,如果不存在交换则整个数组已经有序退出排序过程,反之则继续进行下一趟的比较。
#include<stdio.h> void main(){ void DataSwap(int* data1, int* data2); void BubbleSort(int* pDataArray, int iDataNum); int intArr[] = {8,3,6,4,2,9,5,4,1,7}; int n = sizeof(intArr)/sizeof(intArr[0]); // 计算整型数组的长度 BubbleSort(intArr, n); //输出 for(int i = 0; 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 = 0; i < iDataNum - 1; i++){ //走iDataNum-1趟 flag = false; for (int j = 0; j < iDataNum - i - 1; j++){ if (pDataArray[j] > pDataArray[j + 1]){ flag = true; DataSwap(&pDataArray[j], &pDataArray[j + 1]); } } if (!flag){ //上一趟比较中不存在交换,则退出排序 break; } } }
[1] http://blog.csdn.net/cjf_iceking/article/details/7911027
【Algorithm】冒泡排序,布布扣,bubuko.com
原文:http://www.cnblogs.com/ningvsban/p/3784735.html