c++十种排序算法的时间复杂度

### C++ 中十种常见排序算法的时间复杂度 #### 1. 冒泡排序 (Bubble Sort) 冒泡排序是一种简单的排序算法，通过重复遍历要排序的列表，依次比较相邻元素并交换顺序不对的元素。该过程会持续进行直到没有需要交换的元素为止。 - **时间复杂度**: 平均和最坏情况下均为 O(n²)[^3] ```cpp 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]) std::swap(arr[j], arr[j + 1]); } ``` #### 2. 选择排序 (Selection Sort) 选择排序的工作原理是从未排序部分找到最小(大)元素放到已排序序列的末尾。 - **时间复杂度**: 同样为 O(n²)，无论是在最佳还是最差情况下的性能都较差[^4] ```cpp void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { int minIndex = i; for (int j = i + 1; j < n; ++j) if (arr[j] < arr[minIndex]) minIndex = j; std::swap(arr[i], arr[minIndex]); } } ``` #### 3. 插入排序 (Insertion Sort) 插入排序构建有序数组的一个项接一个项的方式工作，在每一步中将下一个待处理的数据放入已经排好序的部分之中。 - **时间复杂度**: 最佳情况下可以达到 O(n)，但在平均和最糟糕的情况下仍需 O(n²) ```cpp 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; } } ``` #### 4. 归并排序 (Merge Sort) 归并排序采用分治法策略来解决问题，它不断地把当前数据集分成两半直至不能再分割下去，之后再逐步合并这些子集合形成最终的结果。 - **时间复杂度**: 总体上保持在 O(n log n)，即使对于最不利的情况也是如此[^2] ```cpp void merge(int arr[], int l, int m, int r); void mergeSort(int arr[], int l, int r); // Helper function to perform merging of two halves. void merge(int arr[], int l, int m, int r) { /* ... */ } // Recursive call that divides the array into subarrays and merges them back together. 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²)，但实际上往往能维持在 O(n log n) 的水平，并且具有较低常数因子 ```cpp int partition(int arr[], int low, int high); void quickSort(int arr[], int low, int high); // Function to find the partition position. int partition(int arr[], int low, int high) { /* ... */ } // Main recursive sorting routine using Lomuto or Hoare's scheme. void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); // Before pi quickSort(arr, pi + 1, high); // After pi } } ``` #### 6. 堆排序 (Heap Sort) 堆排序利用了最大/最小堆这一特殊形式的完全二叉树结构来进行高效地排列操作。 - **时间复杂度**: 类似于归并与快排，整体表现稳定在 O(n log n) 左右 ```cpp void heapify(int arr[], int N, int i); void buildMaxHeap(int arr[], int N); void heapSort(int arr[], int N); // To maintain max-heap property after removing root node. void heapify(int arr[], int N, int i) { /* ... */ } // Convert input data structure from unordered list/array form into a valid binary heap representation. void buildMaxHeap(int arr[], int N) { /* ... */ } // Actual implementation which sorts elements by repeatedly extracting maximum value out of remaining unsorted portion until all items are processed. void heapSort(int arr[], int N) { buildMaxHeap(arr, N); for (int i = N - 1; i > 0; --i) { std::swap(arr[0], arr[i]); // Move current largest element at end. heapify(arr, i, 0); // Rebuild reduced size heap excluding last item now placed correctly within sorted section. } } ``` #### 7. 计数排序 (Counting Sort) 计数排序适用于范围有限的小整数值输入场景，能够在线性时间内完成任务而不依赖任何额外的空间开销之外的因素影响。 - **时间复杂度**: 可以做到 O(k+n)，其中 k 表示值域宽度，n 是待排序对象数量[^1] ```cpp void countingSort(int arr[], int n, int range) { int output[n]; // Output array will be stored here temporarily during processing phase. int count[range + 1] = {0}; // Auxiliary storage used internally as frequency counter table indexed according keyspace boundaries. // Store counts of each unique integer found inside source collection. for (int i = 0; i < n; ++i) ++count[arr[i]]; // Transform cumulative frequencies so they represent starting indices instead when writing final result back over original dataset later on. for (int i = 1; i <= range; ++i) count[i] += count[i - 1]; // Build resulting ordered sequence based upon transformed index mappings derived previously above step. for (int i = n - 1; i >= 0; --i) { output[count[arr[i]] - 1] = arr[i]; --count[arr[i]]; } // Copy contents of temporary buffer holding newly arranged values back onto caller provided memory location pointed towards initially passed argument 'arr'. for (int i = 0; i < n; ++i) arr[i] = output[i]; } ``` #### 8. 桶排序 (Bucket Sort) 桶排序先按照一定规则分配给不同的“桶”，然后再分别对各个独立分区内的成员实施更精细级别的分类整理作业流程。 - **时间复杂度**: 如果各区间内分布均匀的话则可近似认为是 O(n+k)，反之可能会恶化至 O(n²) ```cpp void bucketSort(float arr[], int n) { vector<float> b[n]; // Distribute individual entries across multiple containers proportionally relative their magnitude compared against overall span covered entire set being operated upon presently. for (int i = 0; i < n; ++i) b[int(n * arr[i])].push_back(arr[i]); // Apply secondary ordering mechanism recursively down through nested levels till reaching leaf nodes containing singletons only then stop further subdivision attempts altogether eventually producing fully organized outcome once completed successfully throughout whole hierarchy tree traversal path taken sequentially one level deep per iteration cycle pass performed iteratively. for (int i = 0; i < n; ++i) sort(b[i].begin(), b[i].end()); // Concatenate results obtained earlier stages forming complete answer ready presentation purposes finally. int index = 0; for (int i = 0; i < n; ++i) for (size_t j = 0; j < b[i].size(); ++j) arr[index++] = b[i][j]; } ``` #### 9. 基数排序 (Radix Sort) 基数排序针对多关键字记录类型设计的一种非比较型整数排序方案，主要特点是按位逐轮次扫描处理每一位上的数字大小关系从而间接实现了全局层面的整体升序降序调整效果。 - **时间复杂度**: 对于固定长度编码表示方式而言基本恒定等于 O(d*(n+b))，这里 d 意味着最高有效位所在