一文搞定选择排序算法
一、选择排序
本次内容概要：
１、选择排序原理
选择排序是一种比较简单而且直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小或者最大的元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
２、图解选择排序算法
输入一个数组，按小到大顺序排列。
input：[5,4,6,1,3,2]output：[1,2,3,4,5,6]
咱们就以这个题为例子，来讲解和演示一下选择排序算法第一趟的过程。
这个GIF动态图是第一趟的排序过程：
下面仅一步进行分解：
我们的初始状态为：
排序之后的结果应该是：
初始化阶段：
最初的话，假设最小的元素的0号位置。
第１次：
A[j] < A[mineIndex]因为当前比较的这个要比最初记录的值要小，所以替换掉minIndex的值为现在小值的索引。
第２次：
A[j] > A[mineIndex]因为当前比较的这个要比最初记录的值要大，所以忽略，不作操作。
第３次:
A[j] < A[mineIndex]因为当前比较的这个要比最初记录的值要小，所以替换掉minIndex的值为现在小值的索引。
第４次：
A[j] > A[mineIndex]因为当前比较的这个要比最初记录的值要大，所以忽略，不作操作。
第５次：
A[j] > A[mineIndex]因为当前比较的这个要比最初记录的值要大，所以忽略，不作操作。
第一趟结果：
３、选择排序思路
每一趟都找出来一个最小或者最大的值。然后放在序列的起始位置。
例如：A={5,4,6,1,3,2}
初始值：{5,4,6,1,3,2}
第一趟排序：{1}{4,6,5,3,2}
最小的数据是1，所以与0号位置的数据交换位置
第二趟排序：{1,2}{6,5,3,4}
最小的数据是2，所以与1号位置的数据交换位置
第三趟排序：{1,2,3}{5,6,4}
最小的数据是3，所以与2号位置的数据交换位置
第四趟排序：{1,2,3,4}{6,5}
最小的数据是4，所以与3号位置的数据交换位置
第五趟排序：{1,2,3,4,5}{6}
最小的数据是５，所以与4号位置的数据交换位置
第六趟排序：{1,2,3,4,5,6}
由于只剩下一个数据了，就不必参与比较了，直接合并过来即可
４、代码实现选择排序
按从小到大的顺序：
给出：{5,4,6,1,3,2}
输出：{1, 2, 3, 4, 5, 6}
package 排序算法.选择排序;
import java.util.Arrays;
/**
* @Auther: truedei
* @Date: 2020 /20-6-3 15:12
* @Description:
*/
public class SelectSort {
public static int[] selectSort(int [] A){
int minIndex=0,//记录每一趟最小值的索引
temp;//用于交换数据
for (int i = 0; i < A.length-1; i++) {
//每一次都假设第一个为这一趟的最小的值
minIndex=i;
//这里为什么是i+1，因为：要一个一个的往后推，
//i之前是存放的有序的
//i之后是存放的无序的
//i+1是跳过与自己的比较；当然了，不跳过也是可以的，这样就多比较了一次
for (int j = i+1; j < A.length ; j++) {
//如果符合要求
if(A[minIndex]>A[j]){
//就替换掉当前认为最小值的索引
minIndex=j;
}
}
//交换数据
temp=A[i];
A[i]=A[minIndex];
A[minIndex]=temp;
}
return A;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(selectSort(new int[]{5,4,6,1,3,2})));
}
}按从大到小的顺序：
只需要修改一下判断的条件即可：if(A[minIndex]<A[j])
给出：{5,4,6,1,3,2}
输出：{6, 5, 4, 3, 2, 1}
package 排序算法.选择排序;
import java.util.Arrays;
/**
* @Auther: truedei
* @Date: 2020 /20-6-3 15:12
* @Description:
*/
public class SelectSort {
public static int[] selectSort(int [] A){
int minIndex=0,//记录每一趟最小值的索引
temp;//用于交换数据
for (int i = 0; i < A.length-1; i++) {
//每一次都假设第一个为这一趟的最小的值
minIndex=i;
//这里为什么是i+1，因为：要一个一个的往后推，
//i之前是存放的有序的
//i之后是存放的无序的
//i+1是跳过与自己的比较；当然了，不跳过也是可以的，这样就多比较了一次
for (int j = i+1; j < A.length ; j++) {
//如果符合要求
if(A[minIndex]<A[j]){
//就替换掉当前认为最小值的索引
minIndex=j;
}
}
//交换数据
temp=A[i];
A[i]=A[minIndex];
A[minIndex]=temp;
}
return A;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(selectSort(new int[]{5,4,6,1,3,2})));
}
}５、时间复杂度分析
选择排序使用了双层for循环；如果看过我上一篇文章的话，可以很快的知道一些技巧，双层for循环的时间复杂度是：
O(N2) O(N^{2}) O(N2)
这里推导一下，为什么是：
O(N2) O(N^{2}) O(N2)
可以注意到该算法就两个操作是有用的：
- 一个是
比较数据 - 一个是
交换数据
比较数据次数：
是两层for循环，每次内循环都会减少一个直至减少到为１为止
(N−1)+(N−2)+(N−3)+...+2+1=((N−1)+1)×Ｎ−12 (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)×\frac {Ｎ-1}{2} (N−1)+(N−2)+(N−3)+...+2+1=((N−1)+1)×2Ｎ−1
交换数据次数：
外层for循环内进行交换数据，所以是N-1次
Ｎ−1 Ｎ-1 Ｎ−1
时间复杂度就是： ((N−1)+1)×Ｎ−12＋(N−1)＝Ｎ22+Ｎ2−1=Ｎ212+Ｎ12−1 ((N-1)+1)×\frac {Ｎ-1}{2}＋(N-1)＝\frac {Ｎ^{2}}{2}+\frac {Ｎ}{2}-1 =Ｎ^{2}\frac {1}{2}+Ｎ\frac {1}{2}-1 ((N−1)+1)×2Ｎ−1＋(N−1)＝2Ｎ2+2Ｎ−1=Ｎ221+Ｎ21−1
根据大Ｏ推导法则，保留最高阶项： 去掉常数项还剩下：
Ｎ2 Ｎ^{2} Ｎ2
所以最终得出时间复杂度为：
O(Ｎ2) O(Ｎ^{2}) O(Ｎ2)
６、小技巧：常用时间复杂度
(1) Ｏ(1)
（１）O(1) 这个针对的是常数；对于一个N，不管这个N是如何增长，这个时间是不变的。
例如下面这些代码的时间复杂度都是O(1)：
/**
* @Auther: truedei
* @Date: 2020 /20-6-2 22:01
* @Description:
*/
public class Test {
public static void main(String[] args) {
System.out.println("你好，我叫郑晖");
System.out.println("你好，我叫郑晖");
System.out.println("你好，我叫郑晖");
System.out.println("你好，我叫郑晖");
}
}还有这种：
我有一个数组，我知道了我需要的这个数据所在的索引，然后去拿这个值，咋这种也是O(1)
/**
* @Auther: truedei
* @Date: 2020 /20-6-2 22:01
* @Description:
*/
public class Test {
public static void main(String[] args) {
String[] names = {"小明","小红","郑晖"};
System.out.println("你好，我叫"+names[2]);
}
}(2) Ｏ(n)
Ｏ(n)是一个线性增长的。
经常用在for()循环当中
例如下面这种代码:
/**
* @Auther: truedei
* @Date: 2020 /20-6-2 22:01
* @Description:
*/
public class Test {
public static void main(String[] args) {
String[] names = {"小明","小红","郑晖"};
for (int i = 0; i < names.length; i++) {
System.out.println("你好，我叫"+names[i]);
}
}
}(3) Ｏ(n^2)
是一个平方级的的增长。经常出现在两层for循环。
例如本文所写的：
public static int[] sort(int A[]){
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A.length -i - 1 ; j++) {
.....
}
}
return A;
}(4) Ｏ(n^3)
是一个立方级的增长。经常出现在遍历一个三层的for循环中
for (...) {
for (...) {
for (...) {
.....
}
}
}(5) Ｏ(lg n)
是一个对数级。
在二分查找法里就是Ｏ(lg n)。
每次执行Ｎ是以一个倍数的形式是递减的：
比如第１次：１/２
比如第２次：１/４
比如第３次：１/８
比如第４次：１/１６
…
快速的让N的规模变小。
(6) Ｏ(n lg n)
在排序中经常见到的
(7) Ｏ(2^n)
指数级的
７、附：常用的排序算法的时间复杂度和空间复杂度
排序法 | 最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
|---|---|---|---|---|
冒泡排序 | O(n^2) | O(n^2) | 稳定 | O(1) |
快速排序 | O(n^2) | O(n*log2n) | 不稳定 | O(log2n)~O(n) |
选择排序 | O(n^2) | O(n^2) | 不稳定 | O(1) |
二叉树排序 | O(n^2) | O(n*log2n) | 不一顶 | O(n) |
插入排序 | O(n^2) | O(n^2) | 稳定 | O(1) |
堆排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
希尔排序 | O | O | 不稳定 | O(1) |
二、小郑有话说
如果对你有帮助，可以分享给你身边的朋友。 水平有限，难免会有疏漏或者书写不合理的地方，欢迎交流讨论。 作者：
TrueDei如果喜欢我的文章，还没看够可以关注我，我会用心写好每一篇文章。