算法研究系列-冒泡排序

算法研究系列---冒泡排序

为了毕业面试需要，计划好好的研究一遍算法，以博客的形式记录下来，同时也为了加深自己的理解.

今天要记录的是：冒泡排序

?

?

冒泡排序是一种典型的交换排序算法.同时也是几大排序算法中比较简单的一个.

?

算法思想：通过无序区中相邻记录关键字间的比较和位置的交换，，是关键字较小的记录如同气泡一样上浮，整个算法从记录的最下面开始，对每两个相邻的关键字进行比较，并将关键字小的记录置换到关键字较大的记录之上，是的一趟排序之后，关键字最小的记录上浮到了记录的最上端。以此类推，每次比较都会将本次比较范围的记录中最小的记录置换到最上端，这样当最后一趟完成时，所有记录就都是有序的了...

?

java代码：

?

public class BubbleSort {/** * @param args */public static void main(String[] args) {int[] a = new int[]{7,5,3,4,6,1,10,9,8,2}; a = bubbleSort(a, 10);for(int i = 0; i<10; i++) {System.out.println(a[i]);}}public static int[] bubbleSort(int[]a, int n) {int i, j;int change = 0; int tmp=-1;for(i=0; i<n-1; i++) { change= 0; for(j=n-1; j>i; j--) { if(a[j] < a[j-1]) {tmp = a[j-1];a[j-1] = a[j];a[j] = tmp;change = 1; } } if(change == 0) { break; }}return a;}}

?

这里用到了一个小技巧,即代码中的变量：change，因为如果在一趟排序中没有发生位置交换，则表明当前的序列已经是有序的了,后面的比较操作就不需要再进行下去,应当跳出循环，所以在这里用change变量来标识在一趟比较中是否发生的置换操作，若没有，则跳出循环.