Cara cepat menguasai algoritma carian dan menyusun algoritma dalam pengaturcaraan Java

1. Algoritma Carian

Algoritma Binari

Carian Binari, juga dikenali sebagai carian binari, ialah algoritma carian yang cekap. Idea asasnya ialah: bahagikan tatasusunan (atau set) kepada dua Jika elemen tengah semasa adalah sama dengan elemen sasaran, carian berjaya jika elemen tengah semasa lebih besar daripada elemen sasaran, separuh kiri dicari ; jika elemen tengah semasa kurang daripada Untuk elemen sasaran, cari separuh kanan. Ulangi langkah di atas sehingga elemen sasaran ditemui atau julat carian kosong dan carian gagal.

Berikut ialah algoritma binari yang dilaksanakan dalam Java:

public static int binarySearch(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

Kaedah di atas menggunakan set tatasusunan integer tertib dan nilai sasaran sebagai parameter dan mengembalikan indeks nilai sasaran dalam tatasusunan ;Jika nilai sasaran tidak wujud dalam tatasusunan, kembalikan -1.

Inti algoritma ialah gelung while, yang dilaksanakan berulang kali apabila kiri dan kanan memenuhi syarat tertentu:

• Jika pertengahan sama dengan sasaran, pertengahan dikembalikan dan algoritma tamat ;

• Jika pertengahan lebih besar daripada sasaran, teruskan carian di sebelah kiri, iaitu, tetapkan ke kanan kepada pertengahan -

• Jika pertengahan kurang daripada sasaran, Kemudian teruskan carian di sebelah kanan, iaitu, tetapkan kiri ke pertengahan + 1.

Setiap kali melalui gelung, kami mengira indeks elemen tengah menggunakan pertengahan = kiri + (kanan - kiri) / 2. Perlu diingatkan bahawa kita mesti menggunakan bentuk kiri + kanan dan bukan bentuk (kiri + kanan) / 2, jika tidak, ia boleh menyebabkan masalah limpahan integer.

2. Algoritma pengisihan

Di Java, algoritma pengisihan dilaksanakan dengan melaksanakan antara muka Sebanding atau Pembanding. Berikut ialah beberapa algoritma pengisihan yang biasa digunakan dan kaedah pelaksanaannya:

Isih gelembung

Isih buih ialah algoritma pengisihan yang mudah. Ideanya adalah untuk sentiasa membandingkan dua elemen bersebelahan, dan jika susunannya salah, tukar kedudukan. Proses ini seperti buih air yang naik secara berterusan, jadi ia dipanggil pengasingan gelembung.

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

Isih pilihan

Idea isihan pilihan adalah untuk memilih elemen terkecil daripada elemen yang tidak diisih dan meletakkannya di penghujung pengisihan. Setiap kali elemen terkecil ditemui, kedudukannya ditukar dengan elemen pertama yang tidak diisih pada masa ini.

public static void selectionSort(int[] arr) {
    int minIndex;
    for (int i = 0; i < arr.length - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        //交换位置
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

Isih sisipan

Idea isihan sisipan adalah untuk memasukkan unsur yang tidak diisih ke dalam kedudukan yang diisih yang sesuai. Pilih elemen daripada elemen yang tidak diisih dan rentas elemen yang diisih dari belakang ke hadapan Jika ia lebih kecil daripada elemen yang diisih, gerakkan satu kedudukan ke belakang dan teruskan membandingkan sehingga anda menemui kedudukan yang lebih kecil daripada elemen yang tidak diisih , dan kemudian masukkannya di lokasi ini.

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

Isih cepat

Isih cepat ialah algoritma isihan berdasarkan idea bahagi dan takluk. Ia memilih titik pangsi, membahagi tatasusunan kepada dua subarray kurang daripada atau sama dengan titik pangsi dan lebih besar daripada titik pangsi, dan kemudian mengisih dua subarray secara rekursif.

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int i = left, j = right, pivot = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = pivot;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

Atas ialah kandungan terperinci Cara cepat menguasai algoritma carian dan menyusun algoritma dalam pengaturcaraan Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!