算法學(xué)習(xí)：排序算法

一、算法分類(lèi)

我們可以將排序算法分為比較類(lèi)排序和非比較類(lèi)排序。

  • 比較類(lèi)排序：通過(guò)比較來(lái)決定元素間的相對(duì)次序，由于其時(shí)間復(fù)雜度不能突破 O(nlogn)，因此也稱(chēng)為非線性時(shí)間比較類(lèi)排序。
    注：比如如果是java的話，可以調(diào)用系統(tǒng)自帶的排序方法，傳入一個(gè)Comparator函數(shù)。

  • 非比較類(lèi)排序：不通過(guò)比較來(lái)決定元素間的相對(duì)次序，它可以突破基于比較排序的時(shí)間下界，以線性時(shí)間運(yùn)行，因此也稱(chēng)為線性時(shí)間非比較類(lèi)排序。
    注：一般只能用于整型相關(guān)的數(shù)據(jù)類(lèi)型，并且一般需要輔助使用額外的內(nèi)存空間。



二、初級(jí)排序-O(n^2)

1. 選擇排序（Selection Sort）

每次找最小值，然后放到待排序數(shù)組的起始位置。

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}
2. 插入排序（Insertion Sort）

從前到后逐步構(gòu)建有序序列；對(duì)于未排序數(shù)據(jù)，在已排序序列中從后
向前掃描，找到相應(yīng)位置并插入。

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int cur = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > cur) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = cur;
    }
}
3. 冒泡排序（Bubble Sort）

嵌套循環(huán)，每次查看相鄰的元素如果逆序，則交換。

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

三、高級(jí)排序-O(n*Logn)

1. 快速排序（Quick Sort）
  • 核心思想是分治：數(shù)組取標(biāo)桿pivot，將小元素放pivot左邊，大元素放右側(cè)，然后依次對(duì)右邊和右邊的子數(shù)組繼續(xù)快排；以達(dá)到整個(gè)序列有序。
  • 關(guān)于基數(shù)選擇有很多方式，而基數(shù)選擇直接關(guān)系到快排的效率。
  • 代碼實(shí)現(xiàn)：
public static void quickSort(int[] array, int begin, int end) {
    if (end <= begin) return;
    int pivot = partition(array, begin, end);
    quickSort(array, begin, pivot - 1);
    quickSort(array, pivot + 1, end);
}

// 選取最后一個(gè)數(shù)為標(biāo)桿，將比它小的數(shù)放到前面去，然后排列
static int partition(int[] a, int begin, int end) {
    int pivot = end, counter = begin;
    for (int i = begin; i < end; i++) {
        // pivot: 標(biāo)桿位置，counter: ?于pivot的元素的個(gè)數(shù)
        if (a[i] < a[pivot]) {
            int temp = a[i];
            a[i] = a[counter];
            a[counter] = temp;
            counter++;
        }
    }
    int temp = a[pivot];
    a[pivot] = a[counter];
    a[counter] = temp;
    return counter;
}
2.歸并排序（Merge Sort）
  • 核心思想是分治；
  • 排序過(guò)程：
    a. 把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列；
    b. 對(duì)這兩個(gè)子序列分別采用歸并排序；
    c. 將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。
  • 代碼實(shí)現(xiàn)：
public static void mergeSort(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = (left + right) >> 1;
    mergeSort(array, left, mid);
    mergeSort(array, mid + 1, right);
    merge(array, left, mid, right);
}

public static void merge(int[] array, int left, int mid, int right) {
    int[] arr = new int[right - left + 1];
    int i = 0, m = left, n = mid + 1;
    while (m <= mid && n <= right) {
        arr[i++] = array[m] < array[n] ? array[m++] : array[n++];
    }
    while (m <= mid) {
        arr[i++] = array[m++];
    }
    while (n <= right) {
        arr[i++] = array[n++];
    }
    System.arraycopy(arr, 0, array, left, right - left + 1);
}
3.堆排序（Heap Sort）

堆和堆排序比較復(fù)雜，會(huì)拎出來(lái)單獨(dú)寫(xiě)一篇學(xué)習(xí)筆記；在算法題中遇到要使用堆排序時(shí)，如果是java，可以直接使用PriorityQueue優(yōu)先隊(duì)列。

四、特殊排序

1. 計(jì)數(shù)排序（Counting Sort）

計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開(kāi)辟的數(shù)組空間中；然后依次把計(jì)數(shù)大于 1 的填充回原數(shù)組。

