Java排序算法-持续更新中

paixusuanfa

一、比较排序

1.1 交换排序

数组两元素交换位置

public class ArrayUtil {

    /**
     * 交换数组中的两个元素
     * @param array 数组
     * @param ele1Idx 元素1的索引下标
     * @param ele2Idx 元素1的索引下表
     */
    public static void swap(int[] array, int ele1Idx, int ele2Idx) {
        int tmp = array[ele1Idx];
        array[ele1Idx] = array[ele2Idx];
        array[ele2Idx] = tmp;
    }
}

1.1.1 冒泡排序

public class BubbleSort {

    public static void main(String[] args) {
        int[] nums = {12, 34, 11, 98, 56, 49, 21, 29, 19};
        System.out.println("排序前: " + Arrays.toString(nums));
        new BubbleSort().bubbleSort(nums);
        System.out.println("排序后: " + Arrays.toString(nums));
    }

    private void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    ArrayUtil.swap(nums, j, j + 1);
                }
            }
        }
    }
}

在这里插入图片描述

1.1.2 快速排序

public class QuickSort {

    public static void main(String[] args) {
        int[] nums = {12, 34, 11, 98, 56, 49, 21, 29, 19};
        System.out.println("排序前: " + Arrays.toString(nums));
        new QuickSort().quickSort(nums, 0, nums.length - 1);
        System.out.println("排序后: " + Arrays.toString(nums));
    }

    private void quickSort(int[] nums, int start, int end) {
        if (start > end) return;
        int i = start, j = end, base = nums[start];
        while (i < j) {
            while (j >= 0 && nums[j] >= base) j--;
            while (i < j && nums[i] <= base) i++;
            if (i < j) {
                ArrayUtil.swap(nums, i, j);
            }
        }
        ArrayUtil.swap(nums, start, i);
        quickSort(nums, start, i - 1);
        quickSort(nums, i + 1, end);
    }
}

在这里插入图片描述

1.2 插入排序

1.2.1 简单插入排序

public class InsertionSort {

    public static void main(String[] args) {
        int[] nums = {12, 34, 11, 98, 56, 49, 21, 29, 19};
        System.out.println("排序前: " + Arrays.toString(nums));
        new InsertionSort().insertionSort(nums);
        System.out.println("排序后: " + Arrays.toString(nums));
    }

    private void insertionSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int j, temp = nums[i];
            for (j = i; j > 0 && nums[j - 1] > temp; j--) {
                nums[j] = nums[j - 1];
            }
            nums[j] = temp;
        }
    }
}

在这里插入图片描述

1.2.2 希尔排序

public class ShellSort {

    public static void main(String[] args) {
        int[] nums = {12, 34, 11, 98, 56, 49, 21, 29, 19};
        System.out.println("排序前: " + Arrays.toString(nums));
        new ShellSort().shellSort(nums);
        System.out.println("排序后: " + Arrays.toString(nums));
    }

    private void shellSort(int[] nums) {
        // 缩小增量排序
        for (int gap = nums.length / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < nums.length; i++) {
                int j, temp = nums[i];
                for (j = i; j >= gap && nums[j - gap] > temp; j-=gap) {
                    nums[j] = nums[j - gap];
                }
                nums[j] = temp;
            }
        }
    }
}

在这里插入图片描述

1.3 选择排序

1.3.1 简单选择排序

public class SelectionSort {

    public static void main(String[] args) {
        int[] nums = {12, 34, 11, 98, 56, 49, 21, 29, 19};
        System.out.println("排序前: " + Arrays.toString(nums));
        new SelectionSort().selectionSort(nums);
        System.out.println("排序后: " + Arrays.toString(nums));
    }

    private void selectionSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    ArrayUtil.swap(nums, i, j);
                }
            }
        }
    }
}

在这里插入图片描述

1.3.2 堆排序

public class HeapSort {

