十大排序算法之选择排序

发表于 | 分类于
字数统计: 1.2k 字 | 阅读时长 ≈ 4 分钟

本文首发于个人博客

前言

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

  • 使用的语言为：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
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 = {7, 3, 5, 8, 6, 7, 4, 5,19,30,40,50};

结果为：

  • 【SelectionSort】 稳定性：true 耗时：0.0s(0ms) 比较次数：66 交换次数：11

思考

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

代码地址