Penyelidikan mendalam tentang mengoptimumkan jenis gelembung Java

. Walaupun kerumitan masa isihan gelembung ialah O(n^2) dan kecekapannya agak rendah, ia masih merupakan pilihan yang mudah dan berkesan untuk pengisihan data berskala kecil. Dalam artikel ini, kami akan menyelidiki strategi pengoptimuman isihan gelembung Java dan memberikan contoh kod khusus.

Isih Buih Asas

Mula-mula, mari kita semak semula pelaksanaan asas isih gelembung. Isih gelembung menggunakan berbilang lelaran untuk membandingkan dan menukar elemen bersebelahan, mengisih elemen terbesar hingga akhir. Berikut ialah kaedah pelaksanaan mudah isihan gelembung:

public class BubbleSort {
    public static void bubbleSort(int[] array) {
        int n = array.length;

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // 交换相邻的两个元素
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Strategi pengoptimuman jenis gelembung
1. 
   
Walaupun isihan gelembung ialah algoritma pengisihan yang mudah dan mudah untuk dilaksanakan, kecekapannya tidak tinggi. Dalam sesetengah kes, isihan gelembung memerlukan banyak perbandingan dan pertukaran. Di sini kami menyediakan beberapa strategi pengoptimuman untuk meningkatkan kecekapan isihan gelembung.

2.1. Penamatan awal
Setiap lelaran isihan gelembung akan mengalihkan elemen terbesar semasa ke penghujung, tetapi untuk urutan tersusun, isihan gelembung tidak perlu meneruskan lelaran. Oleh itu, kita boleh memperkenalkan pembolehubah untuk menandakan sama ada terdapat operasi swap Jika tiada swap dilakukan, ini bermakna urutan itu teratur dan boleh ditamatkan lebih awal.

public static void bubbleSort(int[] array) {
    int n = array.length;

    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;  // 标记是否进行了交换操作

        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                // 交换相邻的两个元素
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;

                swapped = true;
            }
        }

        // 如果没有进行交换，则提前终止
        if (!swapped) {
            break;
        }
    }
}

2.2. Kawalan sempadan

Isih buih akan meletakkan elemen terbesar di penghujung setiap lelaran, yang bermaksud elemen berikut sudah teratur dan tidak perlu dibandingkan. Oleh itu, kita boleh menentukan sempadan lelaran seterusnya dengan merekodkan kedudukan pertukaran terakhir.

public static void bubbleSort(int[] array) {
    int n = array.length;

    int lastSwappedIndex = n - 1;  // 上一次交换的位置

    for (int i = 0; i < n - 1; i++) {
        int currentSwappedIndex = -1;  // 当前交换的位置

        for (int j = 0; j < lastSwappedIndex; j++) {
            if (array[j] > array[j + 1]) {
                // 交换相邻的两个元素
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;

                currentSwappedIndex = j;  // 记录当前交换的位置
            }
        }

        // 更新上一次交换的位置
        lastSwappedIndex = currentSwappedIndex;

        // 如果上一次交换的位置没有变化，则提前终止
        if (lastSwappedIndex == -1) {
            break;
        }
    }
}

Kesimpulan

Dengan memperkenalkan dua strategi pengoptimuman penamatan awal dan kawalan sempadan, kami boleh meningkatkan kecekapan isihan gelembung dengan ketara. Terutamanya apabila berurusan dengan urutan tersusun, strategi pengoptimuman ini boleh mengurangkan kerumitan masa isihan gelembung. Walau bagaimanapun, perlu diingatkan bahawa isihan gelembung masih tidak cekap apabila memproses data berskala besar, jadi dalam aplikasi praktikal, algoritma pengisihan yang lebih cekap mungkin perlu dipertimbangkan.

Di atas ialah perbincangan mendalam tentang strategi pengoptimuman isihan gelembung Java, serta contoh kod yang sepadan. Saya berharap melalui artikel ini, pembaca dapat lebih memahami dan menggunakan algoritma isihan gelembung.

Atas ialah kandungan terperinci Penyelidikan mendalam tentang mengoptimumkan jenis gelembung Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!