【寒假实习备战day6】选择排序算法的学习

简单的自我介绍

我是一名双非大二学生，目前学习方向为Java后端，快速学习并学到了springboot，并和实验室的朋友做了一个简单的微信小程序，想在寒假找份有关互联网的实习，打算海投，城市和公司暂时没有特别强烈的意向，我会再次牢固的复习一遍Java整套学习知识，并且开始补充算法知识刷算法题，来备战这次寒假实习，并且想报名参加蓝桥杯Java B组的比赛，希望我的一些学习笔记能为你带来一些帮助，这次给大家带来的是选择排序的算法学习。

昨天状态不好，发了动态，被官方小姐姐驼瑞驰回应并给出非常帮的建议，很开心更暖心。当然发帖过程中也有其他牛友们的鼓励和支持，感受到了牛客新的一面，非常感谢能参加这次活动，得到大家的关心和支持！

选择排序是什么？

选择排序是基础排序的一种，它的思路是，原数列分为有序和无序部分，每次从无序部分中挑出极值放入有序数列部分

算法原理

对于数列{5,3,7,2,1,9,8,4}进行从小到大选择排序
初始有序部分为空无序部分为 5 3 7 2 1 9 8 4

第一趟：1 3 7 2 5 9 8 4，有序部分为1 无序部分为3 7 2 5 9 8 4，元素1的位置与元素5的位置对换

第二趟：1 2 7 3 5 9 8 4 ，有序部分为1 2 无序部分为 7 3 5 9 8 4 ，元素2的位置与元素3的位置对换

第三趟：1 2 3 7 5 9 8 4，有序部分为1 2 3 无序部分为7 5 9 8 4，元素3的位置与元素5的位置对换

第四趟：1 2 3 4 5 9 8 7 ，有序部分为1 2 3 4 无序部分为5 9 8 7 ，元素4的位置与元素7的位置对换

第五趟：1 2 3 4 5 9 8 7，有序部分为1 2 3 4 5 无序部分为7 9 8，元素5的位置与元素5的位置对换

第六躺：1 2 3 4 5 7 8 9，有序部分为1 2 3 4 5 7 无序部分为 8 9，元素7的位置与元素9的位置对换

第七趟：1 2 3 4 5 7 8 9，有序部分为1 2 3 4 5 7 8 无序部分为9，元素8的位置与元素8的位置对换，但因为现在只有一个元素无序所以其实以及排序完了

可以看出几个问题

1.可以看出8个元素排序7趟

2.选择排序是选择无序部分的第一个元素与剩下元素的极值进行交换，最后吧无序部分的第一个元素加入有序部分

3.可以看出第五趟与第七趟都进行与自身的交换，这里是优化点

代码示例

public static void main(String[] args) {
    int[] a = {5,3,7,2,1,9,8,4};
    int len = a.length;
    for (int i=0;i<len-1;i++){
        int pos=i;
        for (int j=pos+1;j<len;j++){
            if (a[j]<a[pos]) {
                pos = j;
            }
        }
        if (pos!=i){// 如果交换元素不是自身
            System.out.println("第"+(i+1)+"趟");
            int t=a[pos];
            a[pos]=a[i];
            a[i]=t;
            for (int k=0;k<len;k++)
                System.out.printf("%d ",a[k]);
            System.out.println();
        }
    }
}

结果：

第1趟
1 3 7 2 5 9 8 4
第2趟
1 2 7 3 5 9 8 4
第3趟
1 2 3 7 5 9 8 4
第4趟
1 2 3 4 5 9 8 7
第6趟
1 2 3 4 5 7 8 9

可以看出优化后少了第五趟与第七趟的的交换