冒泡排序算法及其优化

冒泡排序

1、介绍：

冒泡排序和选择排序的思想是蛮力法，冒泡，顾名思义，每次选择后面一个元素（最大或者最小）冒上来，从而得到一个有序的序列。比如对于序列：10、8、5、7、3、1的冒泡第一趟演示图示如图所示

可见第一趟过后做大元素10已经沉底，第二趟就对另外的8、5、7、3、1进行上述同样的比较冒泡，会使得最大元素8沉底，...... ，最终可得到一个有序序列。

2、C语言实现

#include <stdio.h>

void bubbleSort(); //声明函数

int arr[10] = {10,6,4,9,7,26,3,1,11,2};

#define n 10  //宏定义需要排序的序列元素个数

int main()
{
    bubbleSort();  //调用函数
    return 0;
}
//以下是冒泡排序算法
void bubbleSort()
{
    int count = 0; //记录进行比较的次数，考量算法的复杂度
    int i,j,k;
    for(i=0;i<n;i++)  //第一层循环控制循环的趟数
    {
        for(j=0;j<n-1-i;j++) //第二层循环在每趟中进行“冒泡”比较
        {
            count++;   //count+1
            if(arr[j]>arr[j+1]) //加入前一个比后一个大，则交换两个数的位置
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }

    for(k=0;k<n;k++) //打印排序后的序列
    {
        printf("%4d",arr[k]);
    }

    printf("\nTotal count is %d",count); //打印总共比较的次数

}

程序的运行结果：

2-2、Java代码实现

	/**
	 * 冒泡排序
	 *@author DR
	 * @param args
	 * @return
	 *2014年3月
	 */
	public int[] bubbleSort(int...args){ //这里使用JDK提供的可变参数作可变数组
		for(int i=0;i<args.length-1;i++){  
			for(int j=args.length-1;j>i;j--){  //这里从右向左扫描
				if(args[j]<args[j-1]){
					int temp = args[j];
					args[j] = args[j-1];
					args[j-1] = temp;
				}
			}
		}
		return args;
	}

注：程序中有两个for循环，在args[i]左边的元素是已经沉底的，排序好了的元素；j作为一个扫描指针，从右向左扫描，如果j-1位置的大于j位置的元素，则交换它们，直到把最小的那个元素沉底到i+1位置。

3、冒泡排序算法的优化

对于上面的序列我们发现，含有10个元素的序列需要45次比较（第一趟9次，第二趟8次，第三趟7次，....... ，第九趟1次），那么真的需要45次吗？对于下面的这种序列{1,2,4,5,8,9,10,14,15,13}，使用上面的算法也是45次，但观察发现该序列大部分是有序的，第一趟将15沉底放置最后，得到{1,2,4,5,8,9,10,14,13,15}，第二趟将14沉底放置最后，得到{1,2,4,5,8,9,10,13,14,15}，从第三趟到最后一趟都无需再移动，所以那些比较都是徒劳的，因此，我们对上述算法进行如下优化，减少算法的比较次数。优化的方法就是加一个标志位，记录本趟比较是否发生交换，下一趟根据这个标志位，若上一次没有交换，则本趟比较无需进行。

4、冒泡排序算法优化C语言实现

#include <stdio.h>

void bubbleSort();

int arr[] = {1,2,4,5,8,9,10,14,15,13};
int i,j,k;

int main()
{
    bubbleSort();
    return 0;
}

void bubbleSort()
{
    int flag = 1;  //添加控制标志位，记录上一趟是否发生交换
    int count = 0;
    for(i=0;i<10&&flag;i++) //指针i控制次数
    {
        for(j=0;j<10-1-i;j++) //j从头开始，将最大的元素沉底到最后
        {
            flag = 0;
            count++;
            if(arr[j]>arr[j+1])
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                flag = 1;
            }
        }
    }

    for(k=0;k<10;k++)
    {
        printf("%4d",arr[k]);
    }

    printf("\ntotal count is %d",count);
}

程序运行结果：只需比较24次（第一趟9次，第二趟8次，第三趟7次）

4-2、冒泡排序算法优化Java代码实现

	/**
	 * 冒泡排序的优化算法
	 *@author DR
	 * @param args
	 * @return
	 *2014年3月

	 */
	public int[] bubbleSort2(int...args){
		boolean flag = true;   //是否交换标志位
		for(int i=0;i<args.length-1&&flag;i++){
			flag = false;
			for(int j=args.length-1;j>i;j--){
				if(args[j]<args[j-1]){
					int temp = args[j];
					args[j] = args[j-1];
					args[j-1] = temp;
					flag = true;   //发生交换则让标志位为真
				}
			}
		}
		return args;
	}

5、总结

总的来说，冒泡排序是最基本简单排序的一种，是一种基于蛮力思想的排序，其时间复杂度为o(n²)。