十大排序算法之选择排序

本文首发于个人博客

前言

本系列排序包括十大经典排序算法。

  • 使用的语言为:Java
  • 结构为:
    定义抽象类Sort里面实现了,交换,大小比较等方法。例如交换两个值,直接传入下标就可以了。其他的具体排序的类都继承抽象类Sort。这样我们就能专注于算法本身。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* 返回值等于0,代表 array[i1] == array[i2]
* 返回值小于0,代表 array[i1] < array[i2]
* 返回值大于0,代表 array[i1] > array[i2]
*/
protected int cmp(int i1, int i2) {
return array[i1].compareTo(array[i2]);
}

protected int cmp(T v1, T v2) {
return v1.compareTo(v2);
}

protected void swap(int i1, int i2) {
T tmp = array[i1];
array[i1] = array[i2];
array[i2] = tmp;
}

什么是选择排序

  • 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是稳定的排序方法。
  • 需要注意的是,不同的写法可能会导致选择排序变成不稳定的。

算法思想

  • n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
    • ①初始状态:无序区为R[1..n],有序区为空。
    • ②第1趟排序
      在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
    • ……
    • ③第i趟排序
      第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

解释

  • 对比数组中前一个元素跟后一个元素的大小,如果后面的元素比前面的元素小则用一个变量k来记住他的位置,接着第二次比较,前面“后一个元素”现变成了“前一个元素”,继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标),等到循环结束的时候,我们应该找到了最小的那个数的下标了,然后进行判断,如果这个元素的下标不是第一个元素的下标,就让第一个元素跟他交换一下值,这样就找到整个数组中最小的数了。然后找到数组中第二小的数,让他跟数组中第二个元素交换一下值,以此类推。

算法分析

时间复杂度

选择排序的最坏、最好、平均时间复杂度为 O(n^2)。
综上,因此选择排序总的平均时间复杂度为O(n^2)。但是总体上要比冒泡排序要好。因为交换的次数少于冒泡排序

算法稳定性

  • 选择排序是一种稳定排序算法。

是否是原地算法

  • 何为原地算法?
    • 不依赖额外的资源或者依赖少数的额外资源,仅依靠输出来覆盖输入
    • 空间复杂度为 𝑂(1) 的都可以认为是原地算法
  • 非原地算法,称为 Not-in-place 或者 Out-of-place
  • 选择排序属于 In-place

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class InsertionSort2<T extends Comparable<T>> extends Sort<T>  {

@Override
protected void sort() {
for (int begin = 1; begin < array.length; begin++) {
int cur = begin;
T res =array[cur];
while (cur>0 && cmp(res,array[cur-1])<0) {
array[cur] = array[cur-1];
cur--;
}
array[cur] = res;
}

}

}

可以优化为如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class SelectionSort <T extends Comparable<T>> extends Sort<T>{

@Override
protected void sort() {
// TODO Auto-generated method stub
for (int end = array.length-1; end >0; end--) {

int maxIndex = 0;
for (int begin = 1; begin <=end; begin++) {
if (cmp(maxIndex, begin)<=0) {
maxIndex = begin;
}
}
swap(maxIndex, end);
}
}

}

验证

使用数据源如下

Integer[] array = Integers.random(20000, 1, 80000);

结果为:

【BubbleSort】
稳定性:true 耗时:2.494s(2494ms) 比较次数:2.00亿 交换次数:9950.84万

【BubbleSort1】
稳定性:true 耗时:1.95s(1950ms) 比较次数:2.00亿 交换次数:9950.84万

【BubbleSort2】
稳定性:true 耗时:2.048s(2048ms) 比较次数:2.00亿 交换次数:9950.84万

【InsertionSort1】
稳定性:true 耗时:1.125s(1125ms) 比较次数:9952.84万 交换次数:9950.84万

【InsertionSort2】
稳定性:true 耗时:0.772s(772ms) 比较次数:9952.84万 交换次数:0

【InsertionSort3】
稳定性:true 耗时:0.546s(546ms) 比较次数:25.80万 交换次数:0

【SelectionSort】
稳定性:true 耗时:0.458s(458ms) 比较次数:2.00亿 交换次数:2.00万

【HeapSort】
稳定性:false 耗时:0.013s(13ms) 比较次数:51.08万 交换次数:2.00万

【QuickSort】
稳定性:false 耗时:0.01s(10ms) 比较次数:32.00万 交换次数:1.32万

【MergeSort】
稳定性:true 耗时:0.011s(11ms) 比较次数:26.08万 交换次数:0

思考

上一篇我们是经过了一些代码优化,那么这一种选择排序是否也可以进行优化呢?答案是肯定的。我们可以使用堆来选择最大值,从而进行优化。后续文章十大排序算法之堆排序有讲到。

代码地址

------ 本文结束感谢您的阅读 ------