JAVA集合类（2）：冒泡排序、二分查找

以下各种排序都是使用数组实现的。

 

1，冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

 

package com.test.array;

public class BubbleSortTest {
	
	public static void main(String[] args) {
		int[] array = {7,2,9,4,5};
		bubbleSort(array);
	}
	
	public static void bubbleSort(int[] array){
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array.length-i-1; j++) {
				if(array[j] > array[j+1]){
					int tmp = array[j];
					array[j] = array[j+1];
					array[j+1] = tmp;
				}
			}
			
			System.out.println("第"+i+1+"趟排序结果");
			for (int k = 0; k < array.length; k++) {
				System.out.print(array[k]+" ");
			}
			System.out.println();
		}
	}
}

最后输出结果为

第01趟排序结果
2 7 4 5 9 
第11趟排序结果
2 4 5 7 9 
第21趟排序结果
2 4 5 7 9 
第31趟排序结果
2 4 5 7 9 
第41趟排序结果
2 4 5 7 9 

  

 

 

2，二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

 

package com.test.array;

public class ArraySearchTest {
	public static void main(String[] args) {
		int[] array = {1,3,6,8,11,18};
		int value = 11;
		int index = binarySearch(array, value);
		System.out.println(index);
	}

	public static int binarySearch(int[] array, int value) {
		int low = 0;
		int high = array.length - 1;
		int middle;
		while (low <= high) {
			middle = (low + high) / 2;
			if (array[middle] == value) {
				return middle;
			}
			if (value < array[middle]) {
				high = middle - 1;
			}
			if (value > array[middle]) {
				low = middle + 1;
			}
		}
		return -1;
	}
}

 

 

3，生成随机数排序测试：

随机生成50个数字（整数），每个数字的范围是【10，50】，统计每个数字出现的次数以及出现次数最多的数字与它的个数，最后将每个数字及其出现次数打印出来。如果某个出现的次数是0，则不打印它。打印时按照数字的升序排列。

package com.test.array;

import java.util.Random;

public class RandomTest {
	public static void main(String[] args) {
		Random random = new Random();
		int[] count = new int[41];  //【10，50】有41个数字
		//生成50个从10到50的随机数
		for (int i = 0; i < 50; i++) {
			//nextInt返回的是大于等于0，小于界限值的整数值，例如下面的nextInt(41)将返回0到40的整数
			int number = random.nextInt(41)+10;
			count[number - 10]++; //记录出现的次数
		}
		int maxTimes = 0;
		int maxTimesValue = 0;
		//打印结果
		for (int i = 0; i < count.length; i++) {
			if (count[i] == 0) {
				continue;
			}
			System.out.println((10+i)+"出现次数："+count[i]);
			if(maxTimes < count[i]){
				maxTimes = count[i];
				maxTimesValue = i +10;
			}
		}
		System.out.println("最大次数是:"+maxTimes+"次,数字是："+maxTimesValue);
	}
}