常用排序算法

在Java中存在如Arrays.sort(nums);這樣的快捷方法，使得在實(shí)際刷題過程中很少需要自己手寫排序算法。但是在面試中，一旦面試官問類似問題，回答不上來，就很容易被認(rèn)為代碼能力不過關(guān)。以下展示常用的一些排序算法。

冒泡排序：重復(fù)地遍歷要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就交換位置。這個(gè)過程持續(xù)對數(shù)列的末尾進(jìn)行，直到整個(gè)數(shù)列都排序完成。其時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。

選擇排序：其基本思想是每次從待排序的元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始或結(jié)束位置，直到全部待排序的元素排完。其時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。

插入排序：其基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中。其時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。 將當(dāng)前值key和前面的值進(jìn)行比較，如果前面的值大于key 則將值往后移1位，在不小于key的位置插入當(dāng)前值。

歸并排序：一種分治思想的排序算法，它的基本思想是將待排序的數(shù)組分成若干個(gè)子序列，每個(gè)子序列都是有序的，然后再將子序列合并成一個(gè)有序的數(shù)組。

歸并排序圖解.gif

具體實(shí)現(xiàn)代碼如下：

public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
public static void merge(int[] arr, int left, int mid, int right) {
    // 左子數(shù)組 L 的大小
    int n1 = mid - left + 1;
    // 右子數(shù)組 R 的大小
    int n2 = right - mid;
    // 創(chuàng)建兩個(gè)臨時(shí)數(shù)組 L 和 R ，分別用來存儲(chǔ)左子數(shù)組和右子數(shù)組的元素
    int[] L = new int[n1];
    int[] R = new int[n2];
    // 使用 for 循環(huán)將原始數(shù)組 arr 中的元素復(fù)制到臨時(shí)數(shù)組 L 和 R 中，分別從 left 和 mid + 1 開始
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }
    // 初始化三個(gè)變量 i、j和k，分別指向數(shù)組 L 、R 和原始數(shù)組 arr 的起始位置
    int i = 0, j = 0, k = left;
    // 使用 while 循環(huán)，比較 L 和 R 的元素，并將較小的元素放回原始數(shù)組 arr 中
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 當(dāng) L 或 R 中的元素用完時(shí)，將剩余的元素依次放回原始數(shù)組 arr 中
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
    // merge方法執(zhí)行完畢后，兩個(gè)子數(shù)組范圍內(nèi)的元素已經(jīng)按照從小到大的順序合并到了原始數(shù)組 arr 中
}

代碼內(nèi)含一個(gè)遞歸調(diào)用，且每次都是n/2，同時(shí)每次調(diào)用過程中都做了n次比較，所以歸并排序的時(shí)間復(fù)雜度為O()；每次都需要?jiǎng)?chuàng)建和為對應(yīng)長度的左右子數(shù)組，其空間復(fù)雜度為O(n)。

快速排序：一種分治思想的排序算法，它的基本思想是通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，然后再分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序的目的。

快速排序圖解.gif

其具體代碼如下：

// 接收一個(gè)數(shù)組 arr，一個(gè)低索引 low ，和一個(gè)高索引 high 作為參數(shù)
    public static void quickSort(int[] arr, int low, int high) {
        // 檢查 low 是否小于 high。如果不是，則意味著數(shù)組只有一個(gè)元素或?yàn)榭?，因此不需要排?        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }
/**
 * 取最后一個(gè)元素作為樞軸元素，將較小的元素放在左邊，較大的元素放在右邊
 * @param arr 輸入數(shù)組
 * @param low 低位索引
 * @param high 高位索引
 * @return 樞軸所在位置
 */
private static int partition(int[] arr, int low, int high) {
    // 將最后一個(gè)元素作為樞軸元素
    int pivot = arr[high];
    // 將 i 初始化為 low - 1，用于跟蹤較小元素的索引
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            // 如果當(dāng)前元素 arr[j] 小于樞軸元素，則增加 i 并交換 arr[i] 和 arr[j]
            i++;
            // 將當(dāng)前元素 arr[j] 放在較小元素索引位置，將較小元素放在前面
            swap(arr, i, j);
        }
        // 其他情況，則較小元素索引沒有增加，說明當(dāng)前元素應(yīng)該放在右邊
    }
    // 將樞軸元素（ arr[high] ）與索引 i + 1 處的元素交換
    // 確保樞軸元素左邊是較小元素，右邊是較大元素
    swap(arr, i + 1, high);
    // 將 i + 1 作為樞軸索引返回，樞軸元素已是實(shí)際排序后的位置
    return i + 1;
}
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