    public static void main(String[] args) {
        int[] nums = {12, 34, 11, 98, 56, 49, 21, 29, 19};
        System.out.println("排序前: " + Arrays.toString(nums));
        new HeapSort().headSort(nums);
        System.out.println("排序后: " + Arrays.toString(nums));
    }

    private void headSort(int[] nums) {
        int n = nums.length;
        buildHeap(nums, n);
        for (int i = n - 1; i >= 0 ; i--) {
            swap(nums, i, 0);
            heapify(nums, i, 0);
        }
    }

    private void buildHeap(int[] tree, int n) {
        int lastNodeIndex = n - 1;
        int parentNodeIndex = (lastNodeIndex - 1) / 2;
        for (int i = parentNodeIndex; i >= 0; i--) {
            heapify(tree, n, i);
        }
    }

    private void heapify(int[] tree, int n, int i) {
        if (i > n) {
            return;
        }
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int max = i;
        if (l < n && tree[l] > tree[max]) {
            max = l;
        }
        if (r < n && tree[r] > tree[max]) {
            max = r;
        }
        if (max != i) {
            swap(tree, max, i);
            heapify(tree, n, max);
        }
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

在这里插入图片描述

1.4 归并排序

1.4.1 二路归并排序

public class MergeSort {

    public static void main(String[] args) {
        int[] nums = {6, 8, 10, 9, 4, 5, 2, 7};
        new MergeSort().mergeSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    private void mergeSort(int[] arr, int l, int r) {
        if (l == r) return;
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m + 1, r);
    }

    private void merge(int[] arr, int l, int m, int r) {
        int lSize = m - l;
        int rSize = r - m + 1;
        int[] lArr = new int[lSize];
        int[] rArr = new int[rSize];
        // 1.fill in the left sub array
        if (m - l >= 0) System.arraycopy(arr, l, lArr, 0, lSize);
        // 2.fill in the right sub array
        if (r + 1 - m >= 0) System.arraycopy(arr, m, rArr, 0, rSize);
        // 3.merge into the original array
        int i = 0, j = 0, k = l;
        while (i < lSize && j < rSize) {
            if (lArr[i] < rArr[j]) {
                arr[k++] = lArr[i++];
            } else {
                arr[k++] = rArr[j++];
            }
        }
        while (i < lSize) {
            arr[k++] = lArr[i++];
        }
        while (j < rSize) {
            arr[k++] = rArr[j++];
        }
    }
}

在这里插入图片描述

1.4.2 多路归并排序

待更新...

二、非比较排序

2.1 计数排序

public class CountingSort {

    public static void main(String[] args) {
        int[] nums = {12, 34, 11, 98, 56, 49, 21, 29, 19};
        System.out.println("排序前: " + Arrays.toString(nums));
        new CountingSort().countingSort(nums);
        System.out.println("排序后: " + Arrays.toString(nums));
    }

    public void countingSort(int[] nums) {
        int[] mm = getMaxMin(nums);
        int[] cnt = new int[mm[1] - mm[0] + 1];
        for (int num : nums) {
            cnt[num - mm[0]] += 1;
        }
        int idx = 0;
        for (int i = 0; i < cnt.length; i++) {
            for (int j = 0; j < cnt[i]; j++) {
                nums[idx++] = i + mm[0];
            }
        }
    }

    private static int[] getMaxMin(int[] nums) {
        int max = nums[0], min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > max) max = nums[i];
            if (nums[i] < min) min = nums[i];
        }
        return new int[]{min, max};
    }
}

在这里插入图片描述

2.2 桶排序

public class BucketSort {

    public static void main(String[] args) {
        int[] nums = {12, 34, 11, 98, 56, 49, 21, 29, 19};
        System.out.println("排序前: " + Arrays.toString(nums));
        new BucketSort().bucketSort(nums);
        System.out.println("排序后: " + Arrays.toString(nums));
    }

