一个Java小白通向数据结构算法之旅(5) - 选择排序

前言

今天去东鹏特饮面试,我很生气。面的技术岗,卷子竟然是营销的。浪费了我一晚上的时间,害得我差点没赶上地铁的末班车。你能敢相信?这是面Java的试卷。生气归生气,学习还是要继续的。

image.png


什么是选择排序?

选择排序是不稳定的排序。每一趟从待排序的数据元素中选出最小(或者最大)的一个元素放在已排好序的数列的最后,直到全部待排序的数据排完。


选择排序和冒泡排序的区别

  • 选择排序相对于冒泡来说,它不是每次发现逆序都要进行交换。
  • 选择排序改进了冒泡排序,将必要的交换次数从O(N^2)减少到O(N)。但是比较的次数还是O(N^2)
  • 选择排序在为大记录量的排序中提出了一个非常重要的改进。因为这些记录需要在内存中移动,这就使交换的时间和比较的时间相比起来,交换的时间更为很重要。在Java语言中不是这种情况,Java中只是改变了引用位置,而实际对象的位置并没有发生改变。

提取思想

  • 进行选择排序就是先遍历所有的数字扫描一趟,从中挑出最小的数据。最小的数字和队列最左边的数字进行交换位置,即站到0号位置。现在最左端的数字都是有序的,不需要再进行交换位置了。
  • 在这个算法中,有序的数字都排列在队列的最左边,而冒泡排序则是排序在队列最右边。
  • 再次遍历数据队列时,就从第1号位置开始了,还是寻找剩下队列中最小的数据,然后和第1号位置的数字进行交换。重复以上过程,一直持续到所有的队员都排定。

手写代码

public class SelectSortDemo {
    public static int[] a = { 11, 20, 5, 4, 8, 14, 2, 10, 20, 9 };

    public static void main(String[] args) {
        sort();
        display();
    }

    public static void sort() {
        int count = a.length;

        for (int i = 0; i < count - 1; i++) {
            int min = i;

            for (int k = i + 1; k < count; k++) {
                if (a[k] < a[min]) {
                    min = k;
                }
            }

            if (min != i) {
                swap(min, i);
            }
        }
    }

    public static void swap(int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

    public static void display() {
        int count = a.length;

        for (int i = 0; i < count; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println("");
    }
}
  • 运行结果,看输出。

image.png


效率问题

选择排序和冒泡排序都执行了相同次数的比较: N * (N - 1) / 2。对于10个数据项,需要45次比较。然而10个数据项只需要少于10次交换。选择排序和冒泡排序一样运行了O(N^2)时间。但是,选择排序会更快。因为它进行的交换少的很。当N值较小的时候,如果交换的时间级要比比较的时间级大的多时候,选择排序是相当快的。


尾言

今天女朋友跟我说,面试的时候不要带任何主观色彩情绪。女朋友说的很对,我需要再耐心一点,少一点浮躁,多一点沉淀。实话说,我是一个很爱抱怨的人,可是这往往是弱者的表现。在成为强者的路上,我缺的不仅仅是知识,更多的是如何做人。时间也不早了,晚安,地球人。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

寻找中位数

LeetCode 295. Find Median from Data Stream 设计一个数据结构,该数据结构动态维护一组数据,且支持如下操作: 1.添...

12830
来自专栏青玉伏案

PHP精选数组函数

编程怎么能少的了数组呢,以下是学习PHP时常用的数组处理函数。在编程中要遵循一个原则就是DRY(Don`t Repeat Yourself)原则,PHP中有大...

24480
来自专栏IMWeb前端团队

神奇运算符

每一门编程语言的设计都离不开运算符,我们写的每一行代码基本也少不了它们,这篇文章就让我们一起来了解一下这个无处不在的小伙伴的应用和小技巧吧~~ ~ 按位取反 字...

21890
来自专栏较真的前端

看到这题后还敢说自己精通Promise吗?

18520
来自专栏程序人生 阅读快乐

JavaScript函数式编程

JavaScript 是近年来非常受瞩目的一门编程语言,它既支持面向对象编程,也支持函数式编程。本书专门介绍JavaScript函数式编程的特性。

7320
来自专栏Phoenix的Android之旅

重构 - 完全不用 if-else 可能吗?

上次那篇重构-为什么 if-else 不是好代码 说到代码中的 if-else会随着代码量的增加,在迭代的过程中变的越来越难以维护, 然后用工厂模式的思路可以把...

9420
来自专栏AlgorithmDog的专栏

靠默契保证的私有制:Python 中的私有

人类文明开化以来,私有制似乎是人类历史的主流在西方国家,“私有财产神圣不可侵犯” 是很多资本主义国家的立国原则之一。在我国,“私有财产不可侵犯” 也...

21080
来自专栏大史住在大前端

javascript基础修炼(2)——What's this(上)

this是javascript关键字之一,是javascript能够实现面向对象编程的核心概念。用得好能让代码优雅高端,风骚飘逸,用不好也绝对是坑人坑己利器。我...

9710
来自专栏一个会写诗的程序员的博客

React极简教程: Hello,World!React简史React安装Hello,World

A programming paradigm is a fundamental style of computer programming. There are...

9310
来自专栏向治洪

Scala入门笔记

Scala入门 Scala简介 ps:在最新的薪资调查中,Scala程序员的工资是平均最高的Scala工资。 Scala是一门多范式的编程语言,一种类似ja...

22370

扫码关注云+社区

领取腾讯云代金券