选择排序

学习排序的时候呢 就是把复杂的东西先转化成简单的东西，如果直接写循环？那谁能直接写？主要是思想不对了。

选择排序select sorting：

算法思想：选择排序，从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。


第一次从 arr[0]~arr[n-1]中选取最小值，与 arr[0]交换
第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换
第三次从 arr[2]~arr[n-1]中选取最小值，与 arr[2]交换，
第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值，与 arr[n-2]交换，共计 n-1 次，得到一个按排序码从小到大排列的有序序列。

package com.leo.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

//选择排序
public class SelectSort {
	public static void main(String[] args) {
		
		//创建100000个数的随机的数组
		int[] arr = new int[100000];
		for (int i = 0; i < 100000; i++) {
			arr[i] = (int) (Math.random() * 1000000); 
		}
		
		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的时间是:" + date1Str);
		selectSort(arr);
		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序后的时间是:" + date2Str);
        
	}
	
	//选择排序
	public static void selectSort(int[] arr) {
		//选择排序时间复杂度是 O(n^2)
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;
			int min = arr[i];
			for (int j = i + 1; j < arr.length; j++) {
				if (min > arr[j]) { // 说明假定的最小值，并不是最小
					min = arr[j]; // 重置min
					minIndex = j; // 重置minIndex
				}
			}
			// 将最小值，放在arr[0], 即交换
			if (minIndex != i) {
				arr[minIndex] = arr[i];
				arr[i] = min;
			}
		}
		
	}

}

性能比冒泡好。注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

        选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n - 1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等 的元素后面，那么交换后稳定性就被破坏了。就是原数组等的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。