Bagaimana untuk Mengisih Array di Jawa

Isih adalah salah satu operasi yang paling biasa dan perlu dalam pengaturcaraan. Ia mewakili susunan beberapa set elemen dalam susunan tertentu. Artikel ini adalah mengenai kaedah standard untuk menyusun tatasusunan dalam Java.

Secara ringkas tentang menyusun

Jadi, pengisihan ialah susunan satu set data. Dalam kes kami, tatasusunan. Tujuan mengisih tatasusunan atau struktur data lain adalah untuk memudahkan mencari, memanipulasi atau menghuraikan data dalam koleksi. Pengaturcara perlu mengisih dengan kerap sehingga mana-mana bahasa pengaturcaraan termasuk kaedah terbina dalam untuk menyusun tatasusunan, senarai dan struktur data tertib yang lain. Untuk menggunakan kaedah sedemikian, hubungi mereka. Operasi dipermudahkan sebaik mungkin. Biasanya, kaedah terbina dalam dioptimumkan secara maksimum; dalam kebanyakan kes, menggunakannya untuk kerja atau projek anda adalah idea yang baik. Walau bagaimanapun, hampir setiap pengaturcara, semasa pengajian mereka, perlu melaksanakan algoritma pengisihan sendiri. Oleh itu, latihan yang sempurna ini mengajar anda untuk memahami intipati pengaturcaraan. Di samping itu, kadangkala anda memerlukan kaedah pengisihan bukan standard dalam kerja. Terdapat banyak algoritma pengisihan. Mereka mempunyai kekuatan dan kelemahan bergantung pada jenis atau saiz set data. Algoritma pengisihan standard termasuk isihan gelembung, isihan pemilihan, isihan sisipan, isihan gabungan dan isihan pantas.

Kaedah terbina dalam untuk menyusun tatasusunan dalam Java: Arrays.sort

Mari kita mulakan dengan yang paling mudah. Seseorang telah menulis kaedah untuk menyusun tatasusunan dalam Java untuk kami. Kaedah ini berada dalam kelas Arrays , lebih khusus java.util.Arrays . Kelas ini mengandungi pelbagai kaedah untuk bekerja dengan tatasusunan, seperti menyusun dan mencari. Kaedah Arrays.sort menyediakan cara yang mudah untuk mengisih tatasusunan dalam Java, sama ada ia mengandungi rentetan, integer atau elemen lain. Terdapat beberapa variasi kaedah Arrays.sort di Jawa. Berikut ialah beberapa kaedah pengisihan yang biasa digunakan daripada kelas Arrays :

• Arrays.sort(Array) : gunakannya untuk mengisih tatasusunan jenis atau objek primitif dalam tertib menaik. Ia menggunakan susunan semula jadi unsur-unsur.
• Arrays.sort(Array, fromIndex, toIndex) : Kaedah isihan terlampau beban ini membolehkan anda mengisih hanya sebahagian daripada Array yang ditentukan oleh parameter fromIndex dan toIndex.
• Arrays.sort(Array, comparator) : yang ini adalah untuk mengisih tatasusunan objek menggunakan pembanding tersuai. Pembanding mentakrifkan susunan unsur-unsur.
• Arrays.parallelSort(Array) : Versi kaedah ini menyusun Array secara selari, menggunakan berbilang benang untuk prestasi yang lebih baik. Ia berfaedah untuk menyusun tatasusunan yang besar.
• Arrays.parallelSort(Array, fromIndex, toIndex) : Versi overload kaedah parallelSort ini membolehkan pengisihan julat tertentu elemen dalam Array .

Mereka membenarkan anda menyusun elemen dengan cepat berdasarkan susunan semula jadinya atau menggunakan pembanding tersuai. Mari kita teroka kaedah ini dengan dua contoh, satu melibatkan rentetan.

Contoh 1: Menyusun Rentetan

Katakan kita mempunyai pelbagai alat muzik bertali: "violin", "viola", "cello", dan "double bass". Kita boleh menggunakan kaedah Array.sort untuk menyusunnya mengikut abjad.

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

Outputnya ada di sini: Dalam program ini, pertama, kami mengimport kelas java.util.Arrays untuk mendapatkan akses kepada kaedah Array.sort . Kemudian kami mencipta tatasusunan rentetan yang dipanggil instrumen yang mengandungi nama alat muzik. Selepas itu, kami memanggil Arrays.sort(instruments) . Jadi kaedah ini mendapat tatasusunan, mengisih unsur dalam tertib menaik berdasarkan susunan semula jadinya (abjad). Akhirnya, kami mengulangi Array yang diisih dan mencetak setiap instrumen.

Contoh 2: Mengisih Integer

Mari kita pertimbangkan contoh lain di mana kita mengisih tatasusunan integer dalam tertib menaik.

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

Pengeluaran: Di sini kita mencipta tatasusunan integer yang dipanggil nombor dengan beberapa elemen yang tidak diisih. Seterusnya, kami memanggil Arrays.sort(nombor) untuk mengisih tatasusunan dalam tertib menaik. Ambil perhatian bahawa kaedah Array.sort mengubah suai tatasusunan asal di tempat. Jadi untuk mengekalkan Array asal , buat salinan sebelum mengisih.

