Rumah  >  Artikel  >  Java  >  Algoritma isihan pantas dilaksanakan dalam bahasa Java

Algoritma isihan pantas dilaksanakan dalam bahasa Java

WBOY
WBOYasal
2024-02-19 13:35:05768semak imbas

Algoritma isihan pantas dilaksanakan dalam bahasa Java

Kaedah pelaksanaan algoritma isihan pantas berdasarkan bahasa Java

Isih cepat ialah algoritma isihan yang cekap, yang sering digunakan untuk mengisih sejumlah besar data. Artikel ini akan memperkenalkan kaedah pelaksanaan algoritma pengisihan pantas berdasarkan bahasa Java dan memberikan contoh kod khusus.

Idea asas isihan pantas ialah membahagikan data untuk diisih kepada dua bahagian bebas Contohnya, menggunakan satu elemen sebagai nilai standard, elemen yang lebih kecil daripada nilai diletakkan di sebelah kiri, dan elemen yang lebih besar daripada nilai diletakkan di sebelah kanan. Kemudian cepat susun kedua-dua bahagian ini secara berasingan sehingga keseluruhan urutan diisih.

Pertama, kita perlu melaksanakan fungsi Partition untuk membahagikan data. Fungsi ini membahagikan keseluruhan jujukan kepada dua bahagian dengan memilih Pivot (biasanya memilih elemen pertama dalam jujukan) dan mengembalikan kedudukan Pivot. Kod khusus adalah seperti berikut:

public class QuickSort {
    public int partition(int[] array, int low, int high) {
        int pivot = array[low]; // 选择第一个元素作为Pivot
        while (low < high) {
            while (low < high && array[high] >= pivot) {
                high--;
            }
            array[low] = array[high]; // 将小于Pivot的元素移到左边

            while (low < high && array[low] <= pivot) {
                low++;
            }
            array[high] = array[low]; // 将大于Pivot的元素移到右边
        }
        array[low] = pivot; // 将Pivot放到正确的位置
        return low; // 返回Pivot的位置
    }
}

Seterusnya, kita perlu melaksanakan fungsi QuickSort untuk mengisih keseluruhan jujukan. Kod khusus adalah seperti berikut:

public class QuickSort {
    // ... 上面的代码省略 ...

    public void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high); // 划分序列
            quickSort(array, low, pivotIndex - 1); // 对左边序列进行快速排序
            quickSort(array, pivotIndex + 1, high); // 对右边序列进行快速排序
        }
    }
}

Akhir sekali, kita boleh menggunakan kelas QuickSort untuk mengisih tatasusunan integer. Kod khusus adalah seperti berikut:

public class Main {
    public static void main(String[] args) {
        int[] array = {5, 2, 6, 3, 1, 4}; // 待排序的数组

        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(array, 0, array.length - 1); // 对数组进行快速排序

        System.out.print("排序结果:");
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

Di atas ialah kaedah untuk melaksanakan algoritma isihan pantas berdasarkan bahasa Java. Dengan melaksanakan fungsi Partition dan fungsi QuickSort, kita boleh mengisih tatasusunan integer dengan cepat. Algoritma ini mempunyai kerumitan masa O(nlogn) dan merupakan algoritma pengisihan yang sangat cekap.

Atas ialah kandungan terperinci Algoritma isihan pantas dilaksanakan dalam bahasa Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn