简单选择排序

基本思想

在a[1]-a[n-1]中选择最小的元素和a[0]交换；
在a[2]-a[n-1]中选择最小的元素和a[1]交换；
……
在a[i]-a[n-1]中选择最下的元素和a[i-1]交换；

思路

代码实现

package com.nanzx.sort;

import java.util.Arrays;

public class SelectSort {

	public static void main(String[] args) {
		int arr[] = { 101, 34, 119, 1 };
        // 每i轮确定第i个元素为最小值
		selectSort(arr);
	}

	public static void selectSort(int[] arr) {
		int minIndex = 0;
		int min = arr[0];
		for (int i = 0 + 1; i < arr.length; i++) {
			if (arr[i] < min) {
				minIndex = i;
				min = arr[i];
			}
		}
		if (minIndex != 0) {
			arr[minIndex] = arr[0];
			arr[0] = min;
		}
		System.out.println("第一轮后：");
		System.out.println(Arrays.toString(arr));

		minIndex = 1;
		min = arr[1];
		for (int i = 1 + 1; i < arr.length; i++) {
			if (arr[i] < min) {
				minIndex = i;
				min = arr[i];
			}
		}
		if (minIndex != 1) {
			arr[minIndex] = arr[1];
			arr[1] = min;
		}
		System.out.println("第二轮后：");
		System.out.println(Arrays.toString(arr));

		minIndex = 2;
		min = arr[2];
		for (int i = 2 + 1; i < arr.length; i++) {
			if (arr[i] < min) {
				minIndex = i;
				min = arr[i];
			}
		}
		if (minIndex != 2) {
			arr[minIndex] = arr[2];
			arr[2] = min;
		}
		System.out.println("第三轮后：");
		System.out.println(Arrays.toString(arr));
	}
}

运行结果

第1轮后：
[1, 34, 119, 101]
第2轮后：
[1, 34, 119, 101]
第3轮后：
[1, 34, 101, 119]

整合代码

package com.nanzx.sort;

import java.util.Arrays;

public class SelectSort {

	public static void main(String[] args) {
		int arr[] = { 101, 34, 119, 1 };
		selectSort(arr);	
	}

	public static void selectSort(int[] arr) {
		for (int j = 0; j < arr.length - 1; j++) {
			int minIndex = j;
			int min = arr[j];
			for (int i = j + 1; i < arr.length; i++) {
				if (arr[i] < min) {
					minIndex = i;
					min = arr[i];
				}
			}
			if (minIndex != j) {
				arr[minIndex] = arr[j];
				arr[j] = min;
			}
			System.out.println("第" + (j + 1) + "轮后：");
			System.out.println(Arrays.toString(arr));
		}
}

测试简单选择排序的速度O(n²)

package com.nanzx.sort;

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

public class SelectSort {

	public static void main(String[] args) {
		// 创建一个80000个元素的随机的数组
		int[] arr = new int[80000];
		for (int i = 0; i < 80000; i++) {
			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
		}

		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) {
		for (int j = 0; j < arr.length - 1; j++) {
			int minIndex = j;
			int min = arr[j];
			for (int i = j + 1; i < arr.length; i++) {
				if (arr[i] < min) {
					minIndex = i;
					min = arr[i];
				}
			}
			if (minIndex != j) {
				arr[minIndex] = arr[j];
				arr[j] = min;
			}
		}
	}
}