02-选择排序

选择排序

是一种简单直观的排序算法。

• 固定值与其他值依次比较，互换位置
• 记忆：外层0 ~ <length-1，i为固定值，内层i+1 ~ <length

/**
 * 选择排序：固定值与其他值依次比较，互换位置
 * 总共轮次：数组长度-1
 * 单轮次数：固定值依次比较其他值
 * @arr 传入int类型数组
 */
 public static void selectSort(int[] arr) {
     //外层轮次：i(0~3)，每轮固定元素值
     for (int i = 0; i < arr.length-1; i++) {
         //内层单轮次数：每轮从固定值的下一个值开始，逐个比较
         for (int j = i+1; j < arr.length; j++) {
             if (arr[i] > arr[j]) {
                 int tmp = arr[i];
                 arr[i] = arr[j];
                 arr[j] = tmp;
             }
         }
     }
 }

它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
选择排序是不稳定的排序方法。
原因是用数组实现的选择排序是不稳定的，用链表实现的选择排序是稳定的，因为数组内会破坏相同元素的位置，所以选择排序是不稳定的。
在《算法》第四版217页上作者已经说了，有很多办法可以将任意排序算法变成稳定的，但是，往往需要额外的时间或者空间。

【逻辑】外层0 ~ <length-1，i为固定值，内层i+1 ~ <length。固定值与其他值依次比较，互换位置
【优点】数据移动次数已知为（n-1）次
【缺点】比较次数多

public class TestArraySort {
	public static void main(String[] args) {
		int[] nums = {1, 8, 3, 6, 2, 9, 7, 4, 5};
		selectSort(nums);
		for (int i = 0; i < nums.length; i++) {
			System.out.print(nums[i] + " "); // 1 2 3 4 5 6 7 8 9
		}
	}
	
	/**
	 * Java排序：选择排序
	 * 说明：固定值与其他值依次比较，互换位置
	 * @param array 需要排序的无序整数类型数组
	 */
	public static void selectSort(int[] array) {
		// 1. 参数合法性判断
		if (null == array || array.length == 0) {
			return;
		}
		
		// 2. 选择排序主逻辑
		for (int i = 0; i < array.length-1; i++) {
			for (int j = i + 1; j < array.length; j++) {
				if (array[i] > array[j]) { // 升序：选择1个数array[i]与i+1后面的数依次比较
				//if (array[i] < array[j]) { // 降序
					int tmp = array[i];
					array[i] = array[j];
					array[j] = tmp;
				}
			}
		}
	}
}