【Java基础】 几种简单的算法排序

简介: 几种简单的JAVA算法排序

学习Java中的排序算法不仅有助于理解数据结构与算法的基本原理,还能提升解决实际问题的能力。排序算法是计算机科学中的重要组成部分,它们在数据处理、数据库管理、机器学习等多个领域都有着广泛的应用。通过学习不同的排序算法,可以加深对算法复杂度、稳定性等概念的理解,并能够根据具体问题选择或设计最合适的排序方法。


下面介绍几种JAVA中简单的算法排序



1.冒泡排序

冒泡排序思路易于理解,是学习排序算法时的一个很好的入门点。这种排序算法的基本思想是每次比较相邻的两个元素,如果前一个元素大于后一个元素,则交换它们的位置。这样一轮比较下来,最大的元素就会被交换到数组的末尾。然后再进行下一轮比较,直到整个数组有序。


public class Main {
    public static void main(String[] args) {
       int [] arr={-3,3,55,12,32,65,78};
       //冒泡排序
        bubbleSort(arr);
        for (int nNum:arr){
            System.out.println(nNum);
        }
    }
    public static void bubbleSort(int []arr){
        //临时变量,用于交换元素
        int temp;
        //标志位,用来判断有没有交换
        boolean flag;
        //外层循环,限制循环次数
        for (int i = 0;i < arr.length - 1;i++){
            flag = false;
            //内层控制元素相邻变换
            for(int j = 0;j< arr.length -1 -i;j++){
                if(arr[j] > arr[j + 1]){
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag){
                break;
            }
        }
    }
}


上述代码中,调用bubbleSort方法,首先定义了一个临时变量temp和一个标志位flag。外层循环控制排序的轮数,每轮比较相邻的元素,如果前一个元素大于后一个元素,则交换它们的位置。一轮比较下来,最大的元素就会被交换到数组的末尾。内层循环控制每轮比较的次数,每次比较相邻的两个元素,如果前一个元素大于后一个元素,则交换它们的位置。如果一轮比较中没有发生任何交换,说明数组已经有序,此时可以提前结束排序。




2.选择排序

选择排序是一种简单直观的排序算法,无论什么数据进去都是 O (n²) 的时间复杂度。 所以用到它的时候,数据规模越小越好。 唯一的好处可能就是不占用额外的内存空间了吧。

选择排序的基本思想是:首先在未排序序列中找到最小(或最大)元素,将其放到排序序列的起始位置,然后再从剩余的未排序元素中继续寻找最小(或最大)元素,并将其放到已排序序列的末尾。这一过程重复进行,直到所有元素均排序完毕。


public class Main {
    public static void main(String[] args) {
       int [] arr={50,89,0,-22,67};
       //选择排序
        selectionSort(arr);
        for (int nNum:arr){
            System.out.println(nNum);
        }
    }

