- **正确答案**：常见的排序算法包括冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序等。它们的时间复杂度和空间复杂度各有不同，适用于不同的场景。 - **解答思路**：首先要明确每种排序算法的基本思想，然后分析其时间复杂度（最好、最坏、平均情况）和空间复杂度。接着可以比较它们的稳定性、是否是原地排序等特性。最后可以讨论它们在实际应用中的优缺点以及适用场景。 - **深度知识讲解**： ### 1. 冒泡排序（Bubble Sort） - **基本思想**：重复遍历数组，每次比较相邻元素，若顺序错误则交换。 - **时间复杂度**： - 最好 O(n)（已排序情况下） - 最坏 O(n^2) - 平均 O(n^2) - **空间复杂度**：O(1)（原地排序） - **稳定性**：稳定 - **实现原理**：通过两层循环完成，外层控制轮数，内层进行相邻元素比较与交换。示例代码： ``` void bubbleSort(int arr[], int n) { 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]); } } } } ``` --- ### 2. 插入排序（Insertion Sort） - **基本思想**：将未排序部分逐个插入到已排序部分的合适位置。 - **时间复杂度**： - 最好 O(n) - 最坏 O(n^2) - 平均 O(n^2) - **空间复杂度**：O(1) - **稳定性**：稳定 - **实现原理**：从第二个元素开始，依次将其与前面的元素比较并插入合适位置。示例代码： ``` void insertionSort(int arr[], int n) { 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]; j--; } arr[j + 1] = key; } } ``` --- ### 3. 选择排序（Selection Sort） - **基本思想**：每一轮选出最小（或最大）元素放到当前序列的起始位置。 - **时间复杂度**：O(n^2)（无论输入如何） - **空间复杂度**：O(1) - **稳定性**：不稳定 - **实现原理**：维护一个已排序区和未排序区，每轮从未排序区找到最小值放到已排序区末尾。示例代码： ``` void selectionSort(int arr[], int n) { 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]); } } ``` --- ### 4. 归并排序（Merge Sort） - **基本思想**：分治法。将数组分为两半分别排序后合并成一个有序数组。 - **时间复杂度**：O(n log n)（所有情况） - **空间复杂度**：O(n)（需要额外空间） - **稳定性**：稳定 - **实现原理**：递归将数组拆分成子数组，直到单个元素；再合并两个有序子数组。示例代码： ``` void merge(int arr[], int l, int m, int r) { int n1 = m - l + 1; int 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) { int m = l + (r-l)/2; mergeSort(arr, l, m); mergeSort(arr, m+1, r); merge(arr, l, m, r); } } ``` --- ### 5. 快速排序（Quick Sort） - **基本思想**：分治法。选取基准元素，将数组划分为小于基准和大于基准的两部分，递归处理。 - **时间复杂度**： - 平均 O(n log n) - 最坏 O(n^2)（如已排序数组） - **空间复杂度**：O(log n)（递归栈） - **稳定性**：不稳定 - **实现原理**：选一个pivot，分区操作使得左边都小于等于pivot，右边都大于等于pivot，递归对左右排序。示例代码： ``` int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i+1], arr[high]); return i + 1; } void quickSort(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); } } ``` --- ### 6. 堆排序（Heap Sort） - **基本思想**：利用堆结构进行排序。构建最大堆后，不断取出堆顶元素放到数组末尾，并调整堆。 - **时间复杂度**：O(n log n) - **空间复杂度**：O(1) - **稳定性**：不稳定 - **实现原理**：构造大根堆，堆顶元素为最大值，将其与末尾元素交换后重建堆。示例代码： ``` void heapify(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int 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(int arr[], int n) { 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); } } ``` --- ### 总结对比表： | 排序算法 | 时间复杂度（平均） | 时间复杂度（最坏） | 空间复杂度 | 是否稳定 | 是否原地 | |--------------|---------------------|----------------------|------------|----------|-----------| | 冒泡排序 | O(n²) | O(n²) | O(1) | 是 | 是 | | 插入排序 | O(n²) | O(n²) | O(1) | 是 | 是 | | 选择排序 | O(n²) | O(n²) | O(1) | 否 | 是 | | 归并排序 | O(n log n) | O(n log n) | O(n) | 是 | 否 | | 快速排序 | O(n log n) | O(n²) | O(log n) | 否 | 是 | | 堆排序 | O(n log n) | O(n log n) | O(1) | 否 | 是 | --- ### 扩展知识： - **应用场景**： - 小规模数据适合使用插入排序、冒泡排序； - 大数据量推荐使用归并、快排、堆排； - 快排在大多数库中被广泛使用（如Java的Arrays.sort()）； - 归并排序常用于链表排序； - 堆排序可用于优先队列、Top K问题等。 - **优化技巧**： - 快排可采用三路划分、随机化pivot、小数组切换插入排序等方式优化； - 归并排序可通过提前复制辅助数组来减少拷贝开销； - 插入排序可改为二分查找插入位置提升效率。掌握这些常见排序算法及其底层实现机制，不仅有助于应对面试，还能帮助理解更复杂的算法设计思想。

5.29美团一面凉经

全站热榜

创作者周榜