排序算法詳細介紹對比及備考建議

文章目錄

  • 排序算法對比
    • 基本概要
  • 算法逐一介紹
    • 1. 冒泡排序（Bubble Sort）
    • 2. 選擇排序（Selection Sort）
    • 3. 插入排序（Insertion Sort）🌟🌟
    • 4. 希爾排序（Shell Sort）
    • 5. 歸并排序（Merge Sort）🌟🌟
    • 6. 快速排序（Quick Sort）🌟🌟🌟🌟🌟🌟
    • 7. 堆排序（Heap Sort）🌟🌟
    • 8. 計數排序（Counting Sort）
    • 9. 桶排序（Bucket Sort）
    • 10. 基數排序（Radix Sort）
      • 總結
  • 關于備考
    • ? 必考 or 高頻排序算法
    • 🎯 企業面試中高頻考察點
    • 🧠 拓展建議
    • 🎯 排序算法面試核心知識清單
      • ? 高頻要求手寫的排序算法
    • 🔝 面試高頻 Leetcode 題目（附關鍵詞）
    • 🧩 排序面試思維框架（你可以這樣答）
      • 🌟 經典問題：快速排序的時間復雜度？
      • 🌟 高級問題：為什么說歸并適合鏈表？
      • 🌟 擴展：非比較類排序的適用場景？
    • 🧠 排序算法復習筆記（面試 & 考試專用）
      • 一、排序算法分類
      • 二、常考排序算法精講
        • 1. 快速排序（Quick Sort）
        • 2. 歸并排序（Merge Sort）
        • 3. 堆排序（Heap Sort）
        • 4. 插入排序（Insertion Sort）
        • 5. 計數排序（Counting Sort）
        • 6. 基數排序（Radix Sort）
      • 三、面試高頻題推薦
      • 四、應答框架 & 面試建議
      • 五、實戰建議

本文將介紹常見排序算法，包括算法思想、代碼實現（C++和Python）、時間復雜度對比及不同排序間的比較。

排序算法對比

基本概要

排序算法大體可分為兩種：

  • 比較排序，時間復雜度O(nlogn) ~ O(n^2)，主要有：冒泡排序，選擇排序，插入排序，歸并排序，堆排序，快速排序等。
  • 非比較排序，時間復雜度可以達到O(n)，主要有：計數排序，基數排序，桶排序等。
  • 關于排序算法的穩定性問題：排序算法穩定性的簡單形式化定義為：如果arr[i] = arr[j]，排序前arr[i]在arr[j]之前，排序后arr[i]還在arr[j]之前，則稱這種排序算法是穩定的。通俗地講就是保證排序前后兩個相等的數的相對順序不變。（可以通過自定義比較函數來去除穩定性問題）
    舉例：對于冒泡排序，原本是穩定的排序算法，如果將記錄交換的條件改成arr[i] >= arr[i + 1]，則兩個相等的記錄就會交換位置，從而變成不穩定的排序算法。
排序算法平均時間復雜度最好情況最壞情況空間復雜度穩定性適用場景是否原地
冒泡排序O(n2)O(n)O(n2)O(1)穩定小數據或基本有序是
選擇排序O(n2)O(n2)O(n2)O(1)不穩定小數據，交換次數少，通用是
插入排序O(n2)O(n)O(n2)O(1)穩定小數據或基本有序是
希爾排序O(n log n) ~ O(n2)O(n logn)O(n2)O(1)不穩定中等數據量，通用是
歸并排序O(n log n)O(n log n)O(n log n)O(n)穩定鏈表/大數據量，穩定排序否
快速排序O(n log n)O(n log n)O(n2)O(log n)不穩定通用排序，平均最快是
堆排序O(n log n)O(n log n)O(n log n)O(1)不穩定通用排序，避免最壞情況是
計數排序O(n +k)O(n +k)O(n +k)O(k)穩定整數，范圍小否
桶排序O(n +k)O(n +k)O(n2)O(n +k)穩定均勻分布數據，浮點數否
基數排序O(d(n +k))O(d(n +k))O(d(n +k))O(n +k)穩定多位數整數否

算法逐一介紹

1. 冒泡排序（Bubble Sort）

  • 思想：相鄰元素比較交換，將最大元素逐步“冒泡”到末尾。
  • 時間復雜度：
    • 平均/最壞：O(n2)
    • 最好（已有序）：O(n)
  • 空間復雜度：O(1)
  • 穩定性：穩定

C++代碼：

