如何在 Java 中对数组进行排序

排序是编程中最常见也是最必要的操作之一。它表示某些元素集按特定顺序的排序。本文介绍 Java 中数组排序的标准方法。

简单介绍一下排序

所以，排序就是对一组数据进行排序。在我们的例子中，是数组。对数组或其他数据结构进行排序的目的是为了更轻松地查找、操作或解析集合中的数据。程序员经常需要排序，因此任何编程语言都包含用于对数组、列表和其他有序数据结构进行排序的内置方法。要使用此类方法，请调用它们。操作尽可能简化。通常，内置方法会得到最大程度的优化；在大多数情况下，将它们用于您的工作或项目是一个好主意。然而，几乎每个程序员在学习的过程中，都需要自己实现排序算法。因此，这些完美的练习可以教你理解编程的本质。另外，有时你在工作中需要非标准的排序方法。排序算法有很多种。它们各有优缺点，具体取决于数据集的类型或大小。标准排序算法包括冒泡排序、选择排序、插入排序、合并排序和快速排序。

Java 中对数组进行排序的内置方法：Arrays.sort

让我们从最简单的开始。有人已经用Java为我们写了一个数组排序的方法。该方法位于Arrays类中，更具体地说是java.util.Arrays中。此类包含用于处理数组的各种方法，例如排序和搜索。Arrays.sort方法提供了一种在 Java 中对数组进行排序的便捷方法，无论它们包含字符串、整数还是其他元素。Java 中的Arrays.sort方法有多种变体。以下是Arrays类中一些常用的排序方法：

• Arrays.sort(Array)：用它对原始类型或对象的数组按升序排序。它使用元素的自然顺序。
• Arrays.sort(Array, fromIndex, toIndex)：此重载排序方法允许您仅对由 fromIndex 和 toIndex 参数指定的 Array 的一部分进行排序。
• Arrays.sort(Array, comparator)：此函数用于使用自定义比较器对对象数组进行排序。比较器定义元素的顺序。
• Arrays.parallelSort(Array)：此方法版本并行对数组进行排序，利用多个线程来提高性能。这对于对大型数组进行排序很有好处。
• Arrays.parallelSort(Array, fromIndex, toIndex)：parallelSort 方法的此重载版本允许对 Array 中的特定范围的元素进行排序。

它们允许您根据元素的自然顺序或使用自定义比较器快速排列元素。让我们通过两个示例来探讨该方法，其中一个涉及字符串。

示例 1：对字符串进行排序

假设我们有一系列弦乐器：“小提琴”、“中提琴”、“大提琴”和“低音提琴”。我们可以使用Array.sort方法按字母顺序排列它们。

import java.util.Arrays;
//Arrays.sort example
public class StringSortExample {
    public static void main(String[] args) {
        String[] instruments = {"violin", "viola", "cello", "double bass"};

        Arrays.sort(instruments);

        System.out.println("Sorted Instruments:");
        for (String instrument : instruments) {
            System.out.println(instrument);
        }
    }
}

输出在这里： 在此程序中，首先，我们导入java.util.Arrays类以访问Array.sort方法。然后我们创建一个名为instruments 的字符串数组，其中包含乐器名称。之后，我们调用Arrays.sort(instruments)。因此，此方法获取一个数组，根据元素的自然顺序（按字母顺序）按升序对元素进行排序。最后，我们循环遍历排序后的数组并打印出每个乐器。

示例 2：对整数排序

让我们考虑另一个示例，其中我们按升序对整数数组进行排序。

import java.util.Arrays;

