Java排序算法实现

温故而知新，可以为师矣！
经常温故旧的知识，每次都有新的体会，这种感觉真的很好。
对于排序算法，面试中经常会被问道，因此我在这里做一个简单的小结，方便以后复习。

在引入排序算法之前，先介绍一下排序会用到的一些基础：
交换数组中的两个元素：
用一个中间变量来存放需要交换的数。以下代码：

	/**
	 * 交换数组中的两个元素
	 * @param arrs 数组
	 * @param i 下标i
	 * @param j 小标j
	 */
	public static void swap(int[] arrs, int i, int j) {
		int temp;// 临时变量
		temp = arrs[i];
		arrs[i] = arrs[j];
		arrs[j] = temp;
	}

正式进入排序学习，排序算法有很多，今天只总结一下其中最常用的两种：
冒泡排序和选择排序。
1.冒泡排序
冒泡排序最基本的原理就是：相邻交换。也就是说比较数组中相邻的元素，如果第一个元素比第二个元素大，则交换他们的位置。

1）代码实现：

	/**
	 * 冒泡排序：相邻交换(比较相邻元素，如果第一个比第二个大，就交换他们的位置)<p>
	 * 适用于排序小列表
	 * @param arrs
	 */
	public static void bubbleSortArray(int[] arrs){
		
		for (int i=1; i< arrs.length; i++) {
			for (int j=0; j<arrs.length-i; j++) {
				if (arrs[j] > arrs[j+1]) {// 比较相邻元素
					swap(arrs, j, j+1);// 交换元素
				}
			}
			
		}
	}

2）图片分析：



2.选择排序
选择排序跟冒泡排序比较类似，冒泡排序只要发现两个元素是逆序的，则交换；而选择排序的原理是，只有当确定了元素是数组中最小的之后才会交换。
1）代码实现：

	/**
	 * 选择排序：每次最小/大排在相应的位置<p>
	 * 适用于排序小列表
	 * @param arrs
	 */
	public static void selectSortArray(int[] arrs){
		
		for (int i=0; i<arrs.length-1; i++) {    // 循环次数0~length-1
			for (int j=i+1; j<arrs.length; j++) {// 循环次数i+1~length 
				if (arrs[i] > arrs[j]) {
					swap(arrs, i, j);// 交换元素
				}
			}
		}
	}

2）图片分析



其实选择排序就是：
1、用数组中的第1个元素去跟数组中第二个元素往后的每一个元素进行比较，得出最小的数放在数组的第1位；
2、接着用数组中的第2个元素去跟数组中的第3个元素往后的每一个元素进行比较，得出第二小的元素放在数组的第2位；
3、以此类推，直到数组排序完毕。

评论

1 楼 huiqoo 2014-04-04