数据结构与算法—选择排序(Java实现)

选择排序

package com.uplooking.bigdata.datastructure;
import java.util.Arrays;
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {8, -2, 3, 9, 0, 1, 7, 6};
        System.out.println("排序前:" + Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
    /**
     * 选择排序:
     *    每次从数组中找到一个最小的元素放到前面
     *    或者从i位置开始往后找,找一个最小的元素和i位置元组进行交换
     *       src:{8, -2, 3, 9, 0, 1, 7, 6} 假如数组长度为n
     *    第一趟:比较n-1
     *      {[-2], [8], 3, 9, 0, 1, 7, 6}
     *    第二趟:比较n-2
     *      {-2, [0], [8], 9, [3], 1, 7, 6}
     *    第三趟:比较n-3
     *      {-2, [0], [1], 9, [8], [3], 7, 6}
     *    第四趟:比较n-4
     *      {-2, 0, 1, [3], [9], [8], 7, 6}
     *    第五趟:比较n-5
     *      {-2, 0, 1, 3, [6], [9], [8], [7]}
     *    第六躺:比较n-6
     *      {-2, 0, 1, 3, 6, [7], [9], [8]}
     *    第七趟:比较n-7
     *      {-2, 0, 1, 3, 6, 7, 8, 9}
     *    比较的次数(n-1) + (n-2) + ... + 2 + 1=(n-1 + 1) * (n-1)/2 = n*(n-1)/2 = n^2/2 - n/2
     *    时间复杂O(n^2)
     *
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[i] > arr[j]) {//交换
                    swap(arr, i, j);
                }
            }
        }
    }
    private static void swap(int[] arr, int i, int j) {
        /*int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;*/
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}
测试
排序前:[8, -2, 3, 9, 0, 1, 7, 6]
排序后:[-2, 0, 1, 3, 6, 7, 8, 9]

时间复杂度分析

1.时间复杂度为:O(n^2)
比较的次数(n-1) + (n-2) + ... + 2 + 1=(n-1 + 1) * (n-1)/2 = n*(n-1)/2 = n^2/2 - n/2
2.数据排列顺序是有可能被改变的,这取决于在比较是的比较符号(>还是>=),所以其是不稳定的排序算法。

原文发布于微信公众号 - 编程坑太多(idig88)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏偏前端工程师的驿站

Java魔法堂:解读基于Type Erasure的泛型

一、前言                               还记得JDK1.4时遍历列表的辛酸吗?我可是记忆犹新啊,那时因项目需求我从C#转身到Jav...

2265
来自专栏夏时

PHP 特色:可变变量

1374
来自专栏HTML5学堂

Math对象面试题目

HTML5学堂:JavaScript的Math对象的命令虽然简单,但是逻辑性要求比较高,它可以辅助开发者实现一些JavaScript复杂效果,这就要求大家有一定...

2485
来自专栏cs

c++面向对象的一些问题1.0

构造函数 特殊的成员函数,给对象的初始化,不需要用户调用,建立对象时,自动执行 它的函数名字与类相同,可以重载,没有返回值和函数类型。 如果不写构造函...

30110
来自专栏HTML5学堂

函数声明与表达式的区别

HTML5学堂:函数有不同的定义方法,一种是函数声明,另一种是函数表达式,那么这两种有何区别呢? 函数声明的基本语法 function functionName...

3424
来自专栏Java开发者杂谈

java finally深入探究

When---什么时候需要finally: 在jdk1.7之前,所有涉及到I/O的相关操作,我们都会用到finally,以保证流在最后的正常关闭。jdk1.7之...

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

由javascript中"匿名函数调用写法"引出的一些东东

匿名函数自动调用的三种写法如下: var f1 = function(){alert("f1");}(); (function(){alert("f2");...

2176
来自专栏偏前端工程师的驿站

Java魔法堂:解读基于Type Erasure的泛型

一、前言                               还记得JDK1.4时遍历列表的辛酸吗?我可是记忆犹新啊,那时因项目需求我从C#转身到Jav...

2168
来自专栏浪淘沙

java初级笔记----final、static、匿名对象、内部类

一、final 1、final可以用来修饰类,方法,成员变量, 2、final修饰类不可以被继承,但是可以继承其他类。 3、final修饰的方法不可...

1593
来自专栏练小习的专栏

xcode编译的时候陷入无限indexing的问题笔记

“Swift因为有类型推断,一般来说你很少需要写类型标注。如果你在声明常量或者变量的时候赋了一个初始值,Swift可以推断出这个常量或者变量的类型”,而事实上,...

1805

扫码关注云+社区

领取腾讯云代金券