选择排序也是一种简单直观的排序算法，实现原理比较直观易懂：
首先在未排序数列中找到最小元素，然后将其与数列的首部元素进行交换，然后，在剩余未排序元素中继续找出最小元素，将其与已排序数列的末尾位置元素交换。以此类推，直至所有元素圴排序完毕.
同理,可以类比与打扑克和打麻将, 和上面插入排序不同, 插入排序相当于抽一张牌整理好了再抽一张, 而选择排序相当于一次性给你一副乱牌, 然后慢慢整理的感觉.
这也容易理解为什么选择排序为啥比插入排序慢了. 插入排序是摸一张牌, 然后直接插入到手中已经排好序的牌,再摸下一张牌.
选择排序相当于在一堆牌中, 不断的找到最小的牌往前面放.
image.png
代码实现：
/**
* 选择排序
*/
public void selectSort01() {
int[] arr = {4,1,3,6,2,5};
/**
* 每轮找到最小值： 找到最小值（[]中为最小值） 交换 分割线左边代表已经排序好的数组，右边代表未排序的数组
* 第一轮： {4,[1],3,6,2,5} -> {[1],4,3,6,2,5} (将[1]和4交换位置)
* 第二轮； {1, --分割线-- 4,3,6,[2],5} -> {1,[2], --分割线-- 3,6,4,5} (将[2]和4交换位置)
* 第三轮： {1,2, --分割线-- [3],6,4,5} -> {1,2,[3], --分割线-- 6,4,5} ([3]和min相等，无需交换位置)
* 第四轮： {1,2,3, --分割线-- 6,[4],5} -> {1,2,3,[4], --分割线-- 6,5} (将[4]和6交换位置)
* 第五轮： {1,2,3,4, --分割线-- 6,[5]} -> {1,2,3,4,[5], --分割线-- 6} (将[5]和6交换位置）
* 第六轮： {1,2,3,4,5, --分割线-- [6]} -> {1,2,3,4,5,6} (就剩6一个元素，无需交换)
* 得到结果：{1,2,3,4,5,6}
*/
for (int i=0;i<arr.length;i++) {//比较几轮
int min = i;//初始化最小值min（索引index）为每轮未排序数组的第一个元素位置
//第二层for循环目的是从未排序的数组中找出最小的值（用来和未排序数组中第一个元素进行比较）
for (int j = i+1;j< arr.length;j++) {
if (arr[j] < arr[min]) {
//将最小值的index复制给min，一轮循环之后，就得到了数组中最小值的index
min = j;
}
}
//每轮找到的最小值min和未排序数组的第一个元素比较
if (min != i) {
//如果最小值min和未排序数组的第一个元素index不同，则替换位置
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
Log.i(TAG, "第"+(i+1)+"轮，i="+i+", min="+min+", arr="+Arrays.toString(arr));
}
Log.i(TAG, "选择排序结果：arr="+Arrays.toString(arr));
}
运行结果：
第1轮，i=0, min=1, arr=[1, 4, 3, 6, 2, 5]
第2轮，i=1, min=4, arr=[1, 2, 3, 6, 4, 5]
第3轮，i=2, min=2, arr=[1, 2, 3, 6, 4, 5]
第4轮，i=3, min=4, arr=[1, 2, 3, 4, 6, 5]
第5轮，i=4, min=5, arr=[1, 2, 3, 4, 5, 6]
第6轮，i=5, min=5, arr=[1, 2, 3, 4, 5, 6]
选择排序结果：arr=[1, 2, 3, 4, 5, 6]
————————————————
版权声明：本文为CSDN博主「zzzgd816」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/zzzgd_666/article/details/87634775
网友评论