求关注
带你读懂选择排序
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
选择排序图解2
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备考资料等你来领，方便你随时随地学习技术知识！
新建了一下qq群：315211365，欢迎大家进群交流一起学习。谢谢了！也可以介绍给身边有需要的朋友。
文章收录至
Github: https://github.com/CoderMerlin/coder-programming
Gitee: https://gitee.com/573059382/coder-programming
微信公众号
求关注
参考文章：
https://blog.csdn.net/qq_36249079/article/details/81584801
https://www.cnblogs.com/shen-hua/p/5424059.html
推荐文章：
网友评论