Beberapa algoritma pengisihan gelembung Java biasa: susun dalam tertib menaik

Isih gelembung Java: beberapa kaedah penulisan biasa daripada kecil hingga besar, contoh kod khusus diperlukan

Isih gelembung ialah algoritma pengisihan mudah yang berulang kali membandingkan dua elemen bersebelahan dan menyusunnya mengikut saiz Pertukaran dilakukan sehingga keseluruhan urutan adalah teratur. Di Jawa, terdapat beberapa kaedah penulisan biasa dan kaedah pengoptimuman untuk pengisihan gelembung Berikut akan memperkenalkan lima kaedah penulisan biasa dan memberikan contoh kod khusus.

Cara pertama untuk menulis: isihan gelembung biasa

Isih gelembung biasa secara langsung menempatkan dua peringkat gelung Gelung luar mengawal bilangan pusingan perbandingan dan gelung dalam melakukan perbandingan dan pertukaran tertentu.

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

Cara penulisan kedua: Mengoptimumkan gelung luar

Berdasarkan cara penulisan pertama, jika tiada pertukaran dilakukan dalam satu pusingan pengisihan, ini bermakna tatasusunan sudah teratur dan pengisihan boleh ditamatkan lebih awal . Untuk mencapai pengoptimuman ini, kita boleh menambah bit bendera untuk merekodkan sama ada pertukaran berlaku.

public static void bubbleSort2(int[] arr) {
    int n = arr.length;
    boolean swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

Cara penulisan ketiga: Mengoptimumkan gelung dalaman

Berdasarkan cara penulisan kedua, anda boleh mendapati bahawa setiap pusingan perbandingan akan "mengebulkan" elemen terbesar hingga akhir. Oleh itu, bilangan perbandingan gelung dalam setiap pusingan boleh dikurangkan secara beransur-ansur.

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

Cara penulisan keempat: Mengoptimumkan gelung dalam dan luar

Berdasarkan cara penulisan ketiga, jika tatasusunan tidak bertukar dalam pusingan perbandingan tertentu, ini bermakna elemen di belakang tatasusunan sudah teratur , dan pengisihan boleh ditamatkan lebih awal.

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

Cara penulisan kelima: mengoptimumkan gelung luar dan gelung dalam

Berdasarkan cara penulisan keempat, kita dapati bahawa setiap pusingan perbandingan akan mencari elemen terbesar bagi pusingan semasa dan meletakkannya di tempat yang betul kedudukan . Oleh itu, kita boleh mencari kedua-dua nilai maksimum dan minimum dalam setiap pusingan perbandingan dan menyusunnya.

public static void bubbleSort5(int[] arr) {
    int n = arr.length;
    int lastSwapIndex, leftBoundary, rightBoundary;
    leftBoundary = 0;
    rightBoundary = n - 1;
    while (leftBoundary < rightBoundary) {
        lastSwapIndex = 0;
        for (int j = leftBoundary; j < rightBoundary; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        rightBoundary = lastSwapIndex;
        for (int j = rightBoundary; j > leftBoundary; j--) {
            if (arr[j] < arr[j-1]) {
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                lastSwapIndex = j - 1;
            }
        }
        leftBoundary = lastSwapIndex;
    }
}

Di atas adalah lima kaedah penulisan jenis gelembung Setiap kaedah penulisan mempunyai kaedah pengoptimuman yang berbeza Dalam penggunaan sebenar, anda boleh memilih kaedah penulisan yang sesuai mengikut situasi tertentu. Melalui pengoptimuman ini, kecekapan pengisihan gelembung dapat dipertingkatkan dan masa pengisihan dapat dikurangkan.

Walaupun isihan gelembung adalah mudah, prestasinya adalah lemah apabila mengisih data berskala besar. Oleh itu, dalam aplikasi praktikal, algoritma pengisihan yang lebih cekap, seperti pengisihan cepat, pengisihan gabungan, dsb., lebih biasa digunakan.

Atas ialah kandungan terperinci Beberapa algoritma pengisihan gelembung Java biasa: susun dalam tertib menaik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!