void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {bool swapped = false;for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {swap(arr[j], arr[j+1]);swapped = true;}}if (!swapped) break;}
}
//---------------------------
void bubbleSort(vector<int>& arr) {int n = arr.size();for(int i = 0; i < n - 1; ++i)for(int j = 0; j < n - i - 1; ++j)if(arr[j] > arr[j + 1])swap(arr[j], arr[j + 1]);
}

Python代碼：

def bubble_sort(arr):n = len(arr)for i in range(n-1):swapped = Falsefor j in range(n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]swapped = Trueif not swapped:breakreturn arr
----------------------------------------
def bubble_sort(arr):n = len(arr)for i in range(n - 1):for j in range(n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]

2. 選擇排序（Selection Sort）

  • 思想：每次選擇最小元素放到已排序序列末尾。
  • 時間復雜度：
    • 平均/最好/最壞：O(n2)
  • 空間復雜度：O(1)
  • 穩定性：不穩定

C++代碼：

void selectionSort(vector<int>& arr) {int n = arr.size();for(int i = 0; i < n - 1; ++i) {int min_idx = i;for(int j = i + 1; j < n; ++j)if(arr[j] < arr[min_idx])min_idx = j;swap(arr[i], arr[min_idx]);}
}

Python代碼：

def selection_sort(arr):n = len(arr)for i in range(n-1):min_idx = ifor j in range(i+1, n):if arr[j] < arr[min_idx]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i]return arr

3. 插入排序（Insertion Sort）🌟🌟

  • 思想：逐個將元素插入到已排序序列的正確位置。當前元素向左找合適位置插入。
  • 時間復雜度：
    • 平均/最壞：O(n2)
    • 最好（已有序）：O(n)
  • 空間復雜度：O(1)
  • 穩定性：穩定

C++代碼：

void insertionSort(vector<int>& arr) {//int n = arr.size();for(int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;while(j >= 0 && arr[j] > key)arr[j + 1] = arr[j--];arr[j + 1] = key;}
}

Python代碼：

def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and arr[j] > key:arr[j + 1] = arr[j]j -= 1arr[j + 1] = keyreturn arr

4. 希爾排序（Shell Sort）

  • 思想：分組插入排序，逐步縮小間隔。插入排序的優化，分組進行插入。
  • 時間復雜度：O(nlogn) ~ O(n2)（取決于間隔序列）
  • 空間復雜度：O(1)
  • 穩定性：不穩定

C++代碼：

void shellSort(int arr[], int n) {for (int gap = n/2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i], j;for (j = i; j >= gap && arr[j-gap] > temp; j -= gap)arr[j] = arr[j-gap];arr[j] = temp;}}
}
----------------------------------------------------
void shellSort(vector<int>& arr) {int n = arr.size();for(int gap = n/2; gap > 0; gap /= 2) {for(int i = gap; i < n; ++i) {int temp = arr[i], j = i;while(j >= gap && arr[j - gap] > temp) {arr[j] = arr[j - gap];j -= gap;}arr[j] = temp;}}
}

Python代碼：

def shell_sort(arr):n = len(arr)gap = n // 2while gap > 0:for i in range(gap, n):temp = arr[i]j = iwhile j >= gap and arr[j-gap] > temp:arr[j] = arr[j-gap]j -= gaparr[j] = tempgap //= 2return arr

5. 歸并排序（Merge Sort）🌟🌟

  • 思想：分治法，遞歸排序后合并。分而治之，分成小塊合并排序。
  • 時間復雜度：O(n log n)
  • 空間復雜度：O(n)
  • 穩定性：穩定
  • 圖示：
    在這里插入圖片描述
    圖源
    C++代碼：
void merge(int arr[], int l, int m, int r) {int n1 = m - l + 1, n2 = r - m;int L[n1], R[n2];for (int i = 0; i < n1; i++) L[i] = arr[l+i];for (int j = 0; j < n2; j++) R[j] = arr[m+1+j];int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) arr[k++] = L[i++];else arr[k++] = R[j++];}while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}void mergeSort(int arr[], int l, int r) {if (l >= r) return;int m = l + (r - l)/2;mergeSort(arr, l, m);mergeSort(arr, m+1, r);merge(arr, l, m, r);
}
-----------------------
void merge(vector<int>& arr, int l, int m, int r) {vector<int> left(arr.begin() + l, arr.begin() + m + 1);vector<int> right(arr.begin() + m + 1, arr.begin() + r + 1);int i = 0, j = 0, k = l;while(i < left.size() && j < right.size())arr[k++] = left[i] < right[j] ? left[i++] : right[j++];while(i < left.size()) arr[k++] = left[i++];while(j < right.size()) arr[k++] = right[j++];
}void mergeSort(vector<int>& arr, int l, int r) {if(l >= r) return;int m = l + (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m + 1, r);merge(arr, l, m, r);
}

