重走算法路之简单排序（冒泡）

           上个学期学校开了数据结构的课，就这样酱油过来了，感觉弱弱的，随着年龄的增长，思维也有了一点点的转变，这个学期又重新捡起了，算法(Algorithm)和数据结构(data structure)是搞伊特（IT）的屌丝程序猿大学四年甚至是一生都要学习的东西，他的重要性就不多说了，搞这个的都懂，虽然做不了什么ACM的大神，也做不了什么算法的大牛，但是觉得这个东西对思维和眼界的开阔 确实很有帮助的，人的脑袋是越想越有idea的，虽然过程有一点痛苦，但是当把一个别人搞不懂的东西（也许只知道用，却不知道原理的人来说）搞出来的时候自己心里还是会有一点点的小幸福的，这种感觉大家都懂。

          这个学期开始决定把一些常用的算法给搞懂，虽然有些东西自己也想不出，还是要借助百度，既然别人乐于奉献，那我们就欣然接受咯，只是花一点点自己的时间去把他们扣下来，成为自己的东西，何乐而不为。下面贴上算法篇的第一个程序，写过很多次了，今天贴出来，放在算法(Algorithm)篇的第一个位置，这绝不是最后一个，相信一年后，那里面会堆得满满的，只为对自己的监督和一个弱弱的承诺。

      说了那么多的废话，下面开始第一个冒泡排序

      

 

      原理：

冒泡排序算法的运作如下：（从后往前）

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

     时间复杂度 O(n2)

     一个循环嵌套另一个循环，外层的循环控制依次要操作的每一个元素，

    内层的循环控制外层当前被操作 数依次和其他数的比较。

    

    代码： 

        /**
	 * 冒泡排序的方法
	 */

 	public void bubbleSort() {
		for(int i=1;i <count;i++ ) {
			for(int j=0; j < count-i;j++) {
				if(array[j]>array[j+1]) {
					exChange(j,j+1);
				}
			}
		}
	}

 

   下面贴出 整个程序的代码：

   

package 冒泡排序;

/**
 * 冒泡排序
 * @author TMs
 *
 */
public class BubbleSort {
	public long[] array;
	public int count;
	
	public static void main(String[] args) {
		BubbleSort bubbleSort = new BubbleSort(10);
		bubbleSort.insert(35);
		bubbleSort.insert(5);
		bubbleSort.insert(3);
		bubbleSort.insert(135);
		bubbleSort.insert(34);
		bubbleSort.insert(78);
		bubbleSort.insert(3);
		bubbleSort.insert(335);
		bubbleSort.insert(25);
		bubbleSort.insert(65);
		
		bubbleSort.getSize();
                System.out.println("排序前：");
		bubbleSort.display();
		
		bubbleSort.bubbleSort();
		System.out.println("排序后：");
		bubbleSort.display();
	}
	
	
	/*
	 * 构造方法，生成一个指定大小的数组
	 */
	public BubbleSort(int max) {
		array = new long[max];
		count = 0;
	}
	
	/**
	 * 向一个数组中插入一个元素
	 */
	public void insert(long value) {
		array[count] = value;
		count++;
	}
	
	/**
	 * 得到数字的中元素的个数
	 * @return 数组中元素的个数
	 */
	public void getSize() {
		System.out.println("数组中当前有的元素个数="+count);
	}
	
	/**
	 * 打印数组的值
	 */
	public void display() {
		for(int i = 0; i<count; i++) {
			System.out.print("array["+i+"]="+array[i]+" ");
		}
		System.out.println();
	}
	
	/**
	 * 冒泡排序的方法
	 */

 	public void bubbleSort() {
		for(int i=1;i <count;i++ ) {
			for(int j=0; j < count-i;j++) {
				if(array[j]>array[j+1]) {
					exChange(j,j+1);
				}
			}
		}
	}
	
	/**
	 * 交换数组的下标
	 * @param x 下标
	 * @param y 下标
	 */
	public void exChange(int x,int y) {
		long temp;
			temp = array[x];
			array[x] = array[y];
			array[y] = temp;
	}
}

   运行结果：

   

数组中当前有的元素个数=10
排序前：
array[0]=35 array[1]=5 array[2]=3 array[3]=135 array[4]=34 array[5]=78 array[6]=3 array[7]=335 array[8]=25 array[9]=65 
排序后：
array[0]=3 array[1]=3 array[2]=5 array[3]=25 array[4]=34 array[5]=35 array[6]=65 array[7]=78 array[8]=135 array[9]=335 

   

   PS：

   冒泡排序也是我们学过的最简单的排序方法了，也是我们大学接触到的第一个     排序方法，先易后难，做事要有一个过程嘛。晚上吃多了会长胖。