基本思想

  • 計(jì)數(shù)：
    遍歷待排序的數(shù)組，統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，并將統(tǒng)計(jì)結(jié)果存儲(chǔ)在一個(gè)計(jì)數(shù)數(shù)組中。計(jì)數(shù)數(shù)組的索引對(duì)應(yīng)著元素的值，而計(jì)數(shù)數(shù)組中的值表示該元素出現(xiàn)的次數(shù)。
    (這里可以統(tǒng)計(jì)最小值，用最小值+index來(lái)對(duì)應(yīng)元素的值)
  • 累積計(jì)數(shù)：
    對(duì)計(jì)數(shù)數(shù)組進(jìn)行累積計(jì)數(shù)，即將每個(gè)元素的計(jì)數(shù)值加上前一個(gè)元素的計(jì)數(shù)值，得到每個(gè)元素在排序后數(shù)組中的位置。這一步確保相同元素的相對(duì)順序不變。
  • 排序：
    創(chuàng)建一個(gè)與待排序數(shù)組大小相同的結(jié)果數(shù)組，然后遍歷待排序數(shù)組，根據(jù)元素的值在累積計(jì)數(shù)數(shù)組中找到其在結(jié)果數(shù)組中的位置，將元素放置在結(jié)果數(shù)組中的正確位置。

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

public static void countingSort(int[] arr) {
    // 找出最大值、最小值
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    // 創(chuàng)建計(jì)數(shù)數(shù)組
    int[] countArray = new int[max - min + 1];
    // 統(tǒng)計(jì)數(shù)字出現(xiàn)的次數(shù)
    for (int i = 0; i < arr.length; i++) {
        countArray[arr[i] - min]++;
    }
    // 創(chuàng)建累計(jì)計(jì)數(shù)數(shù)組（用于表示該數(shù)存放到數(shù)組中的位置）
    int[] posArray = new int[max - min + 1];
    for (int i = 0; i < max - min + 1; i++) {
        if (i == 0) {
            posArray[i] = countArray[i];
        } else {
            posArray[i] = posArray[i - 1] + countArray[i];
        }
    }
    // 填充arr,完成排序
    for (int i = 0; i < max - min + 1; i++) {
        if (countArray[i] == 0) {
            continue;
        }
        int target = min + i;
        int start = i == 0 ? 0 : posArray[i - 1];
        int end = posArray[i];
        Arrays.fill(arr, start, end, target);
    }
}
2. 桶排序（Bucket Sort）

桶排序是計(jì)數(shù)排序的升級(jí)版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。


image.png
3.基數(shù)排序（Radix Sort）

基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類(lèi)推，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序。


五、算法實(shí)戰(zhàn)

1122. 數(shù)組的相對(duì)排序

問(wèn)題描述

給你兩個(gè)數(shù)組，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每個(gè)元素都出現(xiàn)在 arr1 中。
對(duì) arr1 中的元素進(jìn)行排序，使 arr1 中項(xiàng)的相對(duì)順序和 arr2 中的相對(duì)順序相同。未在 arr2 中出現(xiàn)過(guò)的元素需要按照升序放在 arr1 的末尾。

示例
輸入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
輸出：[2,2,2,1,4,3,3,9,6,7,19]

輸入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
輸出：[22,28,8,6,17,44]
解題思路

思路1. 可以正常寫(xiě)一個(gè)簡(jiǎn)單的排序算法，然后將比較大小的地方換成一個(gè)compare方法；按照arr2寫(xiě)出compare方法即可。
思路2. 使用計(jì)數(shù)排序算法，按照題目中的排序規(guī)則即可。

代碼示例
class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int max = Arrays.stream(arr1).max().getAsInt();
        // 統(tǒng)計(jì)數(shù)量
        int[] countArr = new int[max + 1];
        for (int item : arr1) {
            countArr[item]++;
        }
        
        int[] rules = new int[max + 1];
        int pre = 0;
        // 先排arr2中的元素
        for (int item : arr2) {
            Arrays.fill(arr1, pre, pre + countArr[item], item);
            pre += countArr[item];
            rules[item] = 1;
        }
        // 再排arr2以外的元素
        for (int i = 0; i <= max; i++) {
            if (rules[i] == 1) {
                continue;
            }
            Arrays.fill(arr1, pre, pre + countArr[i], i);
            pre += countArr[i];
        }
        return arr1;
    }
}

242. 有效的字母異位詞

問(wèn)題描述

給定兩個(gè)字符串 s 和 t ，編寫(xiě)一個(gè)函數(shù)來(lái)判斷 t 是否是 s 的字母異位詞。
注意：若 s 和 t 中每個(gè)字符出現(xiàn)的次數(shù)都相同，則稱(chēng) s 和 t 互為字母異位詞。
提示:

  • 1 <= s.length, t.length <= 5 * 10^4
  • s 和 t 僅包含小寫(xiě)字母
示例
輸入: s = "anagram", t = "nagaram"
輸出: true

輸入: s = "rat", t = "car"
輸出: false
解題思路

類(lèi)似計(jì)數(shù)排序，這里可以用點(diǎn)小技巧，只用一個(gè)數(shù)組解決問(wèn)題：創(chuàng)建一個(gè)長(zhǎng)度為26的數(shù)組，遍歷第一個(gè)字符串的時(shí)候++，遍歷第二個(gè)字符串的時(shí)候--；遍歷完字符串之后，只需要檢查有沒(méi)有不為0的數(shù)即可。

