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

相关文章
|
23天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
15 1
|
23天前
|
算法 搜索推荐
数据结构与算法学习十八:堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法,具有平均和最坏时间复杂度为O(nlogn)的特点。
60 0
数据结构与算法学习十八:堆排序
|
27天前
|
算法 搜索推荐
算法之堆排序
本文介绍了堆排序算法的原理和实现,通过构建最大堆或最小堆,利用堆的性质进行高效的排序,并提供了具体的编程实现细节和示例。
19 0
算法之堆排序
|
30天前
|
搜索推荐 Java Go
深入了解快速排序算法
深入了解快速排序算法
26 2
|
30天前
|
算法 Java Go
深入了解堆排序算法
深入了解堆排序算法
21 1
|
27天前
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
29天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
66 0
|
29天前
|
算法 Python
Python算法编程:冒泡排序、选择排序、快速排序
Python算法编程:冒泡排序、选择排序、快速排序
22 0
|
30天前
|
搜索推荐 Java Go
深入了解归并排序算法
深入了解归并排序算法
17 0
|
1月前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)