JAVA排序算法-直接选择排序

直接选择排序方法属于选择排序的一种,它的排序速度要比冒泡排 序快一些,也是常用的排序算法,初学者应该掌握。

1.基本思想

直接选择排序的基本思想是将指定排序位置与其他数组元素分别对 比,如果满足条件就交换元素值。注意这里与冒泡排序的区别,不是交 换相邻元素,而是把满足条件的元素与指定的排序位置交换(如从最后 一个元素开始排序),这样排序好的位置逐渐扩大,最后整个数组都成 为已排序好的格式。

这就好比有一个小学生,从包含数字1~10的乱序的数字堆中分别选 择合适的数字,组成一个1~10的排序,而这个学生首先从数字堆中选出 1,放在第一位,然后选出2(注意这时数字堆中已经没有1了),放在 第二位,依此类推,直到其找到数字9,放到8的后面,最后剩下10,就 不用选择了,直接放到最后就可以了。 与冒泡排序相比,直接选择排序的交换次数要少很多,所以速度会 快些。

2.算法示例

每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺 序地放在已排好序的数列的最后,直到全部待排序的数据元素排完。 例如:

直接选择排序算法实例

3.算法实现

下面来介绍一下直接选择排序的具体用法。【例】在项目中创建SelectSort类,这个类的代码将作为直接选 择排序的一个演示,其中排序使用的是正排序,读者可以根据本实例编 写一个倒排序的例子。

/**
 * 直接选择排序算法实例
 * 
 * @author Li Zhong Wei
 */
public class SelectSort {
	public static void main(String[] args) {
		// 创建一个数组,这个数组元素是乱序的
		int[] array = { 63, 4, 24, 1, 3, 15 };
		// 创建直接排序类的对象
		SelectSort sorter = new SelectSort();
		// 调用排序对象的方法将数组排序
		sorter.sort(array);
	}
	
	/**
	 *直接选择排序法
	 * 
	 * @param array
	 *            要排序的数组
	 */
	public void sort(int[] array) {
		int index;
		for (int i = 1; i < array.length; i++) {
			index = 0;
			for (int j = 1; j <= array.length - i; j++) {
				if (array[j] > array[index]) {
					index = j;
				}
			}
			// 交换在位置array.length-i和index(最大值)两个数
			int temp = array[array.length - i];// 把第一个元素值保持到临时变量中
			array[array.length - i] = array[index];// 把第二个元素值保存到第一个元素单元中
			array[index] = temp;// 把临时变量也就是第一个元素原值保持到第二个元素中
		}
		showArray(array);// 输出直接选择排序后的数组值
	}
	
	/**
	 * 显示数组所有元素
	 * 
	 * @param array
	 *            要显示的数组
	 */
	public void showArray(int[] array) {
		for (int i : array) {// foreach格式遍历数组
			System.out.print(" >" + i);// 输出每个数组元素值
		}
		System.out.println();
	}
}
直接选择排序算法运行结果
直接选择排序算法运行结果

发表评论