Contoh 3: tertib menurun

Bagaimana pula dengan jenis menurun? Ia juga mudah dengan Arrays.sort . Hanya gunakan pembanding tersuai. Berikut ialah contoh:

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

Output adalah seterusnya: Di sini kita mempunyai tatasusunan integer bernama nombor. Dengan menghantar Comparator.reverseOrder() sebagai argumen kedua kepada kaedah Arrays.sort , kami menentukan pembanding tersuai yang mengisih elemen dalam tertib menurun. Kaedah Comparator.reverseOrder () mengembalikan pembanding yang membalikkan susunan semula jadi unsur. Ambil perhatian bahawa di sini, kami menggunakan kelas pembalut Integer dan bukannya jenis int primitif kerana kaedah Comparator.reverseOrder() memerlukan objek. Jika anda mempunyai tatasusunan nilai int primitif, anda juga perlu menukarnya kepada objek Integer sebelum menggunakan pendekatan ini. Menggunakan pembanding tersuai, anda boleh mengisih tatasusunan dengan mudah dalam tertib menurun menggunakan kaedah Arrays.sort dalam Java.

Algoritma pengisihan klasik yang ditulis sendiri dalam Java

Anda telah melihat Array menyusun tugasan jika anda belajar Sains Komputer secara bebas atau di universiti. Terdapat banyak algoritma pengisihan yang berbeza, dan kami akan melaksanakan beberapa daripadanya dalam artikel ini. Secara amnya, semakin mudah sesuatu algoritma dilaksanakan, semakin kurang cekapnya. Pengaturcara mengukur kecekapan algoritma diukur dengan masa operasinya dan memori yang dibelanjakan untuk sumber. Itu bukan topik artikel kami, tetapi kami menyebut bahawa Arrays.sort dalam Java ialah algoritma yang berkesan.

Isih Buih

Mari kita mulakan dengan algoritma yang paling popular dalam kalangan pelajar: Bubble sort. Ia mudah: algoritma membandingkan dua elemen dan kemudian menukarnya jika ia berada dalam susunan yang salah, dan seterusnya sehingga penghujung tatasusunan. Ternyata unsur-unsur yang lebih kecil "terapung" ke hujung Array , seperti buih dalam soda muncul ke atas.

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

Di sini kaedah mengambil tatasusunan integer sebagai input. Gelung luar pergi dari 0 ke n-1. Di sini n ialah saiz tatasusunan. Gelung dalam membandingkan elemen bersebelahan. Jika pesanan salah, kaedah menukarnya. Prosedur ini diulang sehingga keseluruhan tatasusunan telah diisih. Berikut adalah output program kami:

Isih Pemilihan

Algoritma pemilihan mengisih tatasusunan dengan mencari berulang kali elemen terkecil dari bahagian yang tidak diisih dan meletakkannya pada permulaan. Mari kita tulis dalam 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 + " ");
       }
   }
}

Berikut ialah output program: Mari kita jelaskan langkah demi langkah. Gelung luar berulang dari permulaan Array ke elemen kedua hingga terakhir (sehingga n-1). Gelung ini memilih setiap elemen satu demi satu sebagai titik permulaan bagi bahagian Array yang tidak diisih . Di dalam gelung luar, kami memulakan minIndex kepada indeks semasa i , dengan mengandaikan ia sebagai indeks item terkecil dalam bahagian Array yang tidak diisih . Gelung dalam bermula dari i+1 dan naik ke elemen terakhir Array . Ia mencari indeks item terkecil dalam bahagian Array yang tidak diisih dengan membandingkan setiap elemen dengan elemen minimum semasa ( arr[minIndex] ). Jika kami menemui elemen yang lebih kecil daripada elemen minimum semasa, kami mengemas kini minIndex kepada indeks elemen minimum baharu. Selepas gelung dalaman selesai, kami telah menemui indeks elemen minimum dalam bahagian Array yang tidak diisih . Kami kemudian menukar elemen minimum dengan elemen pertama bahagian yang tidak diisih dengan menggunakan temp pembolehubah sementara. Gelung luar diteruskan sehingga semua elemen diisih, secara beransur-ansur memanjangkan bahagian yang diisih bagi Array . Akhirnya, Array yang diisih dicetak dalam kaedah utama sebelum dan selepas memanggil kaedah selectionSort .

Gabung Isih

Merge Sort ialah algoritma divide-and-conquer yang membahagikan Array secara rekursif kepada subbarray yang lebih kecil, mengisihnya dan kemudian menggabungkannya untuk mendapatkan tatasusunan yang diisih. Merge Sort adalah stabil dan digunakan secara meluas, terutamanya apabila kestabilan dan kerumitan masa kes terburuk yang dijamin diperlukan.

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