public class IntegerSortExample {
    public static void main(String[] args) {
        int[] numbers = {8, 2, 7, 3, 1, 5};
//sort an array using Arrays.sort
        Arrays.sort(numbers);

        System.out.println("Sorted Numbers:");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

输出： 在这里，我们创建一个名为 number 的整数数组，其中包含多个未排序的元素。接下来，我们调用Arrays.sort(numbers)对数组进行升序排序。请注意，Array.sort方法就地修改原始数组。因此，要保留原始Array，请在排序之前复制一份。

示例 3：降序排列

那么降序排序呢？使用Arrays.sort也很容易。只需使用自定义比较器即可。这是一个例子：

import java.util.Arrays;
import java.util.Comparator;
//Arrays.sort with custom comparator example
public class DescendingSortExample {
    public static void main(String[] args) {
        Integer[] numbers = {8, 2, 7, 3, 1, 5};
        //sort an Array using Arrays.sort
        Arrays.sort(numbers, Comparator.reverseOrder());

        System.out.println("Sorted Numbers (Descending):");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

输出如下： 这里我们有一个名为 number 的整数数组。通过将Comparator.reverseOrder()作为第二个参数传递给Arrays.sort方法，我们指定了一个自定义比较器，该比较器按降序对元素进行排序。Comparator.reverseOrder ()方法返回一个反转元素自然顺序的比较器。请注意，这里我们使用 Integer 包装类而不是原始 int 类型，因为Comparator.reverseOrder()方法需要对象。如果您有一个原始 int 值数组，则还需要在使用此方法之前将它们转换为Integer对象。使用自定义比较器，您可以使用Java 中的 Arrays.sort方法轻松地按降序对数组进行排序。

Java自写经典排序算法

如果您正在独立学习计算机科学或在大学学习计算机科学，您已经看过数组排序作业。有许多不同的排序算法，我们将在本文中实现其中一些。一般来说，算法越容易实现，其效率就越低。程序员通过算法的运行时间和资源消耗的内存来衡量算法的效率。这不是我们文章的主题，但我们提到Java 中的Arrays.sort是一种有效的算法。

冒泡排序

我们先从最受学生欢迎的算法开始：冒泡排序。很简单：该算法比较两个元素，如果顺序错误则交换它们，依此类推，直到数组末尾。事实证明，较小的元素“漂浮”到 Array 的末尾，就像汽水中的气泡浮到顶部一样。

public class BubbleSort {

       public static void bubbleSort(int[] myArray) {
           int n = myArray.length;
           for (int i = 0; i < n - 1; i++) {
               for (int j = 0; j < n - i - 1; j++) {
                   if (myArray[j] > myArray[j + 1]) {
                       // Swap myArray[j] and myArray[j+1]
                       int temp = myArray[j];
                       myArray[j] = myArray[j + 1];
                       myArray[j + 1] = temp;
                   }
               }
           }
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 7, 90, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           bubbleSort(arr);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

这里该方法采用整数数组作为输入。外层循环从0到n-1。这里 n 是数组的大小。内循环比较相邻元素。如果顺序错误，该方法会交换它们。重复此过程，直到整个数组已排序。这是我们程序的输出：

选择排序

选择算法通过重复从未排序部分中查找最小元素并将其放在开头来对数组进行排序。我们用 Java 来写：

public class SelectionSort {
   public static void selectionSort(int[] myArray) {
       int n = myArray.length;

       for (int i = 0; i < n - 1; i++) {
           int minIndex = i;

           // Find the index of the minimum element in the unsorted part of the array
           for (int j = i + 1; j < n; j++) {
               if (myArray[j] < myArray[minIndex]) {
                   minIndex = j;
               }
           }

           // Swap the minimum element with the first element of the unsorted part
           int temp = myArray[minIndex];
           myArray[minIndex] = myArray[i];
           myArray[i] = temp;
       }
   }

   public static void main(String[] args) {
       int[] arr = {18, 28, 45, 2, 90, 7};

       System.out.println("Array before sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }

       selectionSort(arr);

       System.out.println("\nArray after sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }
   }
}

这是程序的输出： 让我们逐步解释一下。外部循环从数组的开头迭代到倒数第二个元素（最多 n-1）。该循环逐一选择每个元素作为Array未排序部分的起点。在外循环内部，我们将minIndex初始化为当前索引i ，假设它是Array未排序部分中最小项的索引。内部循环从i+1开始，一直到Array的最后一个元素。它通过将每个元素与当前最小元素 ( arr[minIndex] ) 进行比较来搜索数组未排序部分中最小项目的索引。如果我们找到一个小于当前最小元素的元素，我们将minIndex更新为新的最小元素的索引。内部循环完成后，我们在Array的未排序部分找到了最小元素的索引。然后，我们使用临时变量 temp 将最小元素与未排序部分的第一个元素交换。外部循环继续进行，直到所有元素都已排序，逐渐扩展Array的已排序部分。最后，在调用selectionSort方法之前和之后，在main方法中打印排序后的Array。

归并排序

归并排序是一种分而治之的算法，它递归地将数组分成更小的子数组，对它们进行排序，然后将它们合并以获得排序后的数组。归并排序非常稳定并且被广泛使用，特别是在需要稳定性和保证最坏情况时间复杂度的情况下。

public class MergeSort {

      //Merge Sort array
      public static void mergeSort(int[] myArray) {
        if (myArray.length <= 1) {
            return;
        }

        int mid = myArray.length / 2;
        int[] left = new int[mid];
        int[] right = new int[myArray.length - mid];

        System.arraycopy(myArray, 0, left, 0, mid);
        System.arraycopy(myArray, mid, right, 0, myArray.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(myArray, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0; // index for left subarray
        int j = 0; // index for right subarray
        int k = 0; // index for merged array

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < left.length) {
            arr[k++] = left[i++];
        }

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

    public static void main(String[] args) {
        int[] arr = {18, 2, 28, 7, 90, 45};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        mergeSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

这里的输出是： 让我们更准确地解释它是如何工作的。该算法递归地将数组分成两部分，直到达到基本情况（当数组有一个或零个元素时）。然后它使用 merge 方法将排序后的两半重新合并在一起。merge 方法接受三个数组作为输入：原始数组和左右子数组（左和右）。它比较左右子数组中的元素，并将它们按排序顺序 合并到原始数组中。

插入排序

插入排序的工作原理是重复地将未排序部分中的元素插入到已排序部分中的正确位置。它对于小数据集或接近排序的数据表现良好。

public class InsertionSort {
    public static void insertionSort(int[] myArray) {
        int n = myArray.length;

        for (int i = 1; i < n; i++) {
            int key = myArray[i];
            int j = i - 1;

            while (j >= 0 && myArray[j] > key) {
                myArray[j + 1] = myArray[j];
                j--;
            }

            myArray[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 90, 7, 28, 45, 2};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        insertionSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

程序的输出与平常一样： 这里的insertionSort方法实现了插入排序算法。它迭代数组并将每个元素视为键。它将键与其前面的元素进行比较，如果它们更大，则将它们向前移动一个位置，从而有效地移动元素，以便在正确的位置为键腾出空间。 外循环从数组的第二个元素 ( i = 1 ) 迭代到最后一个元素。内部循环从当前元素 ( arr[i] ) 开始并向后移动 ( j = i - 1 )，直到找到键的正确位置或到达 Array 的开头。在内循环内部，如果某个元素 ( arr[j] ) 大于键，则会向前移动一位 ( arr[j + 1] = arr[j] ) 以为键腾出空间。此过程将持续进行，直到找到钥匙的正确位置。内部循环完成后，密钥被放置在正确的位置（arr[j + 1] = key）。在 main 方法中，在使用insertSort方法排序之前和之后创建并打印示例数组。

快速排序

快速排序是一种分而治之的算法，它选择一个主元元素并围绕该主元对数组进行分区。一般来说，对于中小型数据集，快速排序由于其常数因子较低而比合并排序更快。

public class QuickSort {

       public static void quickSort(int[] myArray, int low, int high) {
           if (low < high) {
               int pivotIndex = partition(myArray, low, high);
               quickSort(myArray, low, pivotIndex - 1);
               quickSort(myArray, pivotIndex + 1, high);
           }
       }

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

       public static void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 90, 7, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           quickSort(arr, 0, arr.length - 1);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

输出在这里： 所以这里我们有三种方法来实现快速排序。QuickSort方法采用三个参数：要排序的数组、子数组的低索引和子数组的高索引。首先，它检查子数组是否有多个元素。如果是，则使用分区方法选择一个主元，对主元之前的子数组递归排序，对主元之后的子数组递归排序。分区方法选择主元作为子数组的最后一个元素 ( arr[high] )。它将分区索引 (i) 设置为低索引减 1。然后从低索引迭代到高索引 - 1，并检查每个元素是否小于或等于主元。如果是，它将与分区索引 (i) 处的元素交换该元素并递增分区索引。最后，它将主元元素与分区索引 + 1 处的元素交换并返回分区索引。分区方法选择主元作为子数组的最后一个元素 ( arr[high] )。它将分区索引 (i) 设置为低索引减 1。然后从低索引迭代到高索引 - 1，并检查每个项目是否小于或等于主元。如果是，它将与分区索引 (i) 处的元素交换该元素并递增分区索引。最后，它将主元元素与分区索引 + 1 处的元素交换并返回分区索引。swap 方法是一种实用方法，用于交换Array中的两个元素。在main方法中，在使用QuickSort方法排序之前和之后创建并打印示例数组。

结论

从本文中，您了解了如何使用 Java 语言对数组进行排序。您可以使用内置的Arrays.sort方法或编写自己的流行排序方法的实现，例如冒泡排序、合并排序等。你也可以尝试侵入你自己的排序方法。这取决于你的任务。如果您需要快速解决排序问题，只需使用预先编写的方法即可。如果您学习编程并尝试做得更好，那么自己编写一些排序方法确实是个好主意。