編程中遞歸與排序分別是什么

這篇文章主要介紹“編程中遞歸與排序分別是什么”，在日常操作中，相信很多人在編程中遞歸與排序分別是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”編程中遞歸與排序分別是什么”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

遞歸

遞歸需要滿足的三個(gè)條件

• 一個(gè)問題的解可以分為幾個(gè)子問題的解

• 此問題與子問題，除了數(shù)據(jù)規(guī)模不一樣，求解思路完全一樣

• 存在遞歸終止條件

怎么寫遞歸代碼

寫遞歸代碼的關(guān)鍵就是找到如何將大問題分解為小問題的規(guī)律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼。
只要遇到遞歸，我們就把它抽象成一個(gè)遞推公式，不用想一層層的調(diào)用關(guān)系，不要試圖用人腦去分解遞歸的每個(gè)步驟。

遞歸注意事項(xiàng)

警惕堆棧溢出

如果遞歸調(diào)用層很深，則有可能會(huì)出現(xiàn)堆棧溢出；可通過限制最大深度解決此問題：超過一定的深度直接返回報(bào)錯(cuò)。

避免重復(fù)計(jì)算

通過散列表保存已求解過的表達(dá)式；當(dāng)遞歸調(diào)用到此表達(dá)式時(shí)，先判斷是夠已求解過。

排序

最常見的排序：冒泡排序、插入排序、選擇排序、歸并排序、快速排序、計(jì)數(shù)排序、基數(shù)排序、桶排序。

如何分析一個(gè)算法

排序算法的執(zhí)行效率

• 最好、最壞、平均情況時(shí)間復(fù)雜度

• 時(shí)間復(fù)雜度的系數(shù)、常數(shù)、低階

• 比較次數(shù)和交換(或移動(dòng))次數(shù)

排序算法的內(nèi)存消耗

算法的內(nèi)存消耗可以通過空間復(fù)雜度來衡量；原地排序特指空間復(fù)雜度為O(1)的排序算法

排序算法的穩(wěn)定性

待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變。
穩(wěn)定的排序算法可以保持相同的兩個(gè)對象，在排序之后的前后順序不變。

冒泡排序

冒泡排序只操作相鄰的兩個(gè)元素，每次操作時(shí)比較相鄰的兩個(gè)元素判斷是否滿足大小關(guān)系要求，不滿足時(shí)就交換位置。

• 從執(zhí)行效率上看：冒泡排序的最好情況時(shí)間復(fù)雜度為O(n),最壞情況時(shí)間復(fù)雜度為O(n^2 ),平均情況時(shí)間復(fù)雜度為O(n^2 )。

• 從內(nèi)存消耗上看：冒泡排序只涉及相鄰元素交換操作，所以空間復(fù)雜度為O(1),是一個(gè)原地排序算法。

• 從穩(wěn)定性上看：相鄰兩個(gè)元素大小相等時(shí)我們不做交換，所以大小相等的兩個(gè)元素在排序后順序不會(huì)改變，屬于穩(wěn)定的排序算法。

代碼實(shí)現(xiàn)

public static <T extends Comparable> T[] bubbleSort(T[] arrays) {
    for (int i = 0; i < arrays.length; i++) {
        boolean unUse = true;
        for (int j = 1; j < arrays.length - i; j++) {
            //如果前一個(gè)元素大于當(dāng)前元素 就交換雙方位置
            if (arrays[j - 1].compareTo(arrays[j]) > 0) {
                T t = arrays[j - 1];
                arrays[j - 1] = arrays[j];
                arrays[j] = t;
                unUse = false;
            }
        }
        //如果整輪下來沒有交換動(dòng)作，說明排序已完成
        if (unUse) break;
    }
    return arrays;
}

插入排序

插入排序?qū)?shù)組分為已排序區(qū)和未排序區(qū)，核心思想是取未排序區(qū)的元素在已排序區(qū)中找到合適的位置插入，保證已排序區(qū)的數(shù)據(jù)一直是有序的。

• 從執(zhí)行效率上看，插入排序的最好情況時(shí)間復(fù)雜度為O(n),最壞情況時(shí)間復(fù)雜度為O(n^2 ),平均情況時(shí)間復(fù)雜度為O(n^2 )。

• 從內(nèi)存消耗上看：插入排序也不需要額外的存儲(chǔ)空間，所以空間復(fù)雜度為O(1),是一個(gè)原地排序算法。

• 從穩(wěn)定性上看：對于值相同的元素，后面出現(xiàn)的元素插入到前面出現(xiàn)元素的后面，所以兩個(gè)元素在排序后順序不會(huì)改變，屬于穩(wěn)定的排序算法。

代碼實(shí)現(xiàn)

public static <T extends Comparable> T[] insertionSort(T[] arrays) {
    if (arrays.length < 2) return arrays;
    for (int i = 1; i < arrays.length; i++) {
        T t = arrays[i];
        for (int j = 0; j < i; j++) {
            if (t.compareTo(arrays[j]) < 0) {
                System.arraycopy(arrays, j, arrays, j + 1, i - j);
                arrays[j] = t;
                break;
            }
        }
    }
    return arrays;
}

選擇排序

選擇排序也是將數(shù)據(jù)分為已排序區(qū)和未排序區(qū)，和插入排序不同的是：每次將未排序區(qū)中最小的元素放入到已排序區(qū)的尾部。

• 從執(zhí)行效率上看，插入排序的最好情況時(shí)間復(fù)雜度為O(n^2 ),最壞情況時(shí)間復(fù)雜度為O(n^2 ),平均情況時(shí)間復(fù)雜度也為O(n^2 )。

• 從內(nèi)存消耗上看：選擇排序也不需要額外的存儲(chǔ)空間，所以空間復(fù)雜度為O(1),是一個(gè)原地排序算法。

• 從穩(wěn)定性上看：未排序區(qū)最小元素與首元素交換位置時(shí)，可能會(huì)改變相同值的兩個(gè)元素的順序，所以選擇排序?qū)儆诓环€(wěn)定的排序算法。

代碼實(shí)現(xiàn)

public static <T extends Comparable> T[] selectionSort(T[] arrays) {
    if (arrays.length < 2) return arrays;
    for (int i = 0; i < arrays.length; i++) {
        int minIndex = i;//定義最小值索引
        T min = arrays[minIndex];//默認(rèn)第一個(gè)是最小值
        for (int j = i + 1; j < arrays.length; j++) {
            if (arrays[j].compareTo(min) < 0) {
                minIndex = j;
                min = arrays[minIndex];
            }
        }
        //交換值
        arrays[minIndex] = arrays[i];
        arrays[i] = min;
    }
    return arrays;
}

總結(jié)

我們從執(zhí)行效率、內(nèi)存消耗和穩(wěn)定性三個(gè)方面分析了三種時(shí)間復(fù)雜度為O(n^2 )的排序算法：

到此，關(guān)于“編程中遞歸與排序分別是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！