vlambda博客
学习文章列表

1、引言

昨天我们学习了二分查找法，但是二分查找法使用的前提必须是有序的数组或者列表，（当然很多的算法都是仅在数据有序的前提下才能使用）

但是在实际工作中，我们接收到的数组不可能都是有序的，那怎么办呢？于是乎我们就应该先对接收到的数组或者列表进行排序。今天先来介绍第一种排序方法————选择排序。在要理解选择排序的内容，我们还必须具备关于数组、链表和大O表示法（专业术语：时间复杂度）的知识储备。

2、知识准备

我们都知道不管是数组还是链表，它们都是操作系统为我们开辟的一系列空间，但两者不同的是数组是一段连续的内存空间，而链表不连续。这两种内存空间都各有利弊，我们要视实际情况选择数组还是链表解决问题。首先，我们应对内存有一个直观的了解。

2.1.1 内存

我们都去超市买过东西，但是进入超市并不能携带我们的包或者其他物品，超市便提供了储物柜让我们存放物品，这个储物柜又分了很多小的储物箱。每个储物箱都只能放一件合适的东西，但你有两件东西，那怎么办呢？那我们就得向储物柜请求两个储物箱的位置。等到储物柜给你开好两个箱门时，你便可将东西存放起来。这大致上就是计算机内存的工作原理。

储物柜

2.1.2 数组

数组

但我们这节介绍数组，我们就举一个例子去讲解数组的存储方式。比如说你和室友去老食堂吃饭，现在只值军训期间，吃饭的人会非常多，你们转完了整个一层二层之后发现有一个桌子只坐了对面两人，于是乎你去问人家你们旁边还有人吗？人家要说没有你们就赶紧放下具有你们标志的东西就跑去买饭。买好之后正吃着饭又来了一个刚上完课的室友，于是乎你们得三人坐在一起，本来等旁边两人吃完了室友就可以坐下了，但是旁边的一直就吃个没停，那么我们就要重新寻找一个可以容纳三人的桌子，等找到之后你们就可以愉快的吃饭了！但如果再来一个和对象刚刚分开的室友，那你们就得炮轰他之后再次转移，真是吃饭都吃不安宁。同样的，在数组中添加新的元素也很麻烦，数组必须保证是一段连续的内存空间，如果这个空间不够用，那么就得需要重新申请，这样就很麻烦。有没有解决办法呢？是有的！如果你有能力承包整个餐厅的话，那么整个餐厅的桌子都是你的，你可以带上你的室友，你的对象，你对象的对象，你对象的对象......按顺序就坐。当然坐不满的话显然浪费了公共资源，如果不够坐的话你还得去承包新食堂用视频连线吃饭。如果你不想这样，那么就得请链表出山了！

2.1.3 链表

链表

举个简单例子在接力赛跑中，400米并没有找1000人（假设1000人的队伍有400米）去排队，然后到达终点。而现实并不是这样，如果是双人接力的话，那么安排两人（一个在起点，一个在跑道中央），那么就需要告诉起点的人，你的接力的人在哪里，才能将接力棒传给下一个人，但如果是四人接力，那么我们就得分别告诉每一个接力的人，它的下一个位置应在哪里。这个例子应该能够理解链表的存储方式，只要有足够的内存空间，就能为链表分配内存。

2.1.4 优缺点

但数组的缺点就很明显，就是上面所说的不好插入新元素，要么得等，要么就得重新申请。很麻烦，大O表示法为O(n)。链表这块就非常的容易，只需要保存到前一个元素中，就把新元素插入到了链表中。大O表示法为O(1)。

删除元素时，应选择哪个方式更好呢？这个问题留给你们思考。（留言哦~）

2.2 选择排序

对数组和链表有了整体的了解之后，就可以了解选择排序算法了。

2.2.1 选择排序的原理

还是用生活中的例子来解释选择排序的原理。我们都是老网抑云了，当我们听每首歌时，网易云后台都会收集每首歌的播放次数（当然我没有在网易云工作，纯属猜测，只是想举个栗子）。于是乎程序员需要对每一个用户喜爱播放的歌曲次数由多到少的进行排列，很容易想到的就是我再弄一个列表过来，每一次遍历这个次数列表，找出第一多的，放到我的新列表中去，然后在遍历次数列表，找出第二多，然后保存在新列表，循环往复，最后，我得到了一个有序列表（网易云员工应该不会这么排序，应该够程序员辞职好几回了）。

播放列表

2.2.2 代码实现

废话不多说，直接上代码。（代码都是编译通过且得出正确结果的，如果什么更好的写法的话，可以给我留言哦~）

选择排序顺序结构

/*

 定义一个方法：取出数组中的最小值的索引

 数组为int型数组

 */

    private static int GetSmallValue(List<Integer> arr)

    {

        //定义一个变量用于接受数组中第一个值，这个值以后用来返回数组中最小的值

        int smallest = arr.get(0);

        //定义一个变量用来存储数组中第一个值的索引，这个变量以后用来接收数组中最小值的索引

        int smallestIndex = 0;

        //遍历数组

        for(int i = 1 ; i < arr.size() ; i++)

        {

            //如果数组中的某一个元素小于我们最初定义的值，那么我们要修改最小值变量

            if(arr.get(i) < smallest)

            {

                smallest = arr.get(i);

                //赋值最小值索引

                smallestIndex = i;

            }

        }

        return smallestIndex;

    }

    /*

 选择排序:

 每次执行获取数组最小值的方法，选出数组中最小的那个值之后，然后插入到新的数组中，

 从而可以得到新的有序数组

 */

    private static int[] SelectSort(Integer[] arr)

    {

        List<Integer> list = Arrays.asList(arr);

        List arrList = new ArrayList<>(list);

        System.out.println(arrList.size());

        int[] newArr = new int[arr.length];

        //执行获取最小值的方法，插入到新数组中

        for(int i = 0; i<arr.length; i++)

        {

            int smallest = GetSmallValue(arrList);

            newArr[i] = (int) arrList.get(smallest);

            arrList.remove(smallest);

        }

        return newArr;

    }

2.2.3 运行时间

我们来分析一下这个排序算法的运行时间，我们首先需要对列表进行一次简单查找（上一节的傻找），它的运行时间为O(n)。你要找完列表的所有大，那么你需要执行n次。需要的总时间就很容易得到为O(n x n) = O(n²)。这样的算法有点简单粗暴，当然这能说明问题。具体怎么得出我也不会，留给你们吧~你们一定比我聪明!