Memahami Algoritma Isih Pemilihan (dengan Contoh dalam Java)

Isih Pilihan: Panduan Langkah demi Langkah

Isih Pilihan ialah algoritma pengisihan yang mudah. Ia berulang kali mencari elemen minimum dari bahagian senarai yang tidak diisih dan meletakkannya pada permulaan. Proses ini berterusan sehingga keseluruhan senarai diisih.

Cara Isih Pemilihan Berfungsi

Mari kita ilustrasikan dengan contoh, mengisih tatasusunan ini dalam tertib menaik:

Lelaran 1:

Matlamatnya adalah untuk meletakkan elemen terkecil pada permulaan. Kita mulakan dengan menganggap elemen pertama adalah minimum.

Kami membandingkan minimum semasa dengan setiap elemen berikutnya, mengemas kini minimum jika elemen yang lebih kecil ditemui.

Ini berterusan sehingga minimum sebenar dikenal pasti.

Akhir sekali, kami menukar elemen minimum dengan elemen pertama.

Elemen pertama kini diisih. Lelaran berikutnya hanya akan mempertimbangkan bahagian yang tidak diisih.

Lelaran Seterusnya:

Proses ini berulang untuk setiap elemen yang tidak diisih yang tinggal.

Algoritma melelaran n-1 kali (dengan n ialah panjang tatasusunan). Selepas lelaran kelima (untuk tatasusunan enam elemen), elemen terakhir diisih secara tersirat.

Pelaksanaan Isih Pilihan (Java):

import java.util.Arrays;

public class SelectionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr) {
        int size = arr.length;

        // Iterate through the array size-1 times
        for (int i = 0; i < size - 1; i++) {
            int minIndex = i;
            // Find the minimum element in the unsorted part
            for (int j = i + 1; j < size; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap the minimum element with the first unsorted element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

Output:

Tatasusunan tidak diisih: [8, 2, 6, 4, 9, 1] Tatasusunan diisih: [1, 2, 4, 6, 8, 9]

Analisis Kerumitan:

• Kerumitan Masa: O(n²) dalam semua kes (terbaik, purata, paling teruk). Gelung bersarang sentiasa melaksanakan bilangan kali tetap tanpa mengira susunan input.
• Kerumitan Angkasa: O(1). Ia adalah algoritma di tempat, memerlukan ruang tambahan yang berterusan.

Kesimpulan:

Kerumitan masa O(n²) Isih Pilihan menjadikannya tidak cekap untuk set data yang besar. Ia paling sesuai untuk tatasusunan kecil atau situasi di mana kesederhanaan diutamakan berbanding prestasi.

Atas ialah kandungan terperinci Memahami Algoritma Isih Pemilihan (dengan Contoh dalam Java). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!