选择排序

基本理解

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

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

图示

复杂度分析

最坏时间复杂度 О(n²)
最优时间复杂度 О(n²)
平均时间复杂度 О(n²)
空间复杂度 О(n) total, O(1) auxiliary

代码实现

普通版

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
/**
* @ Description: 选择排序 时间复杂度为O(n*n)
* @ Date: Created in 10:57 2018/7/27
* @ Author: Anthony_Duan
*/
public class SelectionSort {

private SelectionSort(){}

public static void sort(Comparable[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j].compareTo(arr[i]) < 0) {
minIndex = j;
}
}
}
}

private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}

}

优化版
一次性筛选出最大与最小值,从两端向中间排

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
37
38
39
40
41
42
43
/**
* @ Description: 优化版选择排序
* @ Date: Created in 13:23 2018/7/27
* @ Author: Anthony_Duan
*/
public class SelectionSortAdvance {
private SelectionSortAdvance(){}

public static void sort(Comparable[] arr){

int left = 0, right = arr.length - 1;
while(left < right){
int minIndex = left;
int maxIndex = right;

// 在每一轮查找时, 要保证arr[minIndex] <= arr[maxIndex]
if(arr[minIndex].compareTo(arr[maxIndex]) > 0) {
swap(arr, minIndex, maxIndex);
}

for(int i = left + 1 ; i < right; i ++) {
if(arr[i].compareTo(arr[minIndex]) < 0) {
minIndex = i;
} else if(arr[i].compareTo(arr[maxIndex]) > 0) {
maxIndex = i;
}
}

swap(arr, left, minIndex);
swap(arr, right, maxIndex);

left ++;
right --;
}
}

private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}

}
-------------End Of This ArticleThank You For Reading-------------