简介

选择排序，在众多的排序算法中，是比较简单直观的一种，它的流程主要是这样：

• 首先，找到数组中最小的那个元素
• 其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素，那么它就和自己交换）
• 再次，在剩下的元素中找到最小的元素，将它与第二个元素交换位置。如此往复，直到将整个数组排序

可以看出来，这种排序算法就是在不断地选择剩余元素之中的最小者，所以叫做选择排序

具体介绍

动图演示

算法实现与分析

下面给出一般情况下选择排序的模板(java实现)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class Selection{

	public static void sort(Comparable[] a){
		//将a[]按升序排列
		int N = a.length;

		for(int i = 0; i < N; i++){
			//假定当前最小元素索引为i
			int min = i;
			//遍历 [i+1,length-1]范围内是否存在更小的元素
			for(int j=i+1;j<N;j++){
				if(less(a[j],a[min])){
					min = j;
				}
			}
			//如果[i+1,length-1]范围存在更小元素，则交换此元素与i索引处的元素
			exch(a,i,min);
		}
	}
	//less(),exch()省略
}

从上述程序中可以看出，选择排序算法有两个循环，一个外循环，一个内循环，其中交换元素的方法写在内循环之外，因此交换的总次数是N，所以算法的时间效率主要取决于比较的次数。
若共有N个元素，

• 对于选择最小的元素，需要对 [1,N-1]范围的元素都进行一次比较，共N-1次
• 对于选择第二小的元素，需要对[2,N-1]范围的元素都进行比较，共N-2次
  依次类推，共进行 (N-1)+(N-2)+···+2+1 = N(N-1)/2 ~ (N^2)/2次比较

总结

总的来说，可以看出选择排序是一种比较容易理解和实现的排序算法，有两个特点：

• 运行时间与输入数组的初始状态无关。 不管输入数组的初始状态是有序还是完全混乱，选择排序算法所需要的排序时间都是完全相同的。
• 数据移动较少。 每次交换只会改变两个数组元素的值，而一共需要进行N次交换——交换次数和数组的大小是线性关系。（大部分其他算法都是线性对数或者平方级别）

参考

• 算法(第4版)
• 选择排序

赏

谢谢你请我吃糖果

支付宝

微信