Python代碼：

def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2L, R = arr[:mid], arr[mid:]merge_sort(L)merge_sort(R)i = j = k = 0while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i +=1else:arr[k] = R[j]j +=1k +=1while i < len(L):arr[k] = L[i]i +=1; k +=1while j < len(R):arr[k] = R[j]j +=1; k +=1return arr
-----------------------------------------------------
def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr)//2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)def merge(left, right):result = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result.extend(left[i:])result.extend(right[j:])return result

6. 快速排序（Quick Sort）🌟🌟🌟🌟🌟🌟

  • 思想：分治法，選基準分區，遞歸排序。選一個基準值，小的放左邊，大的放右邊。通過一趟排序將待排數據分割成獨立的兩部分，其中一部分的所有數據都比另一部分小，再遞歸地對這兩部分進行排序。采用“分治”的思想，對于一組數據，選擇一個基準元素（base），通常選擇第一個或最后一個元素，通過第一輪掃描，比base小的元素都在base左邊，比base大的元素都在base右邊，再有同樣的方法遞歸排序這兩部分，直到序列中所有數據均有序為止。
  • 時間復雜度：
    • 平均/最好：O(nlogn)
    • 最壞（已有序）：O(n2)
  • 空間復雜度：O(log n)（遞歸棧）
  • 穩定性：不穩定
  • 核心步驟

    • 選擇基準值（Pivot）
      從數組中選擇一個元素作為基準值（pivot），通常選擇最后一個元素、第一個元素或隨機元素。

    • 分區（Partition）
      將數組重新排列，使得所有小于基準值的元素放在基準值的左側，所有大于基準值的元素放在右側。
      分區結束后，基準值的位置即為最終排序后的正確位置。

    • 遞歸排序
      對基準值左側和右側的子數組遞歸地進行快速排序。

C++代碼：

