Java中的排序算法详解

Java中的排序算法详解

大家好，我是微赚淘客系统3.0的小编，是个冬天不穿秋裤，天冷也要风度的程序猿！

1. 排序算法概述

排序算法是计算机科学中的基础问题，它将一组元素按照特定的顺序重新排列。在实际开发中，选择合适的排序算法可以显著提高程序的性能。

2. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较每对相邻的元素，如果它们的顺序错误就把它们交换过来。

package cn.juwatech.sort;

public class BubbleSort {

    public void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        BubbleSort sorter = new BubbleSort();
        sorter.sort(arr);
        System.out.println("Sorted array using Bubble Sort:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. 快速排序（Quick Sort）

快速排序是一种分治算法，它将数组分成两个子数组，然后递归地对子数组进行排序。

package cn.juwatech.sort;

public class QuickSort {

    public void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            sort(arr, low, pi - 1);  // Recursively sort elements before partition
            sort(arr, pi + 1, high); // Recursively sort elements after partition
        }
    }

    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1); // Index of smaller element
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        QuickSort sorter = new QuickSort();
        sorter.sort(arr, 0, arr.length - 1);
        System.out.println("Sorted array using Quick Sort:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

4. 归并排序（Merge Sort）

归并排序采用分治策略，将数组分成两半，分别排序后再合并。

package cn.juwatech.sort;

public class MergeSort {

    public void sort(int[] arr, int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;

            sort(arr, l, m);
            sort(arr, m + 1, r);

            merge(arr, l, m, r);
        }
    }

    private void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int[] L = new int[n1];
        int[] R = new int[n2];

        System.arraycopy(arr, l, L, 0, n1);
        System.arraycopy(arr, m + 1, R, 0, n2);

        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }

        while (i < n1) {
            arr[k++] = L[i++];
        }

        while (j < n2) {
            arr[k++] = R[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        MergeSort sorter = new MergeSort();
        sorter.sort(arr, 0, arr.length - 1);
        System.out.println("Sorted array using Merge Sort:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

5. 总结

本文深入介绍了Java中常见的几种排序算法，包括冒泡排序、快速排序和归并排序。通过具体的代码示例，展示了它们的实现原理和基本用法。读者可以根据实际需求选择合适的排序算法来优化程序性能。

著作权归聚娃科技微赚淘客系统开发者团队，转载请注明出处！