Output di sini ialah: Mari terangkan dengan lebih tepat cara ia berfungsi. Algoritma membahagikan Array kepada dua bahagian secara rekursif sehingga kes asas dicapai (apabila Array mempunyai satu atau sifar elemen). Kemudian ia menggabungkan bahagian yang diisih kembali bersama menggunakan kaedah gabungan. Kaedah gabungan mengambil tiga tatasusunan sebagai input: Tatasusunan asal dan subarray kiri dan kanan (kiri dan kanan). Ia membandingkan unsur-unsur dari subarray kiri dan kanan dan menggabungkannya ke dalam Tatasusunan asal dalam susunan yang disusun.

Isihan sisipan

Isih Sisipan berfungsi dengan memasukkan elemen dari bahagian yang belum diisi berulang kali ke kedudukannya yang betul dalam bahagian yang diisih. Ia berfungsi dengan baik untuk set data kecil atau data yang hampir diisih.

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

Output program adalah seperti biasa: Di sini kaedah insertionSort melaksanakan algoritma Insertion Sort. Ia berulang melalui Array dan menganggap setiap elemen sebagai kunci. Ia membandingkan kunci dengan elemen sebelum dan menggerakkannya satu kedudukan ke hadapan jika ia lebih besar, dengan berkesan mengalihkan elemen untuk memberi ruang kepada kunci pada kedudukan yang betul. Gelung luar berulang daripada elemen kedua ( i = 1 ) ke elemen terakhir Array. Gelung dalam bermula dari elemen semasa ( arr[i] ) dan pergi ke belakang ( j = i - 1 ) sehingga ia menemui kedudukan yang betul untuk kunci atau mencapai permulaan Array . Di dalam gelung dalam, jika elemen ( arr[j] ) lebih besar daripada kekunci, ia dianjakkan satu kedudukan ke hadapan ( arr[j + 1] = arr[j] ) untuk memberi ruang kepada kunci. Proses ini berterusan sehingga kedudukan yang betul untuk kunci ditemui. Selepas gelung dalam selesai, kekunci diletakkan pada kedudukan yang betul ( arr[j + 1] = kekunci ). Dalam kaedah utama, tatasusunan contoh dibuat dan dicetak sebelum dan selepas mengisih menggunakan kaedah insertionSort .

Isih cepat

Isih Pantas ialah algoritma bahagi-dan-takluk yang memilih elemen pangsi dan membahagikan Array di sekeliling pangsi. Sebagai peraturan, Isih Pantas adalah lebih pantas daripada Isih Gabung untuk set data bersaiz kecil dan sederhana kerana faktor pemalarnya yang rendah.

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

Outputnya ada di sini: Jadi di sini kita mempunyai tiga kaedah untuk melaksanakan isihan pantas. Kaedah quickSort mengambil tiga parameter: Array untuk diisih, indeks rendah subarray dan indeks tinggi subarray. Pada mulanya, ia menyemak sama ada subarray mempunyai lebih daripada satu elemen. Jika ya, ia memilih pivot menggunakan kaedah partition, mengisih subarray secara rekursif sebelum pivot, dan mengisih subarray secara rekursif selepas pivot. Kaedah partition memilih pangsi sebagai elemen terakhir subarray ( arr[high] ). Ia menetapkan indeks partition (i) kepada indeks rendah tolak 1. Ia kemudian melelaran daripada indeks rendah kepada indeks tinggi - 1 dan menyemak sama ada setiap elemen kurang daripada atau sama dengan pangsi. Jika ya, ia menukar elemen dengan elemen pada indeks partition (i) dan menambah indeks partition. Akhirnya, ia menukar elemen pangsi dengan elemen pada indeks partition + 1 dan mengembalikan indeks partition. Kaedah partition memilih pangsi sebagai elemen terakhir subarray ( arr[high] ). Ia menetapkan indeks partition (i) kepada indeks rendah tolak 1. Ia kemudian melelang daripada indeks rendah kepada indeks tinggi - 1 dan menyemak sama ada setiap item lebih kecil atau sama dengan pangsi. Jika ya, ia menukar elemen dengan elemen pada indeks partition (i) dan menambah indeks partition. Akhirnya, ia menukar elemen pangsi dengan elemen pada indeks partition + 1 dan mengembalikan indeks partition. Kaedah swap ialah kaedah utiliti yang digunakan untuk menukar dua elemen dalam Array . Dalam kaedah utama , tatasusunan contoh dicipta dan dicetak sebelum dan selepas mengisih menggunakan kaedah quickSort .

Kesimpulan

Daripada artikel ini anda telah mengetahui cara mengisih tatasusunan dalam bahasa Java. Anda boleh menggunakan kaedah Arrays.sort terbina dalam atau menulis pelaksanaan kaedah pengisihan popular anda sendiri seperti isihan gelembung, isihan gabungan dan sebagainya. Anda juga boleh cuba menyerang kaedah pengisihan anda sendiri. Ia bergantung kepada tugas anda. Jika anda perlu menyelesaikan masalah pengisihan dengan cepat, hanya gunakan kaedah pra-tulisan. Jika anda mempelajari pengaturcaraan dan cuba menjadi lebih baik dalam hal itu, adalah idea yang sangat baik untuk menulis beberapa kaedah pengisihan sendiri.