    public static void selectionSort(int []arr){
        for (int i = 0;i< arr.length -1;i++)
        {
            int minIndex = i;
            for (int j = i  + 1;j < arr.length;j++){
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            if (minIndex != i){
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }
}


上述代码中调用selectionSort方法,定义了变量minIndex,用于记录最小元素的下标。外层循环控制排序的轮数,每轮比较相邻的元素,找到最小元素的下标minIndex。

内层循环从i+1开始遍历未排序序列,找到最小元素的下标minIndex。如果minIndex不等于i,说明找到了更小的元素,需要交换位置。



3.快速排序

快速排序是一种高效的排序算法,其基本思想是采用分治法的思想,将待排序的序列分为两个子序列,其中一个子序列的所有元素都比另一个子序列的元素小,然后对这两个子序列分别进行排序,最终得到有序序列。


public class Main {
    public static void main(String[] args) {
       int [] arr={22,11,-12,100,89};
       //快速排序
        quickSort(arr,0,arr.length-1);
        for (int nNum:arr){
            System.out.println(nNum);
        }
    }

    public static void quickSort(int [] arr,int low,int high){
        if (low < high){
            int prvot =partition(arr,low,high);
            quickSort(arr,low,prvot - 1);
            quickSort(arr,prvot + 1,high);
        }
    }

    public static int partition(int [] arr,int low,int high){
        int prvot = arr[low];
        while (low < high){
            while (low < high && arr[high] >= prvot){
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[high] <= prvot){
                low++;
            }
            arr[high] = arr[low];
            arr[low] = prvot;
        }
        return low;
    }
}


上述代码调用两个方法,在partition方法中,首先选取一个基准元素pivot,通常选择第一个元素或者最后一个元素。然后从左到右遍历序列,将小于pivot的元素放到左边,大于pivot的元素放到右边。最后返回基准元素的下标。在quickSort方法中,首先判断low是否小于high,如果是,则调用partition方法获取基准元素的下标prvot。然后对左右两个子序列分别递归调用quickSort方法。



4.插入排序

插入排序是一种简单直观的排序算法,其基本思想是将一个无序序列分为已排序和未排序两部分,每次从未排序部分取出一个元素,将其插入到已排序部分的正确位置上。


public class Main {
    public static void main(String[] args) {
       int [] arr={-6,12,89,22,-8};
       //插入排序
        insertionSort(arr);
        for (int nNum:arr){
            System.out.println(nNum);
        }
    }

    public static void insertionSort(int [] arr){
        for (int i = 1; i < arr.length; i++){
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key){
                arr[j +1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}



5.希尔排序

希尔排序是一种改进的插入排序算法,它的基本思想是将待排序的数组按照一定的间隔进行分组,对每组使用插入排序算法进行排序,然后缩小间隔,再对分组进行排序,直到间隔为1为止。

逐渐减小间隔大小的方法有助于提高排序过程的效率,可以减少比较和交换的次数。这是希尔排序算法的一个关键特点。


import java.util.Arrays;

public static void Main(String[] args) {
        int[] arr = {5, 2, 8, 3, 1, 6};
        int[] expectedArr = {1, 2, 3, 5, 6, 8};
        shellSort(arr);
        System.out.println("arr = " + Arrays.toString(arr));
        Assertions.assertArrayEquals(expectedArr, arr);
}
    public static void shellSort(int[] arr) {
        int n = arr.length;
        // 初始化间隔(gap)的值,它决定了每次迭代中子数组的大小
        // 从数组长度的一半开始作为初始间隔值,gap就是分割的子数组数量
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 循环从间隔值开始,遍历数组直到数组的末尾;代表循环所有的子数组
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                // 将当前元素 arr[j] 的值替换为前一个元素 arr[j - gap] 的值。
                // 通过这个操作,将较大的元素向后移动,为当前元素腾出位置
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }


代码中的shellSort方法接收一个整数数组作为参数,对其进行希尔排序。在main方法中,定义了一个待排序的数组arr和一个预期排序后的数组expectedArr,然后调用shellSort方法对arr进行排序,并使用Assertions.assertArrayEquals方法检查排序后的结果是否与预期相符。


6.计数排序

计数排序是一种非基于比较的排序算法,它适用于当待排序的元素是确定的、可数的,并且元素的范围事先已知的情况下。计数排序的基本思想是对每一个输入元素确定小于它的元素个数,这样就可以直接把输入元素放到它在输出数组中的位置上。

计数排序是一种简单而有效的排序算法,特别适用于整数序列,其性能优于比较排序算法,但在应用上有一定的局限性。


import java.util.Arrays;

public static void Main(String[] args) {
        int[] arr = {5, 2, 6, 8, 3, 1, 6, 5, 12};
        int[] expectedArr = {1, 2, 3, 5, 5, 6, 6, 8, 12};
        countingSort(arr);
        System.out.println("arr = " + Arrays.toString(arr));
        Assertions.assertArrayEquals(expectedArr, arr);
}
    public static void countingSort(int[] arr) {
        int n = arr.length;
        // 取出数组中最大值
        int max = getMax(arr);
        int[] count = new int[max + 1];
        // 统计每个元素出现的次数
        for (int i = 0; i < n; i++) {
            count[arr[i]]++;
        }
        // 计算每个元素在有序序列中的位置
        for (int i = 1; i <= max; i++) {
            // 因为count包含了每个数据出现的次数,所以从小到大,
            // 逐个往前加得到就是原数组中每个元素在有序序列中应有的位置
            count[i] += count[i - 1];
        }
        // 输出有序序列
        int[] sortedArr = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int item = arr[i];//元素
            int itemPos = count[item];// 元素在有序数组中的位置
            sortedArr[itemPos - 1] = item; // 将元素填入有序数组
            count[item]--;
        }
        // 将有序序列复制回原数组
        System.arraycopy(sortedArr, 0, arr, 0, n);
    }

    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }


上述代码中的countingSort方法接受一个整数数组作为参数,并对其进行排序。首先,它找到数组中的最大值,然后创建一个长度为最大值加1的计数数组。接下来,它遍历输入数组,统计每个元素出现的次数,并将结果存储在计数数组中。然后,它计算每个元素在有序序列中的位置,并将结果存储回计数数组。最后,它使用计数数组中的位置信息将元素填入一个新的有序数组,并将有序数组复制回原数组。

getMax方法用于获取数组中的最大值。它遍历数组,找到最大的元素并返回。



目录
打赏
0
2
4
0
60
分享
相关文章
探究‘公司禁用 U 盘’背后的哈希表算法与 Java 实现
在数字化办公时代,信息安全至关重要。许多公司采取“禁用U盘”策略,利用哈希表算法高效管理外接设备的接入权限。哈希表通过哈希函数将设备标识映射到数组索引,快速判断U盘是否授权。例如,公司预先将允许的U盘标识存入哈希表,新设备接入时迅速验证,未授权则禁止传输并报警。这有效防止恶意软件和数据泄露,保障企业信息安全。 代码示例展示了如何用Java实现简单的哈希表,模拟公司U盘管控场景。哈希表不仅用于设备管理,还在文件索引、用户权限等多方面助力信息安全防线的构建,为企业数字化进程保驾护航。
Java 实现局域网电脑屏幕监控算法揭秘
在数字化办公环境中,局域网电脑屏幕监控至关重要。本文介绍用Java实现这一功能的算法,涵盖图像采集、数据传输和监控端显示三个关键环节。通过Java的AWT/Swing库和Robot类抓取屏幕图像,使用Socket进行TCP/IP通信传输图像数据,并利用ImageIO类在监控端展示图像。整个过程确保高效、实时和准确,为提升数字化管理提供了技术基础。
84 15
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
75 16
企业局域网监控软件中 Java 优先队列算法的核心优势
企业局域网监控软件是数字化时代企业网络安全与高效运营的基石,犹如一位洞察秋毫的卫士。通过Java实现的优先队列算法,它能依据事件优先级排序,确保关键网络事件如异常流量、数据泄露等被优先处理,保障系统稳定与安全。代码示例展示了如何定义网络事件类并使用PriorityQueue处理高优先级事件,尤其在面对疑似风险时迅速启动应急措施。这一核心技术助力企业在复杂网络环境中稳健前行,护航业务腾飞。
65 32
剖析基于Java算法驱动的智能局域网管控之道
本文探讨了基于Java语言的局域网控制方案,结合链表数据结构与令牌桶算法,解决设备管理和流量调度难题。通过链表灵活存储网络设备信息,实现高效设备管理;令牌桶算法则精准控制流量,确保网络平稳运行。二者相辅相成,为校园、企业等局域网提供稳固高效的控制体系,保障业务连续性和数据安全。
Java 排序神器:Comparable 和 Comparator 该怎么选?
嗨,大家好,我是小米!今天和大家聊一聊Java社招面试中常考的经典问题——Comparable和Comparator的区别。Comparable定义对象的自然排序,适用于单一固定的排序规则;Comparator则是策略接口,用于定义自定义排序规则,适用于多样化或多变的排序需求。掌握这两者的区别是理解Java排序机制的基础,也是面试中的加分题。结合实际项目场景深入探讨它们的应用,能更好地打动面试官。如果你觉得有帮助,欢迎点赞、收藏、分享,期待你的一键三连!我们下期见~ 我是小米,一个喜欢分享技术的程序员,关注我的微信公众号“软件求生”,获取更多技术干货!
47 20
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
67 6
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
50 5

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等