选择排序 Selection Sort

1. 前言

选择排序的基本思想是:首先在为排序的数列中找到最小/最大的元素,然后将其存放到数列的起始位置;接着再从剩余为排序的元素中继续寻找最小/最大元素,放到已排序序列的末尾,以此类推,直到所有元素均排序完成

2. 实现

下面以数列:{20,40,30,10,60,50}为例,演示它的排序过程:

3. 时间复杂度和稳定性

  • 时间复杂度:O(N2);假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),需要遍历多少次呢? N-1!因此,选择排序的时间复杂度是O(N2)。
  • 稳定性:用数组实现的选择排序是不稳定的,用链表实现的选择排序是稳定的,一般默认是数组实现,所以是不稳定的

4. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* 选择排序
* @author xiaoyuge
*/
public class SelectSort {

public static void selectSort(int[] a){
int i; //有序区的末尾
int j; //无序区的起始
int min; //无序区最小元素位置
for(i = 0; i < a.length; i++){
min = i;
//找出"a[i+1]....a[n]"之间的最小元素,并赋值为min
for(j = i+1; j < a.length; j++){
if (a[j] < a[min]){
min = j;
}
}
//若min !=i,则交换a[i] 和 a[min]
//交换之后之后,保证了a[0]....a[i]之间的元素是有序的
if (min != i){
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}

public static void main(String[] args) {
int[] a = {20,40,30,10,60,50};
selectSort(a);
for (int i = 0; i < a.length; i++) {
System.out.printf("%d ", a[i]);
}
}
}