选择排序就这么简单

选择排序就这么简单

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

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

来源百度百科:

选择排序(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个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序不相同。

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

  • 参考知乎回答@独行侠的回答:

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

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

参考资料:

  • https://www.zhihu.com/question/46809714/answer/281361290
  • http://tieba.baidu.com/p/872860935
  • http://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html

一、第一趟排序

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

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

    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;
        }

原文发布于微信公众号 - Java3y(gh_085b56c42174)

原文发表时间:2018-03-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:数组

12970
来自专栏noteless

[八]基础数据类型之Double详解

这些属性,看过浮点数简介的话,可以很清晰的理解,再次说明下,但凡本人的系列文章,全部都是有顺序的

1.2K10
来自专栏Java 源码分析

八大排序算法

​ 八大排序算法是面试经常考到的,尤其是快排,希尔排序和归并也是经常会让写代码的题目,其实只要用一句话说明了他们的原理我们写起代码就没那么困难。 冒泡排序...

54130
来自专栏python学习之旅

算法笔记(六):计数排序和基数排序

        这里我是按自己的理解去实现的,时间复杂度和空间复杂度和算法导论上的可能不一样,感兴趣的话参考下就行,感觉最重要的还是算法思想。根据算法性能去实现...

26120
来自专栏Danny的专栏

【J2SE快速进阶】——递归算法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

10210
来自专栏向治洪

算法笔记之排序

最近在看《算法笔记》,如果单从算法来说,这本书真正做到了短小精悍,首先以排序入题,那么我们今天也来说说排序。 排序 将一堆杂乱无章的元素按照某种规则有序排列的过...

238100
来自专栏后端技术探索

视觉直观感受 7 种常用的排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

11420
来自专栏菩提树下的杨过

数据结构与算法C#版笔记--排序(Sort)-下

5、堆排序(HeapSort) 在接触“堆排序”前,先回顾一下数据结构C#版笔记--树与二叉树 ,其中提到了“完全二叉树”有一些重要的数学特性: ? 上图就是一...

21650
来自专栏nnngu

算法01 七大排序之:冒泡排序和快速排序

排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列;老师查看上课出勤情况时,会按学生学号顺序点名;高考录取时,会按成绩总分降序依次录取等。排序是数...

37870
来自专栏Python数据科学

十大经典排序算法(Python代码实现)

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

42310

扫码关注云+社区

领取腾讯云代金券