Penjelasan terperinci tentang algoritma pengisihan yang biasa digunakan dan kaedah pelaksanaan dalam Java

1. Isih pilihan

Isihan pilihan ialah algoritma pengisihan yang mudah dan intuitif Tidak kira apa data yang dimasukkan, kerumitan masa ialah O(n²). Jadi apabila menggunakannya, lebih kecil saiz data, lebih baik. Satu-satunya kelebihan mungkin ia tidak menduduki ruang memori tambahan

Mula-mula cari elemen terkecil (besar) dalam urutan tidak diisih dan simpannya pada kedudukan permulaan. urutan disusun.

Kemudian teruskan mencari elemen terkecil (terbesar) daripada unsur yang tidak diisih yang tinggal, dan kemudian meletakkannya di penghujung urutan yang diisih.

Ulang langkah kedua sehingga semua elemen diisih.

public static void selectSort(int[] arr) {
        //选择排序
        if(arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int minValueIndex = i;
            for (int j = i+1; j < n; j++) {
                minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
            }
            swap(arr,i,minValueIndex);
        }
    }
    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] arr = {7,5,1,9,4,2,6};
        printArray(arr);
        selectSort(arr);
        printArray(arr);
    }

2. Isih gelembung

**Prinsip algoritma isihan gelembung adalah seperti berikut: **

1. Perbandingan elemen bersebelahan. Jika yang pertama lebih besar daripada yang kedua, tukar kedua-duanya.

2. Lakukan perkara yang sama untuk setiap pasangan elemen bersebelahan, daripada pasangan pertama di awal hingga pasangan terakhir di penghujung. Pada ketika ini, elemen terakhir hendaklah nombor terbesar.

3 Ulang langkah di atas untuk semua elemen kecuali yang terakhir.

4 Teruskan mengulangi langkah di atas untuk semakin sedikit elemen setiap kali sehingga tiada pasangan nombor untuk dibandingkan.

public static void bubbleSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                }
            }
        }
    }
     public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) {
        int[] arr = {14,6,3,10,2};
        printArray(arr);
        bubbleSort(arr);
        printArray(arr);
    }

3. Isih sisipan

Isih sisipan bermaksud antara elemen yang hendak diisih, andaikan bahawa n-1 sebelumnya (di mana n> =2 ) nombor sudah dalam tertib Sekarang masukkan nombor ke-n ke dalam urutan yang telah disusun sebelumnya, dan kemudian cari kedudukan yang sesuai supaya urutan di mana nombor ke-n dimasukkan juga mengikut tertib. Proses memasukkan semua elemen mengikut kaedah ini sehingga keseluruhan urutan adalah teratur dipanggil isihan sisipan

public static void insertSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int currIndex = i;
            while(currIndex - 1 >= 0 && arr[currIndex-1] > arr[currIndex]) {
                swap(arr,currIndex,currIndex-1);
                currIndex--;
            }
        }
    }

    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) {
        int[] arr = {3,6,1,5,2};
        printArray(arr);
        insertSort(arr);
        printArray(arr);
    }

Isih sisipan pengoptimuman

public static void insertSort1(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            for (int j = i-1; j >= 0; j--) {
                if(arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                }else {
                    break;
                }
            }
        }
    }

Atas ialah kandungan terperinci Penjelasan terperinci tentang algoritma pengisihan yang biasa digunakan dan kaedah pelaksanaan dalam Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!