java排序算法:快速排序、归并排序、堆排序等

简介: 排序算法:快速排序、归并排序、堆排序等

Java中的快速排序(QuickSort)、归并排序(Merge Sort)和堆排序(Heap Sort)是三种常用的排序算法,它们各有优缺点。以下是这些排序算法的简单介绍以及在Java中实现的示例。

快速排序

快速排序是一种基于分治策略的排序算法。它选择一个基准元素,将数组分为两部分:一部分包含所有小于基准的元素,另一部分包含所有大于或等于基准的元素。然后对这两部分递归地进行快速排序。

public class QuickSort {
   
    public static void quicksort(int[] arr, int low, int high) {
   
        if (low < high) {
   
            // 找到基准元素的正确位置
            int pivotIndex = partition(arr, low, high);

            // 对基准左边和右边的子数组进行递归排序
            quicksort(arr, low, pivotIndex - 1);
            quicksort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
   
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
   
            if (arr[j] <= pivot) {
   
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
   
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
AI 代码解读

归并排序

归并排序也是一种分治算法,它将数组分成两个相等(或几乎相等)的部分,分别对每个部分进行排序,然后合并已排序的两个部分。

public class MergeSort {
   
    public static void mergeSort(int[] arr, int left, int right) {
   
        if (left < right) {
   
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
   
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right) {
   
            if (arr[i] <= arr[j]) {
   
                temp[k++] = arr[i++];
            } else {
   
                temp[k++] = arr[j++];
            }
        }

        while (i <= mid) {
   
            temp[k++] = arr[i++];
        }

        while (j <= right) {
   
            temp[k++] = arr[j++];
        }

        System.arraycopy(temp, 0, arr, left, temp.length);
    }
}
AI 代码解读

堆排序

堆排序是一种通过构建大顶堆或小顶堆来实现的排序算法。它首先构造一个大顶堆(或小顶堆),然后不断交换堆顶元素与最后一个元素,并重新调整堆结构,直到整个数组有序。

public class HeapSort {
   
    public static void heapify(int[] arr, int n, int i) {
   
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) {
   
            largest = left;
        }

        if (right < n && arr[right] > arr[largest]) {
   
            largest = right;
        }

        if (largest != i) {
   
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

    public static void heapSort(int[] arr) {
   
        int n = arr.length;

        // 构建初始的大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
   
            heapify(arr, n, i);
        }

        // 交换堆顶元素和末尾元素,然后重新调整堆结构
        for (int i = n - 1; i > 0; i--) {
   
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    private static void swap(int[] arr, int i, int j) {
   
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
AI 代码解读

每种排序算法都有其独特的应用场景和性能特点。快速排序通常具有良好的平均性能,但最坏情况下会退化为O(n²);归并排序始终具有稳定的O(n log n)时间复杂度,但需要额外的空间;堆排序的时间复杂度也是O(n log n),并且原地排序不需要额外空间,但它不是稳定的排序算法。

目录
打赏
0
0
0
0
281
分享
相关文章
Java 实现局域网电脑屏幕监控算法揭秘
在数字化办公环境中,局域网电脑屏幕监控至关重要。本文介绍用Java实现这一功能的算法,涵盖图像采集、数据传输和监控端显示三个关键环节。通过Java的AWT/Swing库和Robot类抓取屏幕图像,使用Socket进行TCP/IP通信传输图像数据,并利用ImageIO类在监控端展示图像。整个过程确保高效、实时和准确,为提升数字化管理提供了技术基础。
86 15
算法系列之排序算法-堆排序
堆排序(Heap Sort)是一种基于堆数据结构的比较排序算法。它的时间复杂度为 O(nlogn),并且是一种原地排序算法(即不需要额外的存储空间)。堆排序的核心思想是利用堆的性质来维护一个最大堆或最小堆,然后逐步将堆顶元素(最大值或最小值)取出,放到数组的末尾,最终得到一个有序的数组。
20 8
算法系列之排序算法-堆排序
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
88 16
企业局域网监控软件中 Java 优先队列算法的核心优势
企业局域网监控软件是数字化时代企业网络安全与高效运营的基石,犹如一位洞察秋毫的卫士。通过Java实现的优先队列算法,它能依据事件优先级排序,确保关键网络事件如异常流量、数据泄露等被优先处理,保障系统稳定与安全。代码示例展示了如何定义网络事件类并使用PriorityQueue处理高优先级事件,尤其在面对疑似风险时迅速启动应急措施。这一核心技术助力企业在复杂网络环境中稳健前行,护航业务腾飞。
66 32
剖析基于Java算法驱动的智能局域网管控之道
本文探讨了基于Java语言的局域网控制方案,结合链表数据结构与令牌桶算法,解决设备管理和流量调度难题。通过链表灵活存储网络设备信息,实现高效设备管理;令牌桶算法则精准控制流量,确保网络平稳运行。二者相辅相成,为校园、企业等局域网提供稳固高效的控制体系,保障业务连续性和数据安全。
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
75 6
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
57 5
探秘局域网桌面监控:深入剖析 Java 语言核心算法
在数字化办公时代,局域网桌面监控如同企业的“智慧鹰眼”,确保工作效率与数据安全。本文以Java为载体,揭示哈希表在监控中的关键应用。通过高效的数据结构和算法,哈希表能快速索引设备连接信息,大幅提升监控的时效性和响应速度。代码示例展示了如何用Java实现设备网络连接监控,结合未来技术如AI、大数据,展望更智能的监控体系,助力企业在数字化浪潮中稳健前行。

热门文章

最新文章

AI助理

你好,我是AI助理

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