选择排序（Select Sort）

视频讲解链接：【十大排序算法】用可视化动画讲选择排序

1、介绍

? 从头到尾扫描待排序列，找出最小的一个元素，和当前未排序序列的第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。

2、算法步骤

第一轮从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 轮，得到一个按从小到大排列的有序序列。

3、代码实现

1、Java版代码

package sort;

import java.util.Arrays;

public class SelectSort {

	public static void main(String[] args) {
		int [] arr = {44,100,61,3,72,19};
		selectSort(arr);
		System.out.println("排序后：");
		System.out.println(Arrays.toString(arr));
	}
	
	// 选择排序
	public static void selectSort(int[] arr) {
		/**
		 * currentFirstIndex：当前未排序序列的第一个值下标
		 * compareIndex：比较值下标
		 * minIndex:一轮中的最小值下标
		 * indexLast:数组最后一个下标
		 */
		
		int indexLast = arr.length - 1;
		
		// 外层循环控制轮数
		for (int currentFirstIndex = 0; currentFirstIndex <= indexLast - 1; currentFirstIndex++) {
			
			// 每轮开始时，最小值下标为当前未排序序列的第一个值下标
			int minIndex = currentFirstIndex;

			// 内层循环找每一轮最小值的下标
			for (int compareIndex = currentFirstIndex + 1; compareIndex <= indexLast; compareIndex++) {
				
				// 最小值比比较值大，将比较值下标赋值给最小值下标
				if (arr[minIndex] > arr[compareIndex]) {
					minIndex = compareIndex;
				}
			}
			
			// 如果一轮中的最小值下标和当前未排序序列的第一个值下标不相等就交换 
			if(minIndex != currentFirstIndex) {
				int temp = arr[minIndex];
				arr[minIndex] = arr[currentFirstIndex];
				arr[currentFirstIndex] = temp;
			}
		}
	}
}

2、C语言版代码

#include <stdio.h>


// 交换函数
void swap (int a[], int i, int j) {
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}


// 打印数组
void printArr (int *a, int len) {
	int i;
	for (i = 0; i < len; i++) {
		printf ("%4d", a[i]);
	}

	printf ("\n");
}


// 选择排序
int main() {
	
	int a[6] = {44,100,61,3,72,19};
	int len = sizeof(a) / sizeof(a[0]);

	int currentFirstIndex;  // 当前未排序序列的第一个值下标
	int compareIndex;		// 比较值下标
	int minIndex;			// 一轮比较中的最小值下标
	int indexLast = len - 1;          // 数组最后一个下标
	
	// 外层循环控制轮数
	for (currentFirstIndex = 0; currentFirstIndex <= indexLast-1; currentFirstIndex++) {
		
		// 每轮开始时，最小值下标为当前未排序序列的第一个值下标
		minIndex = currentFirstIndex;
		
		// 内层循环找每一轮最小值的下标
		for (compareIndex = currentFirstIndex + 1; compareIndex <= indexLast; compareIndex++) {
			
			// 最小值比比较值大，将比较值下标赋值给最小值下标
			if (a[minIndex] > a[compareIndex]) {
				minIndex = compareIndex;   
			}
		}

		// 如果一轮中的最小值下标和当前未排序序列的第一个值下标不相等就交换 
		if (minIndex != currentFirstIndex) {
			swap (a, currentFirstIndex, minIndex);
		}
	}

	printArr (a, len);

	return 0;
}