嵌入式开发高频面试题——第四章 常见算法（上）

4.1 排序算法

4.1.1 各种排序算法的时间空间复杂度、稳定性 ⭐⭐⭐⭐⭐

排序算法平均时间复杂度最好情况时间复杂度最坏情况时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n)O(n^2)O(1)稳定希尔排序O(n log n)O(n log^2 n)O(n^2)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(n^2)O(log n)不稳定

• 稳定性：指的是如果两个元素相等，它们在排序前后的相对位置是否保持不变。
  
• 时间复杂度：算法执行所需的时间，通常表现为最坏、平均和最好情况。
  
• 空间复杂度：算法执行时所需的额外存储空间。
  

4.1.2 各种排序算法什么时候有最好情况、最坏情况（尤其是快排） ⭐⭐⭐⭐

• 冒泡排序：
  
  
  
  • 最好情况：数组已经有序，时间复杂度为 O(n)。
    
  • 最坏情况：数组逆序，时间复杂度为 O(n^2)。
    
  
  
• 选择排序：
  
  
  
  • 无论数组是否有序，最好和最坏情况的时间复杂度都是 O(n^2)。
    
  
  
• 插入排序：
  
  
  
  • 最好情况：数组已经有序，时间复杂度为 O(n)。
    
  • 最坏情况：数组逆序，时间复杂度为 O(n^2)。
    
  
  
• 希尔排序：
  
  
  
  • 最好情况：数组基本有序，时间复杂度靠近 O(n log n)。
    
  • 最坏情况：数组完全无序，时间复杂度为 O(n^2)。
    
  
  
• 归并排序：
  
  
  
  • 最好和最坏情况的时间复杂度都是 O(n log n)，因为归并排序是分治算法，分割和合并的过程都不会依赖于数据的次序。
    
  
  
• 快速排序：
  
  
  
  • 最好情况：每次分割点恰好是数组的中位数，时间复杂度为 O(n log n)。
    
  • 最坏情况：每次分割点总是选择最大或最小值，时间复杂度为 O(n^2)（通常在数组几乎有序或完全无序时发生）。改进方式是使用随机化或三数取中。
    
  
  

---

4.1.3 冒泡排序 ⭐⭐⭐⭐

1. void bubbleSort(int arr[], int n) {
2.     for (int i = 0; i < n - 1; i++) {
3.         bool swapped = false;
4.         for (int j = 0; j < n - i - 1; j++) {
5.             if (arr[j] > arr[j + 1]) {
6.                 std::swap(arr[j], arr[j + 1]);
7.                 swapped = true;
8.             }
9.         }
10.         if (!swapped)
11.             break;
12.     }
13. }

复制代码

4.1.4 选择排序 ⭐⭐⭐⭐

1. void selectionSort(int arr[], int n) {
2.     for (int i = 0; i < n - 1; i++) {
3.         int minIndex = i;
4.         for (int j = i + 1; j < n; j++) {
5.             if (arr[j] < arr[minIndex])
6.                 minIndex = j;
7.         }
8.         std::swap(arr[i], arr[minIndex]);
9.     }
10. }

复制代码

4.1.5 插入排序 ⭐⭐⭐⭐

1. void insertionSort(int arr[], int n) {
2.     for (int i = 1; i < n; i++) {
3.         int key = arr[i];
4.         int j = i - 1;
5.         while (j >= 0 && arr[j] > key) {
6.             arr[j + 1] = arr[j];
7.             j--;
8.         }
9.         arr[j + 1] = key;
10.     }
11. }

复制代码

4.1.6 希尔排序 ⭐⭐⭐⭐

1. void shellSort(int arr[], int n) {
2.     for (int gap = n / 2; gap > 0; gap /= 2) {
3.         for (int i = gap; i < n; i++) {
4.             int temp = arr[i];
5.             int j;
6.             for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
7.                 arr[j] = arr[j - gap];
8.             }
9.             arr[j] = temp;
10.         }
11.     }
12. }

复制代码

4.1.7 归并排序 ⭐⭐⭐⭐

1. void merge(int arr[], int left, int mid, int right) {
2.     int n1 = mid - left + 1;
3.     int n2 = right - mid;
4.     int L[n1], R[n2];
6.     for (int i = 0; i < n1; i++)
7.         L[i] = arr[left + i];
8.     for (int i = 0; i < n2; i++)
9.         R[i] = arr[mid + 1 + i];
11.     int i = 0, j = 0, k = left;
12.     while (i < n1 && j < n2) {
13.         if (L[i] <= R[j])
14.             arr[k++] = L[i++];
15.         else
16.             arr[k++] = R[j++];
17.     }
19.     while (i < n1)
20.         arr[k++] = L[i++];
21.     while (j < n2)
22.         arr[k++] = R[j++];
23. }
25. void mergeSort(int arr[], int left, int right) {
26.     if (left < right) {
27.         int mid = left + (right - left) / 2;
28.         mergeSort(arr, left, mid);
29.         mergeSort(arr, mid + 1, right);
30.         merge(arr, left, mid, right);
31.     }
32. }

复制代码

4.1.8 快速排序 ⭐⭐⭐⭐⭐

1. int partition(int arr[], int low, int high) {
2.     int pivot = arr[high];
3.     int i = (low - 1);
4.     for (int j = low; j <= high - 1; j++) {
5.         if (arr[j] < pivot) {
6.             i++;
7.             std::swap(arr[i], arr[j]);
8.         }
9.     }
10.     std::swap(arr[i + 1], arr[high]);
11.     return (i + 1);
12. }
14. void quickSort(int arr[], int low, int high) {
15.     if (low < high) {
16.         int pi = partition(arr, low, high);
17.         quickSort(arr, low, pi - 1);
18.         quickSort(arr, pi + 1, high);
19.     }
20. }

复制代码

4.1.9 快排的 partition 函数与归并的 Merge 函数 ⭐⭐⭐

• Partition 函数（用于快速排序）：
  
  
  
  • 用来确定一个枢轴（pivot），将数组划分为两部分，使得枢轴左边的元素小于枢轴，右边的元素大于枢轴。
    
  • 快排基于分治思想，使用递归将划分后的部分继续排序。
    
  
  
• Merge 函数（用于归并排序）：
  
  
  
  • 用来合并两个已经排序的数组，形成一个有序数组。
    
  • 归并排序的分治过程首先对数组分割，然后通过Merge函数逐步将有序的子数组合并成终极的有序数组。
    
  
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。