栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

排序算法之选择排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

排序算法之选择排序

认识时间复杂度 常数时间的操作

一个操作如果和样本的数据量没有关系,每次都是固定时间内完成的操作,就叫做常数操作

例如

​ 因为数组是有序的,我们拿到数组上任意元素的时间都是固定的,这种就是常数操作

反例

​ 因为链表是无序的,我们拿到某一个元素的时间可能是不一样的,这种操作就非常数操作了

算法时间复杂度

时间复杂度为一个算法流程中,常数操作数量的一个指标。常用O(读作big O)来表述。具体来说,先要对一个算法流程非常熟悉,然后再去写出这个算法流程中,发生了多少常熟操作,进而总结出常数操作数量的表达式。

在表达式中,只要高阶项,不要低阶项,也不要高阶项的系数,剩余的部分如果为f(N)那么时间复杂度为O(f(N))。

现在我们已经初步认识了算法的时间复杂度,接下来我们就先了解排序算法

选择排序

流程

每次遍历一个范围的数组,第一次遍历n次找出一个最小的数字和第0个做交换,第二次遍历n-1(排除第一个)次,找出剩下的元素最小的和第1个做交换……重复操作,这个每次都要循环一次数组某个范围的元素作比较,并作出交换操作,不难看出选择排序是O(N²)的时间复杂度

代码如下

package com.yuan.struck_data.sort;


public class SelectSortTest {

    
    public static void selectSort(int[] arr) {
        // 如果数组为空或者只有一个元素那么直接返回
        if (arr == null || arr.length < 2) {
            return;
        }
        // 先做一次 for遍历arr
        for (int i = 0; i < arr.length; i++) {
            // 假设每次第一个元素是最小的
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                // 如果遇到比当前下标小的数字就互换下标
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            // 交换
            swap(arr, i, minIndex);
        }
    }

    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 主方法
    public static void main(String[] args) {
        // 测试数组
        int[] arr = {12, 123, 1, 12, 42, 543, 64, 3423, 24, 241, 123, 54, 47, 787};
        // 调用排序
        selectSort(arr);

        for (int i : arr) {
            System.out.println(i);
        }
    }
}

我是本篇的小编⚪⚪,大家工作或者开发中遇到Bug需要帮助,欢迎加wx:xmzl1988

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/961936.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号