Cách sắp xếp một mảng trong Java

Sắp xếp là một trong những thao tác phổ biến và cần thiết nhất trong lập trình. Nó đại diện cho thứ tự của một số tập hợp các phần tử theo một thứ tự cụ thể. Bài viết này nói về các phương pháp tiêu chuẩn để sắp xếp mảng trong Java.

Nói ngắn gọn về việc sắp xếp

Vì vậy, sắp xếp là thứ tự của một tập hợp dữ liệu. Trong trường hợp của chúng tôi, mảng. Mục đích của việc sắp xếp mảng hoặc các cấu trúc dữ liệu khác là giúp tìm kiếm, thao tác hoặc phân tích dữ liệu trong bộ sưu tập dễ dàng hơn. Các lập trình viên cần sắp xếp thường xuyên đến mức bất kỳ ngôn ngữ lập trình nào cũng bao gồm các phương thức tích hợp để sắp xếp mảng, danh sách và các cấu trúc dữ liệu có thứ tự khác. Để sử dụng các phương pháp như vậy, hãy gọi cho họ. Các hoạt động được đơn giản hóa càng nhiều càng tốt. Thông thường, các phương thức tích hợp sẵn được tối ưu hóa tối đa; trong hầu hết các trường hợp, sử dụng chúng cho công việc hoặc dự án của bạn là một ý tưởng hay. Tuy nhiên, hầu hết mọi lập trình viên trong quá trình học đều cần phải tự mình thực hiện các thuật toán sắp xếp. Vì vậy, những bài tập hoàn hảo này sẽ dạy bạn hiểu bản chất của lập trình. Ngoài ra, đôi khi bạn cần những phương pháp sắp xếp không chuẩn mực trong công việc. Có nhiều thuật toán sắp xếp. Chúng có điểm mạnh và điểm yếu tùy thuộc vào loại hoặc kích thước của tập dữ liệu. Các thuật toán sắp xếp tiêu chuẩn bao gồm sắp xếp bong bóng, sắp xếp lựa chọn, sắp xếp chèn, sắp xếp hợp nhất và sắp xếp nhanh.

Phương thức tích hợp để sắp xếp mảng trong Java: Arrays.sort

Hãy bắt đầu với cách đơn giản nhất. Ai đó đã viết một phương pháp sắp xếp mảng trong Java cho chúng ta. Phương thức này nằm trong lớp Arrays , cụ thể hơn là java.util.Arrays . Lớp này chứa nhiều phương thức khác nhau để làm việc với mảng, chẳng hạn như sắp xếp và tìm kiếm. Phương thức Arrays.sort cung cấp một cách thuận tiện để sắp xếp mảng trong Java, cho dù chúng chứa chuỗi, số nguyên hay các phần tử khác. Có một số biến thể của phương thức Arrays.sort trong Java. Dưới đây là một số phương pháp sắp xếp thường được sử dụng từ lớp Arrays :

Arrays.sort(Array) : sử dụng nó để sắp xếp các mảng có kiểu hoặc đối tượng nguyên thủy theo thứ tự tăng dần. Nó sử dụng thứ tự tự nhiên của các yếu tố.
Arrays.sort(Array, fromIndex, toIndex) : Phương thức sắp xếp quá tải này cho phép bạn chỉ sắp xếp một phần của Mảng được chỉ định bởi các tham số fromIndex và toIndex.
Arrays.sort(Array, comparator) : cái này dùng để sắp xếp các mảng đối tượng bằng cách sử dụng một bộ so sánh tùy chỉnh. Bộ so sánh xác định thứ tự của các phần tử.
Arrays.parallelSort(Array) : Phiên bản phương thức này sắp xếp Mảng song song , sử dụng nhiều luồng để cải thiện hiệu suất. Nó có lợi cho việc sắp xếp các mảng lớn.
Arrays.parallelSort(Array, fromIndex, toIndex) : Phiên bản quá tải này của phương thức ParallelSort cho phép sắp xếp một phạm vi phần tử cụ thể trong Array .

Chúng cho phép bạn nhanh chóng sắp xếp các phần tử dựa trên thứ tự tự nhiên của chúng hoặc sử dụng bộ so sánh tùy chỉnh. Hãy cùng khám phá phương pháp này bằng hai ví dụ, một ví dụ liên quan đến chuỗi.

Ví dụ 1: Sắp xếp chuỗi