    public void bucketSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }

        // 找出数组中的最大值和最小值
        int[] mm = getMaxMin(nums);

        // 初始化桶数组
        int listSize = mm[1] - mm[0] + 1;
        List<List<Integer>> buckets = new ArrayList<>(listSize);
        for (int i = 0; i < listSize; i++) {
            buckets.add(new ArrayList<>());
        }

        // 将数据分配到桶中
        for (int num : nums) {
            buckets.get(num - mm[0]).add(num);
        }

        // 对每个桶进行排序，这里使用了简单的Insertion Sort
        for (List<Integer> numList : buckets) {
            if (!numList.isEmpty()) {
                Collections.sort(numList);
            }
        }

        // 从桶中收集已排序的数据
        int k = 0;
        for (List<Integer> bucket : buckets) {
            for (Integer value : bucket) {
                nums[k++] = value;
            }
        }
    }

    private static int[] getMaxMin(int[] nums) {
        int max = nums[0], min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > max) max = nums[i];
            if (nums[i] < min) min = nums[i];
        }
        return new int[]{min, max};
    }
}

在这里插入图片描述

2.3 基数排序

public class RadixSort {

    public static void main(String[] args) {
        int[] nums = {12, 34, 11, 98, 56, 49, 21, 29, 19};
        System.out.println("排序前: " + Arrays.toString(nums));
        new RadixSort().radixSort(nums);
        System.out.println("排序后: " + Arrays.toString(nums));
    }

    public void radixSort(int[] nums) {
        int[] mm = getMaxMin(nums);
        int len = String.valueOf(mm[1]).length();
        @SuppressWarnings("unchecked")
        LinkedList<Integer>[] digits = new LinkedList[19];
        for (int powCount = 0; powCount < len; powCount++) {
            for (int num : nums) {
                int idx = (int) Math.abs(num / Math.pow(10, powCount) % 10);
                idx = num >= 0 ? 9 + idx : 9 - idx;
                if (digits[idx] == null) digits[idx] = new LinkedList<>();
                digits[idx].add(num);
            }
            for (int i = 0, j = 0; j < digits.length; j++) {
                while (digits[j] != null && !digits[j].isEmpty()) {
                    nums[i++] = digits[j].removeFirst();
                }
            }
        }
    }

    private static int[] getMaxMin(int[] nums) {
        int max = nums[0], min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > max) max = nums[i];
            if (nums[i] < min) min = nums[i];
        }
        return new int[]{min, max};
    }
}

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/376830.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Linux开发工具】gcc/g++的使用

【Linux开发工具】gcc/g++的使用

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 目录 1.前言2.gcc/g使用方…
阅读更多...
初始Ansible自动化运维工具之playbook剧本编写

初始Ansible自动化运维工具之playbook剧本编写

一、playbook的相关知识 1.1 playbook 的简介 playbook是 一个不同于使用Ansible命令行执行方式的模式&#xff0c;其功能更强大灵活。简单来说&#xff0c;playbook是一个非常简单的配置管理和多主机部署系统&#xff0c;不同于任何已经存在的模式&#xff0c;可作为一个适…
阅读更多...
安装PyInstaller的保姆级教程

安装PyInstaller的保姆级教程

一、安装PyInstaller之前首先要安装Python&#xff0c;小编这里安装的是Python3.9&#xff0c;目前&#xff08;2024/2/6&#xff09;匹配到的最高版本的PyInstaller的版本为6.3.0。需要安装Python的小伙伴可以去这里安装python详细步骤&#xff08;超详细&#xff0c;保姆级&a…
阅读更多...
推荐一款开源的跨平台划词翻译和OCR翻译软件：Pot

推荐一款开源的跨平台划词翻译和OCR翻译软件：Pot

Pot简介 一款开源的跨平台划词翻译和OCR翻译软件 下载安装指南 根据你的机器型号下载对应版本&#xff0c;下载完成后双击安装即可。 使用教程 Pot具体功能如下&#xff1a; 划词翻译输入翻译外部调用鼠标选中需要翻译的文本&#xff0c;按下设置的划词翻译快捷键即可按下输…
阅读更多...
作业2.7

