Pelaksanaan dan teknik pengoptimuman prestasi algoritma isihan pemilihan Java

Pelaksanaan lengkap dan teknik pengoptimuman kod isihan pemilihan Java

Isih Pemilihan ialah algoritma pengisihan yang mudah dan intuitif. Idea asasnya ialah mencari elemen terkecil (atau terbesar) dalam tatasusunan yang tidak diisih, dan Letakkannya di penghujung daripada tatasusunan yang diisih. Ulangi langkah ini sehingga keseluruhan tatasusunan diisih. Berikut ialah penerangan terperinci tentang pelaksanaan lengkap jenis pemilihan dalam Java dan teknik pengoptimuman.

Pelaksanaan asas isihan pemilihan:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Dalam kod di atas, kami mula-mula mentakrifkan kaedah utama isihan pemilihan selectionSort(int[] arr)。在主方法中，我们先计算数组的长度，然后通过两个嵌套的循环来查找未排序部分中的最小元素，并将其与当前位置的元素进行交换。重复这个步骤直到整个数组排序完成。最后，在main方法中，我们定义了一个示例数组，并调用了selectionSort kaedah untuk mengisih.

Kerumitan masa isihan pemilihan ialah O(n^2), yang bermaksud apabila bilangan elemen bertambah, masa yang diperlukan untuk pengisihan akan meningkat secara kuadratik. Walau bagaimanapun, kita boleh menggunakan beberapa teknik untuk meningkatkan kecekapan isihan pemilihan.

Petua Pengoptimuman 1: Kurangkan bilangan operasi pertukaran

Dalam setiap pusingan jenis pemilihan, kami akan mencari elemen terkecil bahagian yang tidak diisih dan menukarnya dengan elemen pada kedudukan semasa. Walaupun ini perlu, ia boleh menjejaskan prestasi jika setiap pertukaran memerlukan tiga tugasan. Kita boleh mengurangkan bilangan pertukaran dengan merekodkan secara langsung nilai indeks unsur terkecil dan kemudian melakukan hanya satu operasi tugasan. Kod yang diubah suai kelihatan seperti ini:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Petua Pengoptimuman 2: Tambahkan pertimbangan untuk menyemak bahagian yang diisih

Dalam setiap pusingan, kami melintasi bahagian yang tidak diisih untuk mencari elemen terkecil. Walau bagaimanapun, sekiranya semasa proses traversal didapati elemen terbesar bahagian yang diisih adalah lebih kecil daripada elemen terkecil bahagian yang tidak diisih, maka pengisihan telah selesai dan kita boleh menamatkan proses pengisihan lebih awal. Kod yang diubah suai adalah seperti berikut:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            boolean sorted = true;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
                if (arr[j] < arr[j-1]) {
                    sorted = false;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
            if (sorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Melalui teknik pengoptimuman di atas, kami boleh meningkatkan kecekapan pelaksanaan isihan pemilihan.

Ringkasan:

Isihan pilihan ialah algoritma pengisihan yang mudah tetapi kurang cekap. Kecekapan isihan pemilihan boleh dipertingkatkan dengan mengurangkan bilangan operasi pertukaran dan menambah pertimbangan pada bahagian yang diisih. Walau bagaimanapun, walaupun kerumitan masa isihan pemilihan ialah O(n^2), ia masih merupakan algoritma pengisihan yang berkesan dalam beberapa senario tertentu.

Saya harap artikel ini dapat membantu anda memahami dan melaksanakan pengisihan pemilihan serta meningkatkan kecekapan algoritma melalui beberapa teknik pengoptimuman.

Atas ialah kandungan terperinci Pelaksanaan dan teknik pengoptimuman prestasi algoritma isihan pemilihan Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!