Analisis mendalam algoritma isihan gelembung Java dan kaedah pelaksanaan biasa

Penjelasan terperinci tentang algoritma isihan gelembung Java dan kaedah pelaksanaan biasa

Pengenalan:
Isih gelembung ialah algoritma pengisihan asas yang mengisih dengan membandingkan dan menukar elemen bersebelahan. Walaupun kerumitan masa isihan gelembung adalah tinggi (O(n^2)), disebabkan pelaksanaannya yang mudah, ia adalah asas untuk memahami algoritma pengisihan dan juga merupakan salah satu soalan biasa dalam temu bual. Artikel ini akan memperkenalkan secara terperinci prinsip, langkah dan kaedah pelaksanaan biasa algoritma isihan gelembung Java, dan juga memberikan contoh kod.

1. Prinsip dan langkah:
Idea asas penyisihan gelembung adalah untuk membandingkan elemen yang akan diisih dari awal hingga akhir Jika elemen bersebelahan berada dalam susunan terbalik, tukarkannya sehingga keseluruhan jujukan. Langkah-langkah khusus adalah seperti berikut:

1. Mulakan dari elemen pertama urutan untuk diisih dan bandingkan dua elemen bersebelahan.
2. Jika elemen pertama lebih besar daripada elemen kedua, tukar kedudukan mereka.
3. Teruskan bandingkan elemen kedua dan elemen ketiga, tukar elemen tersebut jika tertib terbalik, jika tidak pastikan ia tidak berubah.
4. Ulang langkah di atas sehingga keseluruhan urutan adalah teratur. . Kod pelaksanaan khusus adalah seperti berikut:

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;
            }
        }
    }
}

Pengisihan gelembung yang dioptimumkan:

Dalam pengisihan gelembung biasa, setiap pas pengisihan mesti merentasi keseluruhan urutan untuk diisih, termasuk bahagian yang telah dipesan. Malah, jika tiada pertukaran dilakukan dalam pas pengisihan tertentu, ini bermakna keseluruhan jujukan adalah teratur dan gelung boleh keluar terus. Ini boleh mengurangkan perbandingan yang tidak perlu dan operasi pertukaran serta meningkatkan kecekapan pengisihan. Kod pelaksanaan khusus adalah seperti berikut:
1. 
   

   public static void bubbleSortOptimized(int[] arr) {
       int n = arr.length;
       boolean swapped; // 标识是否有交换操作
       for (int i = 0; i < n - 1; i++) {
           swapped = false;
           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;
                   swapped = true;
               }
           }
           // 如果没有进行任何交换，说明已经有序，直接退出循环
           if (!swapped) {
               break;
           }
       }
   }

3. Contoh dan ujian:

Contoh diberikan di bawah untuk menguji dan mengesahkan ketepatan kod:

public static void main(String[] args) {
    int[] arr = {64, 34, 25, 12, 22, 11, 90};
    
    System.out.println("排序前：");
    for (int num : arr) {
        System.out.print(num + " ");
    }
    
    bubbleSortOptimized(arr);
    
    System.out.println("
排序后：");
    for (int num : arr) {
        System.out.print(num + " ");
    }
}

2. Hasil output ialah:
   Sebelum mengisih: 64 34 25 12 22 11 90
Isih Selepas: 11 12 22 25 34 64 90

Kesimpulan:
Isih buih ialah algoritma pengisihan yang mudah tetapi kurang cekap yang mencapai pengisihan melalui perbandingan dan pertukaran antara elemen bersebelahan. Artikel ini memperkenalkan prinsip, langkah dan kaedah pelaksanaan biasa algoritma isihan gelembung Java secara terperinci dan memberikan contoh kod untuk ujian dan pengesahan. Dalam aplikasi praktikal, kita boleh memilih jenis gelembung biasa atau jenis gelembung yang dioptimumkan mengikut keadaan tertentu untuk meningkatkan kecekapan pengisihan.

Atas ialah kandungan terperinci Analisis mendalam algoritma isihan gelembung Java dan kaedah pelaksanaan biasa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!