算法渣-排序-选择

没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法

定义

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

算法

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:

  1. 初始状态:无序区为R[1..n],有序区为空
  2. 第1趟排序
    在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
    ……
  3. 第i趟排序
    第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

演示

image

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void selectSort(int []array) {
for (int i=0;i<array.length-1;i++) {
int min = i;
for (int j = i+1;j<array.length;j++){
if(array[min] > array[j]) {
min = j;
}
}
if( min != i) {
int tmp = array[i];
array[i] = array[min];
array[min] = tmp;
}

}
}

复杂度

比较次数:T = (n-1))+ (n -2)+(n - 3)…. + 1; T = [n*(n-1) ] / 2;

交换次数:

最好的情况全部元素已经有序,则交换次数为0;

最差的情况,全部元素逆序,就要交换 n-1 次;

空间复杂度

最优的情况下(已经有顺序)复杂度为:O(0)

最差的情况下(全部元素都要重新排序)复杂度为:O(n );

平均的时间复杂度:O(1)

Best Average Worst Memory Stable
1 No

VS 插入排序

插入排序特别的相似

复杂度一样,但是插入排序和读入(初始)的数据有关,最优情况只有O(n);而选择排序不论如何,永远都是O(n^2)

插入排序是边读边排,每当读入一个新的数时,目前的数组一定是排好序的。而选择排序不同,它必须是读完所有的数据之后才能开始排序的。

那么选择排序的缺点就是,万一数据量很大,比方说一百万个,光读就慢了,还要排序,那就更慢了。如果这两个耗时的步骤可以并行一起做的话,显然插入排序肯定就会快一些。

朱兴生 wechat
最新文章尽在微信公众号『码农戏码』