选择排序

现在的位置: 首页 > 综合 > 正文

RSS

2014年05月08日 ⁄ 综合 ⁄ 共 4415字 ⁄ 字号小中大 ⁄ 评论关闭

欢迎Java爱好者品读其他算法详解：

简单比较排序：http://blog.csdn.net/ysjian_pingcx/article/details/8652091

冒泡排序： http://blog.csdn.net/ysjian_pingcx/article/details/8653732

直接插入排序：http://blog.csdn.net/ysjian_pingcx/article/details/8674454

快速排序： http://blog.csdn.net/ysjian_pingcx/article/details/8687444

快速排序优化：http://blog.csdn.net/ysjian_pingcx/article/details/8687444

选择排序<详解+优化>

前面介绍了入门的算法比较排序，还有形象的的冒泡排序。不过说出来很伤心，这种排序法效率是很低的，比较排序中需要用一个元素与后面的每一个元素进行比较，如果发现有反序的就交换，这样的话效率是很低的，所以这里引入一个选择排序，与比较排序相似，只不过，在每一趟排序中，比较过程中发现反序的时候，并没有及时交换两个数据，而是引入了一个假设的最小值的下标标记，将这个标记赋值为当前比较中最小记录对应的下标，一直到一趟下来，将所有的记录比较完毕，最后交换两个下标对应的记录，用了比较排序的思路，但是抛弃了每一次交换两个记录的步骤。

选择排序思路：

一趟在 n - i + 1(n = 1,2,3...,n - 1)个记录中选取关键字最小的记录作为有序序列的第i个记录。

关键点：比较两个记录的大小，如果反序，记录下下标，知道一趟比较完毕，让后将原来第i个记录与最后记录的小标的记录交换。

看看下面一趟排序的过程分析图：

核心的比较交换代码：

/**
	 * 选择排序算法的核心程序
	 * @param array
	 */
	public void selectSort(int... array){
		int length = array.length;
		for (int i = 0; i < length - 1; i++) {
			int min = i;  // 将当前下标定义为最小值得下标，然后与后面的值一一比较
			for (int j = i + 1; j < length; j++) {  
				if (array[min] > array[j]) { 
					min = j; // 如果有比假设的值更小的，就将这个值的下标给min，没有重复的交换
				}
			}
			if (min != i) { 
				// 如果最小值的下标有变动，就将一轮比较后的最小值与与开始的值交换
				swap(i, min, array);
			}
		}
	}

@int min = i;这个条件，已进入循环，将当前 i 赋给 min，然后将 i 对应的记录与后面多有的元素进行比较，如果有反序的，就将 j 赋给 min；

@内部循环完毕，也就是一趟比较完毕，if(min != i),如果有变动，就交换最终那个下标与 i 对应的记录，也就是，将最小值交换到第 i 个；

@swap是交换数组两个元素的方法，这里不再赘述；

与冒泡排序相似，如果我们待排序的有序序列一开始是有序的，那么第一次比较之后，发现都是正序，那么后面的比较是不是多余的呢，这种多余我们是不是可以认为控制一下呢？答案是肯定的呢?

选择排序算法核心程序的优化：

/**
	 * 优化的排序算法的核心程序
	 * @param array
	 */
	public void selectSort(int... array){
		int length = array.length;
		boolean flag = true;// 配置一个标记，用于对已经有序的数组排序时的简化后面的比较操作
		for (int i = 0; i < length - 1  && flag; i++) { // 作为进入循环的条件
			flag = false; // 进来之后就置为false
			int min = i;  // 将当前下标定义为最小值得下标，然后与后面的值意义比较
			for (int j = i + 1; j < length; j++) {  
				if (array[min] > array[j]) { 
					flag = true; //如果有交换，就置为true
					min = j; // 如果有比假设的值更小的，就将这个值的下标给min，没有重复的交换
				}
			}
			if (flag) { 
				// 如果最小值的下标有变动，就将一轮比较后的最小值与与开始的值交换
				swap(i, min, array);
			}
		}
	}

