java-冒泡排序-简单选择排序

 

 

1 冒泡

 

冒泡排序动画演示: http://www.cncfan.com/html/88/5380.html   

 

代码：

/**
 * 冒泡排序
 * @author zm
 * 大循环和小循环要结合一起看
 * 小循环负责 当前组下找两两数字比较，找到最大/小值，并将这个最大/小值放在最后
 * 大循环负责 将组内所有数据都安排到合理的位置( eg: 6个数字组成的数组，你需要执行 6-1次的组内小循环，才能将这6个数字按照从大/小的顺序安排到合理的位置)
 */
public class BubbleSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int a[] = new int[4];
		a[0] = 8;
		a[1] = 3;
		a[2] = -1;
		a[3] = 0;
		
		bubbleSort(a);
		for(int i=0; i<a.length; i++){
			
			System.out.println(a[i]);
		}
	}
	/**
	 * 比如在i=0的第一次大循环下的小循环比较中，就会从  [8,3,-1,0]中找到最大数8，  比较结果为 [3,-1,0,8]
	 * 在        i=1的第二次大循环下，小循环就从[3,-1,0]里进行比较(int j=0; j<a.length-1-1; j++)，剔除和数字8的比较，最后结果为 [-1,0,3,8]
	 */
	private static void bubbleSort(int[] a) {
		int temp;// 在单次大循环内，执行这个循环内 数组内部数据的交换操作
		// 大循环是要将数组所有数据排序按照规则排序完， 需要进行 size -1 次               
		for(int i=0; i<a.length-1; i++){ // 小循环是在 每一个大循环对应的数组内，将这个数组的最大/小 数找出，找出后这个最大/小值剔除，不作为下次大循环的比较对象   
			for(int j=0; j<a.length-1-i; j++){ // 这里的 i就表示在当次（i）大循环下，小循环中要剔除比较的数据个数
				if(a[j] > a[j+1]){
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}
	}

}

 

 

 

2 快速选择

 

 

/**
 * 简单选择排序(效率要比冒泡排序高)
 * 对n个记录进行扫描，选择最小的，进行输出
 * 对n-1访问记录进行扫描，选择最小的进行输出
 * .... 不断重复
 * 直到只剩下一个记录为止。
 * @author zm
 * 
 */
public class SelectSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int a[] = new int[4];
		a[0] = 8;
		a[1] = 3;
		a[2] = -1;
		a[3] = 0;
		
		selectSort(a);
		for(int i=0; i<a.length; i++){
			System.out.println(a[i]);
		}
	}

	// 要点是： 1 最小值初始指向最左侧元素
	private static void selectSort(int[] a) {
		// i是第几次大循环的标志位  k 总是指向最小的哪一个  j则在大循环下不断的移动
		int k;
		int tmp;
		for(int i=0; i<a.length-1; i++){
			k = i; // 每次大循环下，k总是指向当前大循环下最开始的位置
			for(int j=i; j<a.length; j++){ // 遍历当前大循环下所有数组内的数据，如果数组内的数据有比 a[k]还小的，那么将k指向最小这个数
				if(a[j] < a[k]){
					k = j; 
				}
			}
			tmp = a[i]; // 每次大循环后，将数组最左侧的数值替换成最小值
			a[i] = a[k];
			a[k] = tmp;
		}
		
	}
	
}

 

 

 

3 两者简单比较：

 

3.1 冒泡排序交换次数多于选择排序，选择排序的内存循环中交换仅仅是在内层for结束后才交换，远远小于冒泡排序

3.2 冒泡排序是将最大/小值放在数组最右侧， 选择排序是将最大/最小数放在数组最左侧。