代碼內(nèi)含遞歸調(diào)用，每次都將其分為2部分，同時(shí)調(diào)用過程中都做了n次比較，所以快速排序的時(shí)間復(fù)雜度為O()；在執(zhí)行過程中并沒有開辟額外的空間來存儲(chǔ)數(shù)據(jù)，而是使用了原地排序，除了遞歸調(diào)用的棧空間外，算法本身只使用了常量的額外空間，其空間復(fù)雜度為O()。注意快排在原先已有序的基礎(chǔ)上時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(n)，但是這樣沒啥意義，所以還是以前面的結(jié)論為公認(rèn)。

桶排序：一種非比較排序算法，它的基本思想是將待排序的數(shù)組分到有限數(shù)量的桶里，然后對每個(gè)桶進(jìn)行排序，最后依次將所有桶中的元素取出來，組成有序的數(shù)組。其本質(zhì)是為每個(gè)目標(biāo)值設(shè)立一個(gè)桶，桶內(nèi)記錄的是此值的出現(xiàn)次數(shù)（也可以是其他屬性），然后對桶根據(jù)其元素值進(jìn)行排序。

桶排序圖解.gif

其時(shí)間復(fù)雜度為O(n2)，因?yàn)閷?shí)際上它并沒有進(jìn)行比較，空間復(fù)雜度為O(n)，隨著屬性值增多空間也會(huì)擴(kuò)大。

快速選擇算法：

[215]數(shù)組中的第K個(gè)最大元素

題設(shè)：給定整數(shù)數(shù)組 nums 和整數(shù) k，請返回?cái)?shù)組中第 k 個(gè)最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素。你必須設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 的算法解決此問題。

思路：快速選擇類似于快速排序，只不過是找到第k大的pivot，而不需要對其左右進(jìn)行排序。具體思路為設(shè) N 為數(shù)組長度，如果某次哨兵劃分后，基準(zhǔn)數(shù)的索引正好是N?k ，則意味著它就是第 k 大的數(shù)字 。使用「三路劃分」，即每輪將數(shù)組劃分為三個(gè)部分：小于、等于和大于基準(zhǔn)數(shù)的所有元素。這樣當(dāng)發(fā)現(xiàn)第 k 大數(shù)字處在“等于基準(zhǔn)數(shù)”的子數(shù)組中時(shí)，便可以直接返回該元素。為了進(jìn)一步提升算法的穩(wěn)健性，可采用隨機(jī)選擇的方式來選定基準(zhǔn)數(shù)。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        List<Integer> numList = new ArrayList<>();
        for (int num : nums) numList.add(num);
        return quickSelect(numList, k);
    }

    private int quickSelect(List<Integer> nums, int k) {
        Random random = new Random();
        int pivot = nums.get(random.nextInt(nums.size()));
        List<Integer> big = new ArrayList<>();
        List<Integer> small = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        for (int num : nums) {
            if (num > pivot) big.add(num);
            else if (num < pivot) small.add(num);
            else equal.add(num);
        }
        //第 k大元素在 big中，遞歸劃分
        if (k <= big.size()) return quickSelect(big, k);
        //第 k大元素在 small中，遞歸劃分
        if (k > nums.size() - small.size()) return quickSelect(small, k - nums.size() + small.size());
        //第 k大元素在 equal中，直接返回
        return pivot;
    }
}

時(shí)間復(fù)雜度：對于長度為 n 的數(shù)組執(zhí)行哨兵劃分操作的時(shí)間復(fù)雜度為 O(n) 。其實(shí)就是遍歷了數(shù)組中的每個(gè)元素，將其分到三個(gè)數(shù)組中。

空間復(fù)雜度： 劃分函數(shù)的平均遞歸深度為 O(log n) 。