java中排序規(guī)則與查找算法如何實(shí)現(xiàn)

這篇文章主要介紹了java中排序規(guī)則與查找算法如何實(shí)現(xiàn)，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

一、遞歸算法

遞歸就是方法自己調(diào)用自己,每次調(diào)用時(shí)傳入不同的變量,可以讓代碼變得簡(jiǎn)潔。遞歸算法在計(jì)算機(jī)科學(xué)中是指一種通過(guò)重復(fù)將問(wèn)題分解為同類的子問(wèn)題而解決問(wèn)題的方法，遞歸式方法可以被用于解決很多的計(jì)算機(jī)科學(xué)問(wèn)題，因此它是計(jì)算機(jī)科學(xué)中十分重要的一個(gè)概念。

基礎(chǔ)案例：通過(guò)遞歸打印數(shù)據(jù)；

public class M01_Recursion {
    public static void main(String[] args) {
        printNum(3);
    }
    private static void printNum (int num){
        if (num > 1){
            printNum(num-1);
        }
        System.out.println("num="+num);
    }
}

遞歸圖解：

基于棧結(jié)構(gòu)的特點(diǎn)，遞歸調(diào)用會(huì)形成如上的結(jié)構(gòu)，當(dāng)所有遞歸方法入棧成功后，在依次執(zhí)行出棧動(dòng)作，打印數(shù)據(jù)結(jié)果。

在實(shí)際開(kāi)發(fā)中遞歸經(jīng)常用來(lái)接近樹(shù)結(jié)構(gòu)問(wèn)題，階乘算法，排序查找等數(shù)學(xué)類問(wèn)題。

遞歸算法的條件必須要不斷接近退出條件，不然很容易出現(xiàn)無(wú)限循環(huán)導(dǎo)致內(nèi)存溢出異常問(wèn)題。

二、排序算法

排序算法就是使一組數(shù)據(jù)記錄，按照特定的排序策略，遞增或遞減的排列起來(lái)的操作；常用的排序算法：冒泡排序，選擇排序，插入排序，希爾排序，歸并排序，快速排序，基數(shù)排序等；排序算法選擇：不同的排序業(yè)務(wù)可以通過(guò)多種算法測(cè)試，復(fù)雜度低，耗時(shí)短的優(yōu)先使用。

1、冒泡排序

通過(guò)對(duì)排序序列依次比較相鄰元素的值，若發(fā)現(xiàn)逆序則交換，使值較大的元素逐漸從前移向后部，算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由排序交換慢慢浮到數(shù)列的一端，就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣，故名冒泡排序。

public class M02_Bubble {
    public static void main(String[] args) {
        int[] arr = {3,7,5,9,6};
        bubbleSort(arr);
        for (int num:arr){
            System.out.println(num);
        }
    }
    public static void bubbleSort(int[] arr) {
        // 聲明臨時(shí)變量
        int temp = 0;
        // 排序總趟數(shù)
        for (int i = 0; i < arr.length - 1; i++) {
            // 元素交換
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 位置交換
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

核心思路：

排序趟數(shù)只有多少元素，理論上要進(jìn)行處理的次數(shù)；每個(gè)元素的位置交換都需要一次完整對(duì)比，外層循環(huán)總控制。內(nèi)層循環(huán)交換單個(gè)元素位置。

2、選擇排序

選擇排序原理：第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，然后再?gòu)氖Ｓ嗟奈磁判蛟刂袑ふ业阶钚。ù螅┰兀缓蠓诺揭雅判虻男蛄械哪┪?。以此類推，直到全部待排序的?shù)據(jù)元素的個(gè)數(shù)為零。

public class M03_Selection {
    public static void main(String[] args) {
        int[] arr = {30,70,50,90,60};
        selectionSort(arr);
    }
    public static void selectionSort (int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            int minData = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                // 假設(shè)最小值判斷
                if (minData > arr[j]) {
                    // 交換小值
                    minData = arr[j];
                    // 重置 minIndex，遞增
                    minIndex = j;
                }
            }
            // 最小值交換放在arr[0]位置
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = minData ;
            }
            System.out.println("第"+(i+1)+"輪排序："+Arrays.toString(arr));
        }
    }
}

