Penjelasan terperinci tentang algoritma pengisihan biasa yang dilaksanakan di Java

Algoritma pengisihan ialah konsep penting dalam sains komputer dan merupakan bahagian teras daripada banyak aplikasi. Dalam kehidupan dan kerja seharian, kita sering perlu mengisih data, seperti senarai pengisihan, pengisihan nilai, dsb. Java, sebagai bahasa pengaturcaraan yang digunakan secara meluas, menyediakan banyak algoritma pengisihan terbina dalam. Artikel ini akan memberikan pengenalan terperinci kepada algoritma pengisihan biasa yang dilaksanakan dalam Java.

1. Isih Buih

Isih Buih ialah salah satu algoritma pengisihan yang paling mudah tetapi paling perlahan. Ia melelar melalui keseluruhan tatasusunan, membandingkan elemen bersebelahan dan mengalihkan nilai yang lebih besar ke langkah demi langkah yang betul, akhirnya mengalihkan elemen terbesar ke penghujung tatasusunan. Proses ini serupa dengan proses buih naik dari dasar air ke permukaan, maka dinamakan jenis gelembung.

Berikut ialah algoritma isihan gelembung yang dilaksanakan dalam Java:

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

Kerumitan masa: O(n^2)

2 isihan ialah satu lagi algoritma pengisihan mudah yang terus memilih elemen terkecil yang tidak diisih dan mengalihkannya ke penghujung bahagian yang diisih. Isih pemilihan adalah serupa dengan isihan gelembung, tetapi ia tidak memerlukan pertukaran berterusan elemen dalam setiap lelaran, menjadikannya lebih pantas.

Berikut ialah algoritma isihan pemilihan yang dilaksanakan dalam Java:

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

Kerumitan masa: O(n^2)

3

Isihan sisipan ialah algoritma pengisihan yang lebih cekap yang mencari kedudukan dalam tatasusunan yang telah diisih dan memasukkan elemen yang tidak diisih ke dalam kedudukan yang betul. Isihan sisipan sesuai untuk set data yang lebih kecil kerana swap yang lebih sedikit.

Berikut ialah algoritma isihan sisipan yang dilaksanakan dalam Java:

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Kerumitan masa: O(n^2)

4

Isih cepat ialah algoritma pengisihan yang cekap yang menggunakan idea bahagi-dan-takluk untuk membahagi tatasusunan kepada sub-tatasusunan yang lebih kecil, kemudian mengisih sub-tatasusunan melalui rekursi, dan menggabungkannya untuk membentuk hasil isihan akhir. Kunci untuk mengisih pantas ialah memilih elemen tengah dan mengisih mengikut saiz.

Berikut ialah algoritma isihan pantas yang dilaksanakan dalam Java:

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 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++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

Kerumitan masa: O(n log n)

5

Isih Cantum ialah satu lagi algoritma pengisihan biasa yang menggunakan idea bahagi-dan-takluk untuk membahagi tatasusunan kepada sub-tatasusunan yang lebih kecil, kemudian mengisih satu demi satu dan menggabungkannya untuk menjana hasil isihan terakhir. Isih gabungan biasanya lebih perlahan daripada isihan cepat, tetapi ia lebih stabil.

Berikut ialah algoritma isihan gabungan yang dilaksanakan dalam Java:

public static void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

public static void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int[] L = new int[n1];
    int[] R = new int[n2];
    for (int i = 0; i < n1; i++) {
        L[i] = arr[l + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[m + j + 1];
    }
    int i = 0, j = 0;
    int k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Kerumitan masa: O(n log n)

Kesimpulan

Perkara di atas adalah perkara biasa dalam algoritma pengisihan Java dan butiran pelaksanaannya. Isih buih dan isihan pilihan adalah lebih mudah tetapi mempunyai kerumitan masa yang lebih tinggi; Dalam penggunaan sebenar, pemilihan perlu dibuat berdasarkan sampel data yang berbeza dan keperluan sebenar.

Atas ialah kandungan terperinci Penjelasan terperinci tentang algoritma pengisihan biasa yang dilaksanakan di Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!