int partition(vector<int>& arr, int low, int high) {int pivot = arr[high], i = low - 1;for(int j = low; j < high; ++j) {if(arr[j] <= pivot){i++;swap(arr[i], arr[j]);//swap(arr[++i], arr[j]);}}swap(arr[i + 1], arr[high]);return i + 1;
}void quickSort(vector<int>& arr, int low, int high) {if(low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}

Python代碼：

def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[-1]left = [x for x in arr[:-1] if x <= pivot]right = [x for x in arr[:-1] if x > pivot]return quick_sort(left) + [pivot] + quick_sort(right)

7. 堆排序（Heap Sort）🌟🌟

  • 思想：構建最大堆，交換堆頂元素并調整堆。利用堆（最大堆）結構，每次取出堆頂元素放到數組尾部。
  • 時間復雜度：O(n log n)
  • 空間復雜度：O(1)
  • 穩定性：不穩定

C++代碼：

void heapify(vector<int>& arr, int n, int i) {int largest = i, left = 2 * i + 1, right = 2 * i + 2;if(left < n && arr[left] > arr[largest]) largest = left;if(right < n && arr[right] > arr[largest]) largest = right;if(largest != i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(vector<int>& arr) {int n = arr.size();for(int i = n / 2 - 1; i >= 0; --i)heapify(arr, n, i);for(int i = n - 1; i > 0; --i) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}

Python代碼：

def heapify(arr, n, i):largest = il, r = 2 * i + 1, 2 * i + 2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n = len(arr)for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)for i in range(n - 1, 0, -1):arr[0], arr[i] = arr[i], arr[0]heapify(arr, i, 0)return arr

8. 計數排序（Counting Sort）

  • 思想：統計元素出現次數，按順序輸出。
  • 時間復雜度：O(n + k)（k為數據范圍）
  • 空間復雜度：O(k)
  • 穩定性：穩定

C++代碼：

void countingSort(int arr[], int n, int max_val) {int output[n], count[max_val+1] = {0};for (int i = 0; i < n; i++) count[arr[i]]++;for (int i = 1; i <= max_val; i++) count[i] += count[i-1];for (int i = n-1; i >=0; i--) output[--count[arr[i]]] = arr[i];for (int i = 0; i < n; i++) arr[i] = output[i];
}
-------------------------------------------
void countingSort(vector<int>& arr) {if(arr.empty()) return;int max_val = *max_element(arr.begin(), arr.end());vector<int> count(max_val + 1, 0);for(int num : arr) ++count[num];int index = 0;for(int i = 0; i <= max_val; ++i)while(count[i]--) arr[index++] = i;
}

Python代碼：

def counting_sort(arr):max_val = max(arr)count = [0] * (max_val + 1)for num in arr:count[num] +=1i = 0for num in range(max_val +1):while count[num] >0:arr[i] = numi +=1count[num] -=1return arr
--------------------------------------------------
def counting_sort(arr):if not arr:returnmax_val = max(arr)count = [0] * (max_val + 1)for num in arr:count[num] += 1idx = 0for i, c in enumerate(count):for _ in range(c):arr[idx] = iidx += 1

9. 桶排序（Bucket Sort）

  • 思想：分桶后分別排序，合并結果。把數據分布到若干桶中，桶內排序，再合并結果。
  • 時間復雜度：
    • 平均：O(n + k)
    • 最壞：O(n2)
  • 空間復雜度：O(n + k)
  • 穩定性：穩定（取決于桶內排序算法）

C++代碼：

void bucketSort(float arr[], int n) {vector<float> buckets[n];for (int i = 0; i < n; i++) {int bi = n * arr[i];buckets[bi].push_back(arr[i]);}for (int i = 0; i < n; i++)sort(buckets[i].begin(), buckets[i].end());int index = 0;for (int i = 0; i < n; i++)for (float num : buckets[i])arr[index++] = num;
}
-----------------------------------------------
void bucketSort(vector<float>& arr) {int n = arr.size();vector<vector<float>> buckets(n);for(float num : arr) {int index = num * n;buckets[index].push_back(num);}for(auto& bucket : buckets)sort(bucket.begin(), bucket.end());arr.clear();for(auto& bucket : buckets)arr.insert(arr.end(), bucket.begin(), bucket.end());
}

Python代碼：

def bucket_sort(arr):max_val, min_val = max(arr), min(arr)bucket_size = (max_val - min_val) / len(arr)buckets = [[] for _ in range(len(arr))]for num in arr:idx = int((num - min_val) // bucket_size)if idx == len(buckets):idx -=1buckets[idx].append(num)sorted_arr = []for bucket in buckets:sorted_arr.extend(sorted(bucket))return sorted_arr
-------------------------------------------------
def bucket_sort(arr):if len(arr) == 0:returnn = len(arr)buckets = [[] for _ in range(n)]for num in arr:index = int(num * n)buckets[index].append(num)for bucket in buckets:bucket.sort()idx = 0for bucket in buckets:for num in bucket:arr[idx] = numidx += 1

10. 基數排序（Radix Sort）

  • 思想：按位排序，從低位到高位。從低位到高位對數字排序，使用穩定排序如計數排序。
  • 時間復雜度：O(d(n + k))（d為位數）
  • 空間復雜度：O(n + k)
  • 穩定性：穩定

C++代碼：

void countingSortForRadix(int arr[], int n, int exp) {int output[n], count[10] = {0};for (int i = 0; i < n; i++) count[(arr[i]/exp)%10]++;for (int i = 1; i < 10; i++) count[i] += count[i-1];for (int i = n-1; i >=0; i--) {output[count[(arr[i]/exp)%10]-1] = arr[i];count[(arr[i]/exp)%10]--;}for (int i = 0; i < n; i++) arr[i] = output[i];
}void radixSort(int arr[], int n) {int max_val = *max_element(arr, arr+n);for (int exp = 1; max_val/exp >0; exp *=10)countingSortForRadix(arr, n, exp);
}
--------------------------------
void countingSortByDigit(vector<int>& arr, int exp) {int n = arr.size();vector<int> output(n), count(10, 0);for(int i = 0; i < n; ++i)count[(arr[i] / exp) % 10]++;for(int i = 1; i < 10; ++i)count[i] += count[i - 1];for(int i = n - 1; i >= 0; --i) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}arr = output;
}void radixSort(vector<int>& arr) {int max_val = *max_element(arr.begin(), arr.end());for(int exp = 1; max_val / exp > 0; exp *= 10)countingSortByDigit(arr, exp);
}

Python代碼：

def radix_sort(arr):max_val = max(arr)exp = 1while max_val // exp >0:counting_sort_by_digit(arr, exp)exp *=10return arrdef counting_sort_by_digit(arr, exp):n = len(arr)output = [0]*ncount = [0]*10for i in range(n):index = (arr[i] // exp) %10count[index] +=1for i in range(1,10):count[i] += count[i-1]for i in range(n-1, -1, -1):index = (arr[i] // exp) %10output[count[index]-1] = arr[i]count[index] -=1for i in range(n):arr[i] = output[i]
---------------------------------------------------
def counting_sort_by_digit(arr, exp):n = len(arr)output = [0] * ncount = [0] * 10for num in arr:index = (num // exp) % 10count[index] += 1for i in range(1, 10):count[i] += count[i - 1]for num in reversed(arr):index = (num // exp) % 10output[count[index] - 1] = numcount[index] -= 1for i in range(n):arr[i] = output[i]def radix_sort(arr):max_val = max(arr)exp = 1while max_val // exp > 0:counting_sort_by_digit(arr, exp)exp *= 10

總結

  • 冒泡、選擇、插入排序：適用于小規模數據。
  • 希爾排序：中等規模數據，優于插入排序。
  • 歸并、快速、堆排序：大規模數據，歸并穩定但需額外空間，快速排序平均最快，堆排序原地排序。
  • 計數、桶、基數排序：特定場景下高效（如整數范圍小、均勻分布、多位數）。

非常好的問題！在數據結構與算法考試、面試（尤其是大廠）中，雖然排序算法很多，但常考的排序算法主要集中在下面這幾種，因為它們代表了不同的思想和場景優化策略：

關于備考

? 必考 or 高頻排序算法

排序算法說明 / 考察點為什么常考
快速排序分治、原地、非穩定排序最常用的高效通用排序，面試常要求手寫
歸并排序分治、穩定排序、空間換時間經常考在鏈表中排序（Leetcode經典）
堆排序二叉堆結構、原地排序、優先隊列基礎常作為Top K 問題基礎
插入排序穩定、簡單，考察基本理解代碼簡單，適合考察寫基礎排序
計數排序線性時間排序代表理解適用范圍 + 穩定排序基礎
冒泡排序教學用、面試中考“你寫一個最基礎排序”了解基本交換機制
桶/基數排序高效但場景特定高級筆試題中出現，用于浮點/大數據位排序

🎯 企業面試中高頻考察點

  • 寫一個快速排序（原地/非遞歸）
  • 鏈表使用歸并排序排序 O(n log n)
  • 從數據流中找第K大（堆排序）
  • Top K 頻率元素（堆 + 計數）
  • 計數排序 vs 比較類排序差別（適用場景）
  • 給定整數數組用基數排序排序

🧠 拓展建議

方向建議練習題
📚 基礎寫法快速排序、歸并排序、堆排序手寫
🔍 排序思想比較類 vs 非比較類排序的適用場景
📈 排序優化小數組用插入排序，大數組快速+歸并
🧪 Leetcode#215, #912, #148, #347, #451 等

🎯 排序算法面試核心知識清單

? 高頻要求手寫的排序算法

算法重點考察方向穩定性原地
快速排序分治思想、原地實現、遞歸/非遞歸??
歸并排序分治思想、鏈表排序實現??
堆排序大頂堆構建、Top K 使用??
插入排序簡單直接、部分有序數組快??

🔝 面試高頻 Leetcode 題目（附關鍵詞）

題目編號名稱涉及排序類型難度
#912排序數組快速/歸并排序🟠 中等
#215數組第K大元素快排/堆排序🟠 中等
#347前K高頻元素堆 + 計數排序思想🟠 中等
#148鏈表排序歸并排序🔵 困難
#451按頻率排序計數 + 自定義排序🟠 中等

🧩 排序面試思維框架（你可以這樣答）

🌟 經典問題：快速排序的時間復雜度？

  • 平均：O(n log n)
  • 最壞：O(n2)（已排序數組）
  • 優化：三路快排、隨機pivot

🌟 高級問題：為什么說歸并適合鏈表？

  • 不依賴隨機訪問
  • 可以輕松實現O(1)空間的鏈表歸并
  • 穩定、時間復雜度始終 O(n log n)

🌟 擴展：非比較類排序的適用場景？

  • 計數排序：整數，范圍小
  • 基數排序：整數、位數小（如手機號、身份證）
  • 桶排序：小數、浮點數、分布均勻

🧠 排序算法復習筆記（面試 & 考試專用）

一、排序算法分類

分類算法穩定性是否原地時間復雜度（平均）時間復雜度（最壞）適用場景
比較類排序冒泡、插入、選擇、歸并、快速、堆插入/冒泡/歸并 ? 其余 ?歸并 ? 其余 ?O(n^2)/O(nlogn)O(n^2)/O(nlogn)通用排序
非比較類排序計數、桶、基數??O(n)/O(nk)O(n)/O(nk)整數/位數小/范圍有限的排序場景

二、常考排序算法精講

1. 快速排序（Quick Sort）
  • 思想：分治 + 原地交換
  • 特點：高效，最常用，平均 O(nlogn)，最壞 O(n^2)
  • 代碼：C++/Python
  • 常考形式：手寫實現；找第K大元素；排序 + 去重
2. 歸并排序（Merge Sort）
  • 思想：分治 + 合并
  • 特點：穩定，適合鏈表，空間復雜度 O(n)
  • 常考形式：鏈表排序；大數據排序
3. 堆排序（Heap Sort）
  • 思想：最大堆構建 + 彈出堆頂
  • 特點：原地，不穩定，優先隊列基礎
  • 常考形式：Top K 問題，最大/最小K個數
4. 插入排序（Insertion Sort）
  • 思想：構建有序序列，將新元素插入
  • 特點：適合小數組、基本有序場景
5. 計數排序（Counting Sort）
  • 思想：統計頻次 -> 回寫數組
  • 特點：非比較排序，穩定，O(n+k)，適合范圍小的整數
6. 基數排序（Radix Sort）
  • 思想：按位排序（低位到高位）
  • 特點：適合大整數排序；與計數結合使用

三、面試高頻題推薦

Leetcode 編號題目重點算法
912Sort an Array快排 / 歸并
215Kth Largest Element in Array快排 / 堆排序
347Top K Frequent Elements堆 + 計數排序思想
148Sort List歸并（鏈表版）
451Sort Characters by Frequency計數 + 自定義排序

四、應答框架 & 面試建議

1. 你知道哪些排序？哪種最好？

  • 分析場景再選：快排適合通用，歸并適合鏈表，計數適合整數范圍小

2. 快排最壞時間復雜度？怎么優化？

  • O(n^2)，優化方法：隨機化 pivot，三路快排

3. 為什么歸并適合鏈表？

  • 鏈表不能隨機訪問，歸并分治直接分中間節點，合并無需額外數組

4. 如何實現 Top K 問題？

  • 小頂堆維護前 K 個元素，堆排序或快速選擇法

五、實戰建議

  • 手寫練習：快排（原地）、歸并（鏈表）、堆構建
  • 使用庫時：記得 sort() 默認用 IntroSort（快排+堆+插入）
  • 注意穩定性、是否原地、空間復雜度等細節

📌 建議每日刷 1-2 道經典題，注重思維過程而非背代碼
📌 可搭配可視化工具（如 Visualgo.net）加深理解

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/75977.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/75977.shtml
英文地址，請注明出處：http://en.pswp.cn/web/75977.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Docker華為云創建私人鏡像倉庫

Docker華為云創建私人鏡像倉庫

Docker華為云創建私人鏡像倉庫 在華為云官網的 產品 中搜索 容器鏡像服務 &#xff1a; 或者在其他頁面的搜索欄中搜索 容器鏡像服務 &#xff1a; 進入到頁面后&#xff0c;點擊 創建組織 &#xff08;華為云的鏡像倉庫稱為組織&#xff09;&#xff1a; 設置組織名字后&…
閱讀更多...
微信小程序-自定義toast

微信小程序-自定義toast

微信小程序-自定義toast 微信小程序原生的toast最多能顯示兩行文字。方案1:方案2 微信小程序原生的toast最多能顯示兩行文字。 有時候并不能滿足業務需求。所以我們需要使用第三方或者自定義。 方案1: 第三方vant-toast 微信小程序下載引入第三方vant之后。 在需要使用的頁面…
閱讀更多...
安卓手游逆向

安卓手游逆向

一、環境安裝 1.1、安裝Java環境 1.2、安裝SDK環境 1.3、安裝NDK環境 二、APK 2.1、文件結構 2.2、打包流程 2.3、安裝流程 應用安裝涉及目錄： system/app ----->系統自帶的應用程序，獲得adb root權限才能刪除。 data/app ------->用戶程序安裝的目錄，安裝…
閱讀更多...
VSCode Continue 擴展踩坑記錄

VSCode Continue 擴展踩坑記錄

Trae 是一款很優秀的 AI 開發工具&#xff0c;但目前支持的平臺還較少&#xff0c;比如不支持 Win7&#xff0c;不支持 Linux&#xff0c;為了在這些平臺上進行開發&#xff0c;我需要尋找一個替代品。經過網上搜索&#xff0c;選擇了 VSCode Continue 擴展&#xff0c;但在使…
閱讀更多...
Elasticsearch：AI 助理 - 從通才到專才

Elasticsearch：AI 助理 - 從通才到專才

作者&#xff1a;來自 Elastic Thorben Jndling 在 AI 世界中&#xff0c;關于構建針對特定領域定制的大型語言模型&#xff08;large language models - LLM&#xff09;的話題備受關注 —— 不論是為了更好的安全性、上下文理解、專業能力&#xff0c;還是更高的準確率。這個…
閱讀更多...
【ARM】MDK燒錄提示Error：failed to execute‘ ‘

【ARM】MDK燒錄提示Error：failed to execute‘ ‘

1、 文檔目標 解決在燒錄程序的時候&#xff0c;因為選擇了錯誤的燒錄方式導致下載失敗的情況。 2、 問題場景 在燒錄程序的時候出現了提示&#xff1a;“Error&#xff1a;failed to execute ’ ”&#xff08;如圖2-1&#xff09;。檢測Target->Debug配置發現沒有問題&a…
閱讀更多...
系統分析師（六）-- 計算機網絡

系統分析師（六）-- 計算機網絡

概述 TCP/IP 協議族 DNS DHCP 網絡規劃與設計 邏輯網絡設計 物理網絡設計 題目 層次化網絡設計 網絡冗余設計 綜合布線系統 IP地址 網絡接入技術 其他網絡技術應用 物聯網
閱讀更多...
優化運營、降低成本、提高服務質量的智慧物流開源了

優化運營、降低成本、提高服務質量的智慧物流開源了

智慧物流視頻監控平臺是一款功能強大且簡單易用的實時算法視頻監控系統。它的愿景是最底層打通各大芯片廠商相互間的壁壘&#xff0c;省去繁瑣重復的適配流程&#xff0c;實現芯片、算法、應用的全流程組合&#xff0c;從而大大減少企業級應用約95%的開發成本可通過邊緣計算技術…
閱讀更多...
從One-Hot到TF-IDF：NLP詞向量演進解析與業務實戰指南（一）

從One-Hot到TF-IDF：NLP詞向量演進解析與業務實戰指南（一）

從One-Hot到TF-IDF&#xff1a;詞向量演進之路 開場白&#xff1a; 想象一下&#xff0c;你試圖用Excel表格分析《紅樓夢》的情感傾向——每個字詞都是孤立的單元格&#xff0c;計算機看到的只有冰冷的0和1&#xff0c;而“黛玉葬花”的凄美意境卻消失得無影無蹤。這就是NLP工…
閱讀更多...
2. kubernetes操作概覽

2. kubernetes操作概覽

以下是 Kubernetes 的核心操作概覽&#xff0c;涵蓋常用命令、資源管理和典型場景的操作流程&#xff1a; 1. 核心操作工具 (1) kubectl 命令行工具 Kubernetes 的所有操作均通過 kubectl 實現&#xff0c;常用命令如下&#xff1a; 操作類型命令示例作用說明查看資源狀態ku…
閱讀更多...
從Ampere到Hopper：GPU架構演進對AI模型訓練的顛覆性影響

從Ampere到Hopper：GPU架構演進對AI模型訓練的顛覆性影響

一、GPU架構演進的底層邏輯 AI大模型訓練效率的提升始終與GPU架構的迭代深度綁定。從Ampere到Hopper的演進路徑中&#xff0c;英偉達通過?張量核心升級?、?顯存架構優化?、?計算范式革新?三大技術路線&#xff0c;將LLM&#xff08;大語言模型&#xff09;訓練效率提升至…
閱讀更多...
p2p的發展

p2p的發展

PCDN&#xff08;P2P內容分發網絡&#xff09;行業目前處于快速發展階段&#xff0c;面臨機遇與挑戰并存的局面。 一、發展機遇 技術融合推動 邊緣計算與5G普及&#xff1a;5G的高帶寬、低延遲特性與邊緣計算技術結合&#xff0c;顯著提升PCDN性能&#xff0c;降低延遲&#x…
閱讀更多...
計算機視覺與深度學習 ｜ 視覺里程計（Visual Odometry, VO）學習思路總結

計算機視覺與深度學習 ｜ 視覺里程計（Visual Odometry, VO）學習思路總結

視覺里程計（Visual Odometry, VO）學習思路總結 視覺里程計（VO）是通過攝像頭捕獲的圖像序列估計相機運動軌跡的技術，廣泛應用于機器人、自動駕駛和增強現實等領域。以下是一個系統的學習路徑，涵蓋基礎理論、核心算法、工具及實踐建議：一、基礎理論與數學準備 核心數學工具…
閱讀更多...
Ubuntu 24.04 中文輸入法安裝

Ubuntu 24.04 中文輸入法安裝

搜狗輸入法&#xff0c;在Ubuntu 24.04上使用失敗&#xff0c;安裝教程如下 https://shurufa.sogou.com/linux/guide 出現問題的情況&#xff0c;是這個帖子里描述的&#xff1a; https://forum.ubuntu.org.cn/viewtopic.php?t493893 后面通過google拼音輸入法解決了&#x…
閱讀更多...
阿里云 MSE Nacos 發布全新“安全防護”模塊，簡化安全配置，提升數據保護

阿里云 MSE Nacos 發布全新“安全防護”模塊，簡化安全配置，提升數據保護

作者&#xff1a;張文浩 阿里云在其微服務引擎&#xff08;MSE&#xff09;注冊配置中心 Nacos 上正式推出全新“安全防護”功能模塊&#xff0c;旨在幫助企業用戶有效管理安全狀態和降低開啟安全相關功能的學習成本&#xff0c;提升微服務架構的安全性。首期推出的“安全防護…
閱讀更多...
C#核心（23）StringBuilder

C#核心（23）StringBuilder

前言 我們先前已經了解了String的一些基本規則和常見的用法，今天就來講一下和string有所區別的StringBulider。 在 C# 中，StringBuilder 類是一個非常有用的工具，特別是在需要頻繁修改字符串時。與 String 類型不同，StringBuilder 類提供了一種動態字符串，可以在不創建新…
閱讀更多...
活動圖與流程圖的區別與聯系：深入理解兩種建模工具

活動圖與流程圖的區別與聯系：深入理解兩種建模工具

目錄 前言1. 活動圖概述1.1 活動圖的定義1.2 活動圖的基本構成要素1.3 活動圖的應用場景 2. 流程圖概述2.1 流程圖的定義2.2 流程圖的基本構成要素2.3 流程圖的應用場景 3. 活動圖與流程圖的聯系4. 活動圖與流程圖的區別4.1 所屬體系不同4.2 表達能力差異4.3 使用目的與語境4.4…
閱讀更多...
idea運行springboot項目，運行時不能生成target

idea運行springboot項目，運行時不能生成target

1&#xff0c;問題 項目本來運行正常&#xff0c;突然重啟項目運行時&#xff0c;提醒主類找不到&#xff0c;發現target未生成 2&#xff0c;解決辦法 查看.idea里面的文件&#xff0c;正常是下面這樣的 如果有缺失&#xff0c;刪除.idea里面的文件&#xff0c;清除idea緩…
閱讀更多...
【unity游戲開發——Animator動畫】Animator動畫狀態機復用——重寫動畫控制器 Animator Override Controller

【unity游戲開發——Animator動畫】Animator動畫狀態機復用——重寫動畫控制器 Animator Override Controller

注意&#xff1a;考慮到UGUI的內容比較多&#xff0c;我將UGUI的內容分開&#xff0c;并全部整合放在【unity游戲開發——Animator動畫】專欄里&#xff0c;感興趣的小伙伴可以前往逐一查看學習。 文章目錄 一、狀態機復用是什么&#xff1f;二、實戰專欄推薦完結 一、狀態機復…
閱讀更多...
山東大學軟件學院創新項目實訓（11）之springboot+vue項目接入deepseekAPI

山東大學軟件學院創新項目實訓（11）之springboot+vue項目接入deepseekAPI

因為該階段是前后端搭建階段&#xff0c;所以沒有進大模型的專項訓練&#xff0c;所以先用老師給的deepseek接口進行代替 且因為前端設計部分非本人負責且還沒有提交到github上&#xff0c;所以目前只能先編寫一個簡易的界面進行功能的測試 首先進行創建model類 然后創建Cha…
閱讀更多...
最新文章

Copyright @ 2022~2023