作业2.7

一、填空题 1、在下列程序的空格处填上适当的字句&#xff0c;使输出为&#xff1a;0&#xff0c;2&#xff0c;10。 #include <iostream> #include <math.h> class Magic {double x; public: Magic(double d0.00):x(fabs(d)) {} Magic operator(__const Magic&…
阅读更多...
登录+JS逆向进阶【过咪咕登录】（附带源码）

登录+JS逆向进阶【过咪咕登录】（附带源码）

JS渗透之咪咕登录 每篇前言&#xff1a;咪咕登录参数对比 captcha参数enpassword参数搜索enpassword参数搜索J_RsaPsd参数setPublic函数encrypt加密函数运行时可能会遇到的问题此部分改写的最终形态JS代码&#xff1a;运行结果python编写脚本运行此JS代码&#xff1a;运行结果&…
阅读更多...
开关电源用什么电感

开关电源用什么电感

开关电源用什么电感 电感波形图 我们看图&#xff0c;如下图所示&#xff1a; 图1 电感波形示意图 PWM那张图和inductor那张图&#xff0c;第一张图就是Buck电路图SW引脚的波形&#xff0c;看波形我们知道在t1的时候是vi在t2的时候是0&#xff0c;紧接着电流和电压经过电感以…
阅读更多...
BUUCTF-Real-ThinkPHP]5.0.23-Rce

BUUCTF-Real-ThinkPHP]5.0.23-Rce

漏洞介绍 这个版本容易存在我们都喜欢的rce漏洞&#xff01; 网站为了提高访问效率往往会将用户访问过的页面存入缓存来减少开销。而Thinkphp 在使用缓存的时候是将数据序列化&#xff0c;然后存进一个 php 文件中&#xff0c;这使得命令执行等行为成为可能&#xff01; ThinkP…
阅读更多...
51单片机基础：定时器

51单片机基础：定时器

1.定时器介绍 51单片机通常有两个定时器&#xff1a;定时器 0/1&#xff0c;好一点的可能有定时器3。 在介绍定时器之前我们先科普下几个知识&#xff1a; 1&#xff0c;CPU 时序的有关知识 ①振荡周期&#xff1a;为单片机提供定时信号的振荡源的周期&#xff08;晶振周期或…
阅读更多...
第二十五回 偷骨殖何九叔送丧 供人头武二郎设祭-Numpy数组计算

第二十五回 偷骨殖何九叔送丧 供人头武二郎设祭-Numpy数组计算

何九叔晕倒了&#xff0c;被抬回家里&#xff0c;他对老婆说&#xff0c;我没事&#xff0c;是看到武大郎的情况&#xff0c;明显是中毒身亡&#xff0c;但是又不敢声张&#xff0c;怕西门庆打击报复。九叔的老婆让他送丧的时候拿两块骨头&#xff0c;同前面十两银子一起收着&a…
阅读更多...
操作系统基础：磁盘组织与管理【下】

操作系统基础：磁盘组织与管理【下】

&#x1f308;个人主页&#xff1a;godspeed_lucip &#x1f525; 系列专栏&#xff1a;OS从基础到进阶 ⚖️1 减少延迟时间⚙️1.1 存在延迟时间的原因⚙️1.2 减少延迟的方法&#x1f9ea;1.2.1 交替编号&#x1f9ea;1.2.2 错位命名 ⚙️1.3 总结 ⚖️2 磁盘的管理&#x1f…
阅读更多...
Leetcode刷题笔记题解（C++）：590. N 叉树的后序遍历

Leetcode刷题笔记题解（C++）：590. N 叉树的后序遍历

