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;
    }
}

归并排序

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

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);
    }
}

堆排序

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

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;
    }
}

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

相关文章
|
12天前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
39 4
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
70 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
1月前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
107 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
1月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
23 1
|
1月前
|
算法 Java Linux
java制作海报一:java使用Graphics2D 在图片上写字,文字换行算法详解
这篇文章介绍了如何在Java中使用Graphics2D在图片上绘制文字,并实现自动换行的功能。
104 0
|
1月前
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
1月前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
72 0
|
1月前
|
算法 Python
Python算法编程:冒泡排序、选择排序、快速排序
Python算法编程:冒泡排序、选择排序、快速排序
|
1月前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
21 0
|
1月前
|
搜索推荐 Java Go
深入了解归并排序算法
深入了解归并排序算法
20 0
下一篇
无影云桌面