普林斯顿大学算法公开课笔记——选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。——维基百科

复杂度

简单选择排序的特点是交换移动次数很少(至多n-1次),其时间复杂度为 O(n²) (时间主要花在比较上,总的比较次数为N=(n-1)+(n-2)+…+1=n*(n-1)/2),与冒泡排序一样,但性能上优于冒泡。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Selection
{
public static void sort(Comparable[] a){
int N = a.length;
for (int i=0; i<N; i++){
int min = i;
for (int j=i+1; j<N; j++ )
if(less(a[j], a[min]))
min = j;
exch(a, i, min);
}
}
private static boolean less(Comparable v, Comparable w)
{
return v.compareTo(w)<0;
}
private static void exch(Comparable[] a, int i, int j)
{
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}