选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾(目前已被排序的序列)。以此类推,直到所有元素均排序完毕。
如图:
第一步: 我们拿80作为参照物(base),在80后面找到一个最小数20,然后将80跟20交换。
第二步:第一位数已经是最小数字了,然后我们推进一步在30后面找一位最小数,发现自己最小,不用交换。
第三步:........
实现代码:
public class SelectionSort { // 选择排序 public static int[] selectionSort(int[] array) { // 要遍历的次数 for (int i = 0; i < array.length - 1; i++) { // 假设tempIndex的下标的值最小 int tempIndex = i; for (int j = i + 1; j < array.length; j++) { // 如果tempIndex下标的值大于j下标的值,则记录较小值下标j if (array[tempIndex] > array[j]){ tempIndex = j; } } if(tempIndex != i){ // 最后将假想最小值跟真的最小值进行交换 int tempData = array[tempIndex]; array[tempIndex] = array[i]; array[i] = tempData; } } return array; } public static void main(String[] args) { int[] array = { 2, 5, 1, 8, 9, 3 }; System.out.println("排序前:" + Arrays.toString(array)); selectionSort(array); System.out.println("排序后:" + Arrays.toString(array)); } }
运行结果:
排序前:[2, 5, 1, 8, 9, 3]
排序后:[1, 2, 3, 5, 8, 9]