Giả sử chúng ta có một loạt các nhạc cụ dây: "violin", "viola", "cello" và "double bass". Chúng ta có thể sử dụng phương thức Array.sort để sắp xếp chúng theo thứ tự bảng chữ cái.

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

Đầu ra ở đây:

Dụng cụ được sắp xếp: đàn Trung Hồ cầm bass đôi viola đàn vi ô lông

Trong chương trình này, trước tiên, chúng ta nhập lớp java.util.Arrays để có quyền truy cập vào phương thức Array.sort . Sau đó, chúng ta tạo một mảng chuỗi gọi là nhạc cụ chứa tên nhạc cụ. Sau đó, chúng ta gọi Arrays.sort(instruments) . Vì vậy, phương thức này lấy một mảng, sắp xếp các phần tử theo thứ tự tăng dần dựa trên thứ tự tự nhiên của chúng (theo bảng chữ cái). Cuối cùng, chúng ta lặp qua Mảng đã sắp xếp và in từng nhạc cụ ra.

Ví dụ 2: Sắp xếp số nguyên

Hãy xem xét một ví dụ khác trong đó chúng ta sắp xếp một mảng các số nguyên theo thứ tự tăng dần.

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

Đầu ra:

Số được sắp xếp: 1 2 3 5 7 8

Ở đây chúng ta tạo một mảng số nguyên gọi là số với một số phần tử chưa được sắp xếp. Tiếp theo, chúng ta gọi Arrays.sort(numbers) để sắp xếp một mảng theo thứ tự tăng dần. Lưu ý rằng phương thức Array.sort sửa đổi mảng ban đầu tại chỗ. Vì vậy, để giữ nguyên Array , hãy tạo một bản sao trước khi sắp xếp.

Ví dụ 3: thứ tự giảm dần

Còn sắp xếp giảm dần thì sao? Điều đó cũng dễ dàng với Arrays.sort . Chỉ cần sử dụng một bộ so sánh tùy chỉnh. Đây là một ví dụ:

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

Đầu ra là tiếp theo:

Số được sắp xếp (Giảm dần): 8 7 5 3 2 1

Ở đây chúng ta có một mảng các số nguyên có tên là số. Bằng cách chuyển Comparator.reverseOrder() làm đối số thứ hai cho phương thức Arrays.sort , chúng tôi chỉ định một bộ so sánh tùy chỉnh sắp xếp các phần tử theo thứ tự giảm dần. Phương thức Comparator.reverseOrder() trả về một bộ so sánh đảo ngược thứ tự tự nhiên của các phần tử. Lưu ý rằng ở đây, chúng ta sử dụng lớp trình bao bọc Integer thay vì kiểu int nguyên thủy vì phương thức Comparator.reverseOrder() yêu cầu các đối tượng. Nếu bạn có một mảng các giá trị int nguyên thủy, bạn cũng cần chuyển đổi chúng thành đối tượng Integer trước khi sử dụng phương pháp này. Bằng cách sử dụng bộ so sánh tùy chỉnh, bạn có thể dễ dàng sắp xếp mảng theo thứ tự giảm dần bằng phương thức Arrays.sort trong Java.

Thuật toán sắp xếp cổ điển tự viết trong Java

Bạn đã từng xem các bài tập sắp xếp mảng nếu bạn đang học Khoa học Máy tính một cách độc lập hoặc ở trường đại học. Có nhiều thuật toán sắp xếp khác nhau và chúng tôi sẽ triển khai một số thuật toán trong bài viết này. Nói chung, thuật toán càng dễ thực hiện thì càng kém hiệu quả. Các lập trình viên đo lường hiệu quả của thuật toán được đo bằng thời gian hoạt động của nó và bộ nhớ được sử dụng cho tài nguyên. Đó không phải là chủ đề của bài viết của chúng tôi, nhưng chúng tôi đề cập rằng Arrays.sort trong Java là một thuật toán hiệu quả.

Sắp xếp bong bóng

Hãy bắt đầu với thuật toán phổ biến nhất trong giới sinh viên: Sắp xếp nổi bọt. Rất đơn giản: thuật toán so sánh hai phần tử và sau đó hoán đổi chúng nếu chúng sai thứ tự, v.v. cho đến hết mảng. Hóa ra là các phần tử nhỏ hơn "nổi" đến cuối Mảng , giống như bong bóng trong nước ngọt nổi lên trên cùng.

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

