Java版 直接选择排序 算法精讲

直接选择排序方法属于选择排序的一种，它的排序速度要比冒泡排序快一些。

直接排序的基本思想是将指定排序位置与其它数组元素分别对比，如果满足条件就交换元素值。

import java.util.Scanner;
/**
 * @author 九幽天决
 * 
 * 在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要比较n-i 次(1<=i<=n-1)
 * 每次交换最多需要3次移动，因此，总的比较次数：C=(n*n - n)/2
 * 总的移动次数(最大值)： 3(n-1).由此可知，直接选择排序的时间复杂度为 O(n^2)
 */
public class SelectionSort {
	public static void selectionSort(int[] a) {
		if (a==null&&a.length<1) {
			return;
			/**
			 * 空数组直接返回
			 **/
		}
		for (int i = 0; i < a.length-1; i++) { // i表示次数，共进行n-1次选择和交换
			int minIndex = i; // 用minIndex表示最小元素的下标
			for (int j = i+1; j < a.length; j++) {// 找到当前排序区间中最小元素的下标
				if (a[minIndex] > a[j]) {// 如果后面的元素小于当前最小元素，则用minIndex记录下后面最小元素的下标
					minIndex = j;//储存最小元素下标
				}
			}
			if (minIndex != i) {// 当最小元素的下标不为i时交换位置
				int temp = a[i];
				a[i] = a[minIndex];
				a[minIndex] = temp;
			}
		}
	}

	/**
	 * 请输入元素的个数 7 
	 * 请依次输入元素 11 44 75 10 5 52 144
	 * 排序之后 5 10 11 44 52 75 144 
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入元素的个数");
		int n = sc.nextInt();// 确定数组容量1
		int[] a = new int[n];// 创建数组
		System.out.println("请依次输入元素");// 数组元素赋值
		for (int i = 0; i < a.length; i++) {
			a[i] = sc.nextInt();
		}
		selectionSort(a);
		System.out.println("排序之后");
		for(int e:a){// 循环打印出排序后的数组
			System.out.print(e+" ");
		}
	}
}