@多了一个boolean flag = true;一个标记，作为外部循环的条件之一；

@进入了外部循环，将 flag = false; 这个思路是假设序列是有序的；

@在内部比较的过程中，if(array[min] > array[j])成立，就是有反序的，就将flag = true；说明序列不是有序的；

选择排序也是一种常见的简单的排序，很容易理解，那么这里就不多说了，下面提供完整的代码(优化后的)：

/**
 * 优化选择排序算法
 * @author PingCX
 *
 */
public class SelectSortOpt {
	
	public static void main(String[] args) {
		SelectSortOpt selectSort = new SelectSortOpt();
		int[] array = { 25, 36, 21, 45, 98, 13};
		System.out.println(Arrays.toString(array));
		selectSort.selectSort(array);
		System.out.println(Arrays.toString(array));
	}
	/**
	 * 优化的排序算法的核心程序
	 * @param array
	 */
	public void selectSort(int... array){
		int length = array.length;
		boolean flag = true;// 配置一个标记，用于对已经有序的数组排序时的简化后面的比较操作
		for (int i = 0; i < length - 1  && flag; i++) { // 作为进入循环的条件
			flag = false; // 进来之后就置为false
			int min = i;  // 将当前下标定义为最小值得下标，然后与后面的值意义比较
			for (int j = i + 1; j < length; j++) {  
				if (array[min] > array[j]) { 
					flag = true; //如果有交换，就置为true
					min = j; // 如果有比假设的值更小的，就将这个值的下标给min，没有重复的交换
				}
			}
			if (flag) { 
				// 如果最小值的下标有变动，就将一轮比较后的最小值与与开始的值交换
				swap(i, min, array);
			}
		}
	}
	/**
	 * 内部实现，用于交换数组的两个引用值
	 * 
	 * @param beforeIndex
	 * @param afterIndex
	 * @param arr
	 */
	private void swap(int oneIndex, int anotherIndex, int[] array) {
		int temp = array[oneIndex];
		array[oneIndex] = array[anotherIndex];
		array[anotherIndex] = temp;
	}
}

和之前一样，在面向对象语言中，任何可以比较的类型，都可以拿来排序，在Java中是实现了Comparable接口的类：

/**
 * 任意可以比较类型的选择排序算法
 * @author PingCX
 *
 */
public class SelectSortTOpt {
	
	public static void main(String[] args) {
		SelectSortTOpt selectSort = new SelectSortTOpt();
		Integer[] array = { 25, 36, 21, 45, 98, 13};
		System.out.println(Arrays.toString(array));
		selectSort.selectSort(array);
		System.out.println(Arrays.toString(array));
	}
	
	/**
	 * 选择排序算法的核心程序
	 * @param array
	 */
	public <T extends Comparable<T>> void selectSort(T[] array){
		int length = array.length;
		boolean flag = true;
		for (int i = 0; i < length - 1 && flag; i++) {
			flag = false;
			int min = i;  // 将当前下标定义为最小值得下标，然后与后面的值意义比较
			for (int j = i + 1; j < length; j++) {  
				if (array[min].compareTo(array[j]) > 0) { 
					flag = true;
					min = j; // 如果有比假设的值更小的，就将这个值的下标给min，没有重复的交换
				}
			}
			if (flag) { 
				// 如果最小值的下标有变动，就将一轮比较后的最小值与与开始的值交换
				swap(i, min, array);
			}
		}
	}
	/**
	 * 内部实现，用于交换数组的两个引用值
	 * 
	 * @param beforeIndex
	 * @param afterIndex
	 * @param arr
	 */
	private <T extends Comparable<T>> void swap(int oneIndex, int anotherIndex, T[] array) {
		T temp = array[oneIndex];
		array[oneIndex] = array[anotherIndex];
		array[anotherIndex] = temp;
	}
}

@在JDK中Integer类型是实现了Comparable接口的，所以可以作为列子；

@也可以自定义一个类，实现Comparable接口，重写了compareTo方法；