思路&#xff1a;类似于二叉树的排序&#xff0c;这里需要将子树进行依次递归遍历&#xff0c;前序遍历也与之类似 /* // Definition for a Node. class Node { public:int val;vector<Node*> children;Node() {}Node(int _val) {val _val;}Node(int _val, vector<N…
阅读更多...
蓝桥杯Web应用开发-CSS3 新特性【练习一：属性有效性验证】

蓝桥杯Web应用开发-CSS3 新特性【练习一：属性有效性验证】

练习一&#xff1a;属性有效性验证 页面上有一个邮箱输入框&#xff0c;当你的输入满足邮箱格式时&#xff0c;输入框的背景颜色为绿色&#xff1b;当你的输入不满足要求&#xff0c;背景颜色为红色。 新建一个 index2.html 文件&#xff0c;在其中写入以下内容。 <!DOCTYP…
阅读更多...
2024-02-06（Sqoop）

2024-02-06（Sqoop）

1.Sqoop Apache Sqoop是Hadoop生态体系和RDBMS&#xff08;关系型数据库&#xff09;体系之间传递数据的一种工具。 Sqoop工作机制是将导入或者导出命令翻译成MapReduce程序来实现。在翻译出的MapReduce中主要是对inputformat和outputformat进行定制。 Hadoop生态包括&#…
阅读更多...
python30-Python的运算符结合性和优先级

python30-Python的运算符结合性和优先级

1&#xff09;所有的数学运算都是从左向右进行的&#xff0c;Python 语言中的大部分运算符也是从左向右结合的&#xff0c;只有单目运算符、赋值运算符和三目运算符例外&#xff0c;它们是从右向左结合的&#xff0c;也就是说&#xff0c;它们是从右向左运算的。 2&#xff09…
阅读更多...
怎么理解 Redis 事务

怎么理解 Redis 事务

背景 在面试中经常会被问到&#xff0c;redis支持事务吗&#xff1f;事务是怎么实现的&#xff1f;事务会回滚吗&#xff1f;又是一键三连&#xff0c;我下面分析下&#xff0c;看看能不能吊打面试官 什么是Redis事务 事务是一个单独的隔离操作&#xff1a;事务中的所有命令…
阅读更多...
Spring的学习（上）

Spring的学习（上）

1、Spring的Beans.xml 一个beans.xml示例&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <beans xmlns"http://www.springframework.org/schema/beans"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:sch…
阅读更多...
树莓派Pico入门

树莓派Pico入门

文章目录 1. Pico概述1.1 微处理器1.2 GPIO引脚1.3 MicroPython优点 2. 硬件准备2.1 购买清单2.2 软件需求 3. 安装MicroPython3.1下载固件3.2把固件安装到硬件里3.3补充 4. 第一个程序5. 验证运行效果6. 扩展应用 1. Pico概述 1.1 微处理器 ARM Cortex-M0 (频率 133MHz) 1.…
阅读更多...
代码随想录算法训练营第43天 | 1049.最后一块石头的重量 II + 494.目标和 + 474.一和零

代码随想录算法训练营第43天 | 1049.最后一块石头的重量 II + 494.目标和 + 474.一和零

今日任务 1049. 最后一块石头的重量 II 494. 目标和 474.一和零 1049.最后一块石头的重量 II - Medium 题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 有一堆石头&#xff0c;用整数数组 stones 表示。其中 stones[i] 表示…
阅读更多...
高速接口PCB布局指南（五）高速差分信号布线（三）

高速接口PCB布局指南（五）高速差分信号布线（三）

高速接口PCB布局指南&#xff08;五&#xff09;高速差分信号布线&#xff08;三&#xff09; 1.表面贴装器件焊盘不连续性缓解2.信号线弯曲3.高速信号建议的 PCB 叠层设计4.ESD/EMI 注意事项5.ESD/EMI 布局规则 tips&#xff1a;资料主要来自网络&#xff0c;仅供学习使用。 …
阅读更多...
最新文章

Copyright @ 2022~2023