代碼示例
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] arr = new int[26];
        for (char item : s.toCharArray()) {
            arr[item - 'a']++;
        }
        for (char item : t.toCharArray()) {
            arr[item - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (arr[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

56. 合并區(qū)間

問(wèn)題描述

以數(shù)組 intervals 表示若干個(gè)區(qū)間的集合，其中單個(gè)區(qū)間為 intervals[i] = [starti, endi] 。請(qǐng)你合并所有重疊的區(qū)間，并返回 一個(gè)不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間 。
提示：

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 10^4
示例
輸入：intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出：[[1,6],[8,10],[15,18]]
解釋?zhuān)簠^(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].

輸入：intervals = [[1,4],[4,5]]
輸出：[[1,5]]
解釋?zhuān)簠^(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間。
解題思路

先對(duì)區(qū)間數(shù)組進(jìn)行排序，按照區(qū)間的左邊界進(jìn)行排序；然后依次合并即可。

代碼示例
class Solution {
    public int[][] merge(int[][] intervals) {
        // 對(duì)區(qū)間的左邊進(jìn)行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });

        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int left = intervals[i][0], right = intervals[i][1];
            // 沒(méi)有重疊，直接添加
            if (res.size() == 0 || res.get(res.size() - 1)[1] < left) {
                res.add(new int[]{left, right});
            } else {
                // 有重疊部分，合并
                res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], right);
            }
        }

        return res.toArray(new int[res.size()][]);
    }
}

493. 翻轉(zhuǎn)對(duì)

問(wèn)題描述

給定一個(gè)數(shù)組 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我們就將 (i, j) 稱(chēng)作一個(gè)重要翻轉(zhuǎn)對(duì)。

你需要返回給定數(shù)組中的重要翻轉(zhuǎn)對(duì)的數(shù)量。

示例
輸入: [1,3,2,3,1]
輸出: 2

輸入: [2,4,3,5,1]
輸出: 3
解題思路

歸并排序，nums[l..r] 中的翻轉(zhuǎn)對(duì)數(shù)目，就等于兩個(gè)子數(shù)組的翻轉(zhuǎn)對(duì)數(shù)目之和，加上左半邊的數(shù)在右半邊的數(shù)組中達(dá)成條件的數(shù)量；每次合并結(jié)果的時(shí)候，還要合并這兩個(gè)個(gè)有序數(shù)組，方便計(jì)算左半邊的數(shù)在右半邊的數(shù)組中達(dá)成條件的數(shù)量。

代碼示例
class Solution {
    public static int reversePairs(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        return recursion(nums, 0, nums.length - 1);
    }

    public static int recursion(int[] nums, int left, int right) {
        if (left == right) {
            return 0;
        }

        int mid = (left + right) / 2;
        int leftCount = recursion(nums, left, mid);
        int rightCount = recursion(nums, mid + 1, right);
        // 左半邊的數(shù)在右半邊的數(shù)組中達(dá)成條件的數(shù)量(左右都是有序數(shù)組)
        int x = left, y = mid + 1, count = 0;
        while (x <= mid) {
            while (y <= right && (long) nums[x] > (long) 2 * nums[y]) {
                y++;
            }
            count += y - mid - 1;
            x++;
        }
        // 合并兩個(gè)有序兩個(gè)數(shù)組
        int[] temp = new int[right - left + 1];
        int index = 0, leftIndex = left, rightIndex = mid + 1;
        while (leftIndex <= mid || rightIndex <= right) {
            if (leftIndex > mid) {
                temp[index++] = nums[rightIndex++];
            } else if (rightIndex > right) {
                temp[index++] = nums[leftIndex++];
            } else {
                if (nums[leftIndex] < nums[rightIndex]) {
                    temp[index++] = nums[leftIndex++];
                } else {
                    temp[index++] = nums[rightIndex++];
                }
            }
        }
        System.arraycopy(temp, 0, nums, left, right - left + 1);

        return leftCount + rightCount + count;
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 目錄一、排序算法的基本邏輯 1.1 什么是排序 1.2 排序算法分類(lèi) 1.3 比較排序 1.4非比較排序 ...
    城中之城閱讀 441評(píng)論 0贊 0
  • 題記： 常見(jiàn)的排序算法有：冒泡排序法，快速排序法，選擇排序法，插入排序法，此處作為自己最近面試準(zhǔn)備進(jìn)行的學(xué)習(xí)筆記，...
    梅先森森森森森森閱讀 95評(píng)論 0贊 2
  • 題記： 常見(jiàn)的排序算法有：冒泡排序法，快速排序法，選擇排序法，插入排序法，此處作為自己最近面試準(zhǔn)備進(jìn)行的學(xué)習(xí)筆記，...
    泥豆芽?jī)篗T閱讀 2,501評(píng)論 0贊 27
  • 1. 常用數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成 。 ...
    孔雨露閱讀 774評(píng)論 0贊 1
  • 1. 冒泡排序 來(lái)源百度百科: 冒泡排序(Bubble Sort，臺(tái)灣譯為:泡沫排序或氣泡排序)是一種簡(jiǎn)單的排序算...
    ficca閱讀 332評(píng)論 0贊 1

友情鏈接更多精彩內(nèi)容