（4）排序算法——选择排序之简单选择排序

发表于   |   分类于   |   阅读次数

1、基本思想：

选择排序就是在列表中依次查找最小（或最大）的值，放到已排好序的序列中，直到元素全部排列。

2、算法描述：

假设有数组arr[n]，升序排列。

  1. 首先找到数组中最小记录并记录其下标，将其与第一个未排序的元素交换位置。
  2. 然后在之后的未排序的数组元素中再找出最小的元素记录其下标，将其与未排序的部分的第一个元素交换位置。
  3. 重复此过程，直到数组遍历完成。
    Alt text

3、Java实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 简单选择排序
* @author lizhen
 */
public class SelectionSort {
	public void selectionSort(int[] array) {
		// 升序排列
		for (int i = 0; i < array.length; i++) {
			int index = i;//记录最小值的下标位置。
			for (int j = i; j < array.length; j++) {
				if (array[j] < array[index]) {
					index = j;
				}
			}
			int minNum = array[index];
			array[index] = array[i];
			array[i] = minNum;
		}
	}
}

查找方式为线性查找，找到最小值的下标index。然后依次把未排序数组中的最小值放到已排序数组之后。

4、效率分析：

Alt text