选择排序就这么简单@慕课网原创_慕课网

tags: 算法

选择排序就这么简单

从上一篇已经讲解了冒泡排序了，本章主要讲解的是选择排序，希望大家看完能够理解并手写出选择排序的代码，然后就通过面试了！如果我写得有错误的地方也请大家在评论下指出。

选择排序介绍和稳定性说明

来源百度百科：

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

上面提到了选择排序是不稳定的排序方法，那我们的冒泡排序是不是稳定的排序方法呢？稳定的意思指的是什么呢？

判断某排序算法是否稳定，我们可以简单理解成：排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同

如果相同，则是稳定的排序方法。
如果不相同，则是不稳定的排序方法

如果排序前的数组是[3,3,1]，假定我们使用选择排序的话，那第一趟排序后结果就是[1,3,3]。这个数组有两个相同的值，它俩在array[0]和array[1]，结果经过排序，array[0]的跑到了array[2]上了。

那么这就导致：2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序不相同，因此，我们就说它是不稳定的

再回到上面的问题，上一篇说讲的冒泡排序是稳定的，主要原因是：俩俩比较的时候，没有对相等的数据进行交换(因为没必要)。因此它不存在2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序不相同。

那么稳定排序的好处是什么？

参考知乎回答@独行侠的回答：

如果我们只对一串数字排序，那么稳定与否确实不重要，因为一串数字的属性是单一的，就是数字值的大小。但是排序的元素往往不只有一个属性，例如我们对一群人按年龄排序，但是人除了年龄属性还有身高体重属性，在年龄相同时如果不想破坏原先身高体重的次序，就必须用稳定排序算法.

很清晰的指出，只有当在“二次”排序时不想破坏原先次序，稳定性才有意义

参考资料：

一、第一趟排序

它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排完

首先，我们创建数组，找到它最大的值(这就很简单了):


    int[] arrays = {2, 3, 1, 4, 3, 5, 1, 6, 1, 2, 3, 7, 2, 3};

    //假定max是最大的
    int max = 0;

    for (int i = 0; i < arrays.length; i++) {
        if (arrays[i] > max) {
            max = arrays[i];
        }
    }

随后这个最大的数和数组末尾的数进行交换：


    //使用临时变量，让两个数互换
    int temp;
    temp = arrays[11];
    arrays[11] = arrays[13];
    arrays[13] = temp;

那么经过第一趟排序，我们的最大值已经到了数组的末尾了。

二、第二趟排序

再次从数组获取最大的数(除了已经排好的那个）：


    int max2 = 0;
    for (int i = 0; i < (arrays.length - 1); i++) {
        if (arrays[i] > max2) {
            max2 = arrays[i];
        }
    }

    System.out.println(max2);

再将获取到的最大值与数组倒数第二位交换：


    temp = arrays[7];
    arrays[7] = arrays[12];
    arrays[12] = temp;

经过第二次排序，已经能够将数组最大两个数进行排序了

三、代码简化

从前两趟排序其实我们就可以摸出规律了：

一个数组是需要n-1趟排序的(因为直到剩下一个元素时，才不需要找最大值)
每交换1次，再次找最大值时就将范围缩小1
查询当前趟数最大值实际上不用知道最大值是多少(上面我查出最大值，还要我手动数它的角标)，知道它的数组角标即可，交换也是根据角标来进行交换

第一趟：遍历数组14个数，获取最大值，将最大值放到数组的末尾[13]
第二趟：遍历数组13个数，获取最大值，将最大值放到数组倒数第二位[12]

....

数组有14个数，需要13趟排序。


    //记录当前趟数的最大值的角标
    int pos ;

    //交换的变量
    int temp;

    //外层循环控制需要排序的趟数
    for (int i = 0; i < arrays.length - 1; i++) {

        //新的趟数、将角标重新赋值为0
        pos = 0;

        //内层循环控制遍历数组的个数并得到最大数的角标
        for (int j = 0; j < arrays.length - i; j++) {

            if (arrays[j] > arrays[pos]) {
                pos = j;
            }

        }
        //交换
        temp = arrays[pos];
        arrays[pos] = arrays[arrays.length - 1 - i];
        arrays[arrays.length - 1 - i] = temp;

    }

    System.out.println("公众号Java3y" + arrays);

四、选择排序优化

博主暂未想到比较好的优化方法，如果看到这篇文章的同学知道有更好的优化方法或者代码能够写得更好的地方，欢迎在评论下留言哦！

查到的这篇选择排序优化方法，感觉就把选择排序变了个味，大家也可以去看看：

他是同时获取最大值和最小值，然后分别插入数组的首部和尾部(这跟选择排序的原理好像差了点，我也不知道算不算)
http://www.cnblogs.com/TangMoon/p/7552921.html

五、扩展阅读

C语言实现

          int findMaxPos ( int arr[], int n)
        {
            int max = arr[0];
            int pos = 0; 
            for (int i = 1; i < n; i++) {
                if (arr[i] > max) {
                    max = arr[i];
                    pos = i;
                }
            }
            return pos;
        }

        void selectionSort ( int arr[], int n)
        {
            while (n > 1) 
            {
                int pos = findMaxPos(arr, n);
                int temp = arr[pos];
                arr[pos] = arr[n - 1];
                arr[n - 1] = temp;
                n--;//
            }
        }

        int main ()
        {
            int arr[] = {5, 32, 7, 89, 2, 3, 4, 8, 9};
            selectionSort(arr, 9);
            for (int i = 0; i < 9; i++)
                cout << arr[i] << endl;
        }