文 | 莫若吻
1.简介
排序就是算法。
选择排序（Selection sort）是一种简单直观的排序算法。
选择排序是不稳定的排序方法。
eg：序列[9，9， 1]第一次就将第一个[9]与[1]交换，导致第一个9挪动到第二个9后面
Note：一般面试的时候才会用到选择、冒泡排序。
2.原理
选择排序的工作原理是**每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 **
3.原理过程图
内循环结束一次，最值出现头角标位置上。（原理过程如下图）
4.时间复杂度
简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 n 个元素，选择排序的赋值操作介于 0 和 3 (n - 1） 次之间; 则比较次数 永远都是n (n- 1) / 2; 而移动次数（即：交换操作）与序列的初始排序有关,介于 0 和 (n - 1） 次之间。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为n - 1 次;逆序交换n/2次。综上，简单选择排序的时间复杂度为 O(n²)。
选择排序的移动次数比冒泡排序少多了，由于交换所需CPU时间比 比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。
5.性能分析 (稳定性)
选择排序的时间复杂度为O(n²)，由于每次选择仅考虑某一位置上的数据情况，可能会破坏之前数据的相对位置，因此它是一种不稳定的排序方法。
6.选择排序有两个重要特点:
1)运行时间和输入无关
即不论数组的初始状态的有序程度，选择排序的比较次数都没有变化。考虑到比较次数与元素个数的关系是n (n- 1)/ 2，所以当一个已经比较有序的数组使用选择排序会很不划算。
2)数据的移动操作最少
移动操作次数是一个常量，最多为n-1，其他的算法都不具备这个特征。
7.选择排序与冒泡排序哪个效率更高？
选择排序、冒泡排序都用for（for(if)）结构语句。一般选择排序效率会更高一些。
自我总结分析原因：（更详细情况请参考上面选择排序的时间复杂度）
冒泡排序的思想为每一次排序过程，通过相邻元素的交换，将当前没有排好序中的最大（小）移到数组的最右（左）端。而选择排序的思想也很直观：每一次排序过程，我们获取当前没有排好序中的最大（小）的元素和数组最右（左）端的元素交换，循环这个过程即可实现对整个数组排序。
同样数据的情况下，两种算法的循环次数是一样的，但选择排序只有0到1次交换，而冒泡排序只有0到n次交换 。而影响我们算法效率的主要部分是循环和交换，显然，次数越多，效率就越差。选择排序的平均时间复杂度比冒泡排序的稍低。所以相比较而言选择排序效率会更高一些。
8.示例代码（Java）
对给指定数组进行排序：{5,1,6,4,2,8,9}
核心代码：
/*
选择排序。
内循环结束一次，最值出现头角标位置上。
*/
public static void selectSort(int[] arr)
{
for (int x=0; x<arr.length-1 ; x++)
{
for(int y=x+1; y<arr.length; y++)
{
if(arr[x]>arr[y]) //缺点：性能低。
{
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
}
}```
__详细代码：__
（注：大家可以自行运行结果查看）
import java.util.*;
class ArraySort
{
public static void main(String[] args)
{
int[] arr = {5,1,6,4,2,8,9};
//排序前；
printArray(arr);
//选择排序
selectSort(arr);
//冒泡排序
//bubbleSort(arr);
//排序后：
printArray(arr);
//Arrays.sort(arr); //java中已经定义好的一种排序方式。开发中，对数组排序。要使用该句代码。
}
/*
选择排序。
内循环结束一次，最值出现头角标位置上。
*/
public static void selectSort(int[] arr)
{
for (int x=0; x<arr.length-1 ; x++)
{
for(int y=x+1; y<arr.length; y++)
{
if(arr[x]>arr[y]) //缺点：性能低。
{
swap(arr,x,y);
}
}
}
}
/*
无论什么排序。都需要对满足条件的元素进行位置置换。
所以可以把这部分相同的代码提取出来，单独封装成一个函数。
*/
public static void swap(int[] arr,int a,int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/*
排序显示格式
*/
public static void printArray(int[] arr)
{
System.out.print("[");
for(int x=0; x<arr.length; x++)
{
if(x!=arr.length-1)
System.out.print(arr[x]+", ");
else
System.out.println(arr[x]+"]");
}
}
}
<br/>
***
版权声明：本文为博主原创文章，转载请必须注明出处，谢谢！
<br/>