1. 基本介绍
选择式排序（select sorting）也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
2. 选择排序思想
基本思想是：第一次从 arr[0]~arr[n-1]中选取最小值，与 arr[0]交换，第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换，第三次从 arr[2]~arr[n-1]中选取最小值，与 arr[2]交换，…，第 i 次从 arr[i-1]~arr[n-1]中选取最小值，与 arr[i-1]交换，…, 第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值，与 arr[n-2]交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。
3. 选择排序理解
![选择排序动图]()
3.1 选择排序图解
1.选择排序一共有数组大小-1 次排序
2.每一次排序，又是一个循环，循环规则如下
2.1 先假定当前这个数是最小数
2.2 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标
2.3 当遍历到数组的最后时，就得到本轮最小数和小标
2.4 交换代码，再继续
4. 选择排序代码
/** * @author: Coder编程 * @create: 2019-6-20 22:06 * @description: 选择排序 **/public class SelectionSort { /** * 选择排序 * @param arr 待排序数组 */ public void selectionSort(Integer[] arr) { // 需要遍历获得最小值的次数 // 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列 for (int i = 0; i < arr.length - 1; i++) { int minindex = i; // 用来保存最小值得索引 int min = arr[i]; // 用来保存最小值 for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) {// 说明假定的最小值，并不是最小 min = arr[j]; // 重置 min minindex = j; // 重置 minIndex } } // 如果假定最小值的索引发生了改变，则进行交换 if(minindex != i){ arr[minindex] = arr[i]; //此时minindex为j，因此i与j交换 arr[i] = min; //最小值给下标i } System.out.format("\n第 %d 趟:\t", i + 1); Arrays.asList(arr).stream().forEach(x -> System.out.print(x + " ")); } } public static void main(String[] args) { //初始数组 Integer arrays[] = {2,9,7,5,3}; // 调用选择排序方法 SelectionSort selection = new SelectionSort(); System.out.print("欢迎个人公众号Coder编程：选择排序前：\t"); Arrays.asList(arrays).stream().forEach(x -> System.out.print(x + " ")); selection.selectionSort(arrays); System.out.print("\n欢迎个人公众号Coder编程：选择排序后:\t"); Arrays.asList(arrays).stream().forEach(x -> System.out.print(x + " ")); } }打印结果
如果还有什么不理解的，可以把代码Debug抛一遍就明白了。
5. 选择排序性能分析
5.1 时间复杂度
简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有n个元素，则比较次数总是n(n - 1) / 2。
而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0.
当序列反序时，移动次数最多，为3n (n- 1) / 2。
所以，综合以上，简单排序的时间复杂度为 O(n^2)。
5.2 空间复杂度
简单选择排序需要占用 1 个临时空间，在交换数值时使用。
6. 选择排序扩展阅读
6.1 C语言版
#include <stdio.h>int main(){ int i,j,t,a[11]; //定义变量及数组为基本整型 printf("请输入10个数：\n"); for(i=1;i<11;i++) scanf("%d",&a[i]); //从键盘中输入要排序的10个数字 for(i=1;i<=9;i++) for (j=i+1;j<=10;j++) if(a[i]>a[j]) //如果前一个数比后一个数大，则利用中间变量t实现两值互换 { t=a[i]; a[i]=a[j]; a[j]=t; } printf("排序后的顺序是：\n"); for(i=1;i<=10;i++) printf("%5d", a[i]); //输出排序后的数组 printf("\n"); return 0;}6.2 Python版
def selectedSort(myList): length = len(myList) for i in range(0,length-1): smallest = i for j in range(i+1,length): if myList[j]<myList[smallest]: tmp = myList[j] myList[j] = myList[smallest] myList[smallest]=tmp print("Round ",i,": ",myList)myList = [2,9,7,5,3]print("Selected Sort: ")selectedSort(myList)6.3 JS版
var example=[2,9,7,5,3];function selectSort(arr){ var len=arr.length; var minIndex,temp; console.time('选择排序耗时')； for(i=0;i<len-1;i++){ minIndex=i; for(j=i+1;j<len;j++){ if(arr[j]<arr[minIndex]){ minIndex=j; } } temp=arr[i]; arr[i]=arr[minIndex]; arr[minIndex]=temp; } console.timeEnd('选择排序耗时'); return arr;}console.log(selectSort(example));文末
欢迎关注个人微信公众号：Coder编程
获取最新原创技术文章和免费学习资料，更有大量精品思维导图、面试资料、PMP备考资料等你来领，方便你随时随地学习技术知识！文章收录至
Github: https://github.com/CoderMerli...
Gitee: https://gitee.com/573059382/c...