輸出結(jié)果：

第1輪排序：[30, 70, 50, 90, 60]
第2輪排序：[30, 50, 70, 90, 60]
第3輪排序：[30, 50, 60, 90, 70]
第4輪排序：[30, 50, 60, 70, 90]

3、插入排序

基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素，把它依次與有序表元素進(jìn)行比較，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表。在實(shí)現(xiàn)過(guò)程使用雙層循環(huán)，外層循環(huán)對(duì)除了第一個(gè)元素之外的所有元素，內(nèi)層循環(huán)對(duì)當(dāng)前元素前面有序表進(jìn)行待插入位置查找，并進(jìn)行移動(dòng)。

public class M04_Insert {
    public static void main(String[] args) {
        int[] arr = {10,40,90,20,80};
        insertSort(arr);
    }
    public static void insertSort (int[] arr) {
        int insertValue = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            // 待插入數(shù)的值和下標(biāo)
            insertValue = arr[i];
            insertIndex = i - 1;
            // 寫入位置
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertValue;
            }
            System.out.println("第" + i + "輪插入排序："+Arrays.toString(arr));
        }
    }
}

輸出結(jié)果：

第1輪插入排序：[10, 40, 90, 20, 80]
第2輪插入排序：[10, 40, 90, 20, 80]
第3輪插入排序：[10, 20, 40, 90, 80]
第4輪插入排序：[10, 20, 40, 80, 90]

三、查找算法

查找算法是指在一組元素中尋找一個(gè)特定的信息元素，在計(jì)算機(jī)應(yīng)用中，查找是常用的基本運(yùn)算，例如編譯程序中符號(hào)表的查找；常用的查找算法有：順序查找，二分查找，插值查找，斐波那契查找。

1、順序查找

順序查找是按照序列原有順序?qū)σ唤M元素進(jìn)行遍歷，并與要查找的元素逐個(gè)比較的基本查找算法。

public class M05_OrderFind {
    public static void main(String[] args) {
        String[] arr = {"first","second","third"};
        System.out.println(seqSearch(arr,"second"));
    }
    public static int seqSearch(String[] arr, String value) {
        // 數(shù)組下標(biāo)，-1代表沒(méi)有
        int findIndex = -1 ;
        // 遍歷并逐個(gè)對(duì)比
        for (int i = 0; i < arr.length; i++) {
            if(value.equals(arr[i])) {
                return i ;
            }
        }
        return findIndex ;
    }
}

2、二分查找

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。

public class M06_BinaryFind {
    public static void main(String[] args) {
        int arr[] = { 10, 20, 30, 40, 50 };
        int index = binarySearch (arr, 0, arr.length - 1, 40);
        System.out.println("index="+index);
    }
    public static int binarySearch(int[] arr, int leftIndex, int rightIndex, int findValue) {
        // leftIndex > rightIndex,沒(méi)有查到
        if (leftIndex > rightIndex) {
            return -1;
        }
        int midIndex = (leftIndex + rightIndex) / 2;
        int midValue = arr[midIndex];
        // 向左遞歸
        if (findValue < midValue) {
            return binarySearch(arr, leftIndex, midIndex - 1, findValue);
        // 向右遞歸
        } else if (findValue > midValue) {
            return binarySearch(arr, midIndex + 1, rightIndex, findValue);
        // 直接找到
        } else {
            return midIndex;
        }
    }
}

如果要查詢的元素是沒(méi)有順序的，可以基于上述模塊二中的排序算法，先排序再查找。

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“java中排序規(guī)則與查找算法如何實(shí)現(xiàn)”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!