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),并且原地排序不需要额外空间,但它不是稳定的排序算法。

相关文章
|
1天前
|
存储 算法 Java
【数据结构与算法】2、链表(简单模拟 Java 中的 LinkedList 集合,反转链表面试题)
【数据结构与算法】2、链表(简单模拟 Java 中的 LinkedList 集合,反转链表面试题)
6 0
|
1天前
|
存储 算法 Java
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
5 0
|
1天前
|
搜索推荐 算法 Python
python实现归并排序算法。
【2月更文挑战第9天】【2月更文挑战第24篇】python实现归并排序算法。
|
1天前
|
搜索推荐 Python
python实现快速排序算法。
【2月更文挑战第9天】【2月更文挑战第23篇】python实现快速排序算法。
|
3天前
|
搜索推荐 算法 Java
【数据结构排序算法篇】----堆排序【实战演练】
【数据结构排序算法篇】----堆排序【实战演练】
8 2
|
3天前
|
搜索推荐 算法 Java
【数据结构排序算法篇】----快速排序【实战演练】
【数据结构排序算法篇】----快速排序【实战演练】
20 2
|
3天前
|
存储 搜索推荐 算法
【数据结构排序算法篇】----归并排序【实战演练】
【数据结构排序算法篇】----归并排序【实战演练】
8 0
|
3天前
|
机器学习/深度学习 算法 Java
递归算法还有哪些是你不知道的----【探讨Java经典遍历问题和面试题】
递归算法还有哪些是你不知道的----【探讨Java经典遍历问题和面试题】
25 1
|
4天前
|
存储 算法 安全
【国密算法】国密算法在Java中的实践
【国密算法】国密算法在Java中的实践
|
4天前
|
搜索推荐
排序算法之七:归并排序(非递归)
排序算法之七:归并排序(非递归)
排序算法之七:归并排序(非递归)

相关产品