排序算法——选择排序

基本思想

首先再未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。一次类推，直到所有的元素都排序完成。

动态图演示

代码实现

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
		  int[] data = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		  selectSort(data);
		  System.out.println("选择排序后的结果: " + Arrays.toString(data));
    }
	
	/**
	 * 选择排序
	 * @param data 待排序序列
	 */
	public static void selectSort(int[] data) {
		for(int i = 0; i < data.length - 1; i++) {
		   // 交换次数
		   // 先假设每次循环时，最小索引为i
			int minIndex = i;
			// 每个元素都和剩下的未排序的元素比较
			for(int j = i + 1; j < data.length; j++) {
				// 寻找最小索引
				if(data[j] < data[minIndex]) {
					// 将最小索引保存起来
					minIndex = j;
				}
			}
			// 经过一轮循环，可以找到最小索引，将最小索引对应的元素放到i的位置
			swap(data,i,minIndex);
		}
	}
	
	/**
	 * 交换元素
	 * @param 排序序列
	 * @param i 交换元素的索引
	 * @param minIndex 最小元素索引
	 */
	private static void swap(int[] data, int i, int minIndex) {
		int tmp = data[i];
		data[i] = data[minIndex];
		data[minIndex] = tmp;
	}
}

复杂度

• 时间复杂度：O(n²)