Ở đây phương thức lấy một mảng các số nguyên làm đầu vào. Vòng lặp bên ngoài đi từ 0 đến n-1. Ở đây n là kích thước của mảng. Vòng lặp bên trong so sánh các phần tử liền kề. Nếu thứ tự sai, phương thức sẽ hoán đổi chúng. Thủ tục này được lặp lại cho đến khi toàn bộ mảng được sắp xếp. Đây là một đầu ra của chương trình của chúng tôi:

Mảng trước khi sắp xếp: 18 28 2 7 90 45 Mảng sau khi sắp xếp: 2 7 18 28 45 90

Sắp xếp lựa chọn

Thuật toán lựa chọn sắp xếp một mảng bằng cách liên tục tìm phần tử nhỏ nhất từ phần chưa được sắp xếp và đặt nó ở đầu. Hãy viết nó bằng 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 + " ");
       }
   }
}

Đây là một đầu ra của chương trình:

Mảng trước khi sắp xếp: 18 28 45 2 90 7 Mảng sau khi sắp xếp: 2 7 18 28 45 90

Hãy giải thích nó từng bước một. Vòng lặp bên ngoài lặp từ đầu Mảng đến phần tử thứ hai đến phần tử cuối cùng (tối đa n-1). Vòng lặp này chọn từng phần tử một làm điểm bắt đầu của phần chưa được sắp xếp của Mảng . Bên trong vòng lặp bên ngoài, chúng ta khởi tạo minIndex cho chỉ mục hiện tại i , giả sử nó là chỉ mục của mục nhỏ nhất trong phần chưa được sắp xếp của Array . Vòng lặp bên trong bắt đầu từ i+1 và đi lên phần tử cuối cùng của Mảng . Nó tìm kiếm chỉ mục của phần tử nhỏ nhất trong phần chưa được sắp xếp của Mảng bằng cách so sánh từng phần tử với phần tử tối thiểu hiện tại ( arr[minIndex] ). Nếu chúng tôi tìm thấy phần tử nhỏ hơn phần tử tối thiểu hiện tại, chúng tôi sẽ cập nhật minIndex thành chỉ mục của phần tử tối thiểu mới. Sau khi vòng lặp bên trong hoàn tất, chúng ta đã tìm thấy chỉ mục của phần tử tối thiểu trong phần chưa được sắp xếp của Array . Sau đó, chúng tôi hoán đổi phần tử tối thiểu với phần tử đầu tiên của phần chưa được sắp xếp bằng cách sử dụng biến tạm thời temp. Vòng lặp bên ngoài tiếp tục cho đến khi tất cả các phần tử được sắp xếp, dần dần mở rộng phần được sắp xếp của Mảng . Cuối cùng, Mảng đã sắp xếp được in trong phương thức chính trước và sau khi gọi phương thức SelectionSort .

Hợp nhất Sắp xếp

Sắp xếp hợp nhất là một thuật toán chia để trị, chia mảng thành các mảng con nhỏ hơn một cách đệ quy, sắp xếp chúng và sau đó hợp nhất chúng để thu được một mảng được sắp xếp. Sắp xếp hợp nhất ổn định và được sử dụng rộng rãi, đặc biệt khi cần có sự ổn định và độ phức tạp về thời gian trong trường hợp xấu nhất được đảm bảo.

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

Đầu ra ở đây là:

Mảng trước khi sắp xếp: 18 2 28 7 90 45 Mảng sau khi sắp xếp: 2 7 18 28 45 90

Hãy giải thích chính xác hơn về cách thức hoạt động của nó. Thuật toán chia Mảng thành hai phần theo cách đệ quy cho đến khi đạt được trường hợp cơ sở (khi Mảng có một hoặc không phần tử). Sau đó, nó hợp nhất các nửa đã sắp xếp lại với nhau bằng phương pháp hợp nhất. Phương thức hợp nhất lấy ba mảng làm đầu vào: Mảng gốc và các mảng con bên trái và bên phải (trái và phải). Nó so sánh các phần tử từ mảng con bên trái và bên phải và hợp nhất chúng vào Mảng ban đầu theo thứ tự được sắp xếp.

Sắp xếp chèn

Sắp xếp chèn hoạt động bằng cách chèn liên tục một phần tử từ phần chưa được sắp xếp vào đúng vị trí của nó trong phần được sắp xếp. Nó hoạt động tốt đối với các tập dữ liệu nhỏ hoặc dữ liệu gần như được sắp xếp.

public class InsertionS