各种排序算法的实现及性能比较

### 各种排序算法的实现及性能比较 #### 排序算法概述 排序算法是计算机科学中的基础且重要的部分，广泛应用于数据处理、数据库管理、搜索引擎等领域。根据数据的存储方式，排序算法主要分为内排序和外排序两大类。本文重点讨论内排序中的几种常见算法及其性能比较。 #### 插入排序 **简单插入排序** 简单插入排序是最直观的一种排序方法，其工作原理类似于人们日常生活中手动排序卡片或纸牌的方式。具体步骤为：从数组的第二个元素开始遍历，将当前元素与前面已排序好的部分进行比较，如果小于前面的某个元素，则向前移动该元素，直到找到合适的位置将其插入。这种排序方式简单易懂但效率较低，平均时间复杂度为O(n^2)。 ```cpp template<typename Comparable> void InsertSort(vector<Comparable>& vec, int begin, int end) { for (int i = begin + 1; i <= end; i++) { if (vec[i] < vec[i - 1]) { vec[0] = vec[i]; // 使用哨兵 int k; for (k = i - 1; vec[0] < vec[k]; k--) { vec[k + 1] = vec[k]; } vec[k + 1] = vec[0]; } } } template<typename Comparable> void InsertSort(vector<Comparable>& vec) { InsertSort(vec, 0, vec.size() - 1); } ``` **希尔排序** 希尔排序（Shell Sort）是由 Donald Shell 在 1959 年提出的一种基于插入排序的改进算法。它通过引入增量序列来分组数据，使得数据能在较大的范围内进行部分排序，从而减少后续排序所需的操作次数。希尔排序的关键在于增量序列的选择，通常采用“希尔增量”（如 n/2, n/4, ... , 1），其中 n 是待排序序列的长度。 ```cpp template<typename Comparable> void ShellSort(vector<Comparable>& vec) { int n = vec.size(); for (int inc = n / 2; inc >= 1; inc /= 2) { for (int i = inc; i < n; i++) { if (vec[i] < vec[i - inc]) { vec[0] = vec[i]; int k; for (k = i - inc; k >= 0 && vec[0] < vec[k]; k -= inc) { vec[k + inc] = vec[k]; } vec[k + inc] = vec[0]; } } } } ``` #### 交换排序 **冒泡排序** 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 ```cpp template<typename Comparable> void BubbleSort(vector<Comparable>& vec) { int pos = vec.size() - 1; while (pos > 0) { int bound = pos; pos = 0; for (int i = 0; i < bound; i++) { if (vec[i] > vec[i + 1]) { swap(vec[i], vec[i + 1]); pos = i; } } } } ``` #### 选择排序 **简单选择排序** 简单选择排序的基本思想是：每次从未排序的序列中找到最小（或最大）的元素，存放到已排序序列的末尾。这个过程重复进行直到所有元素排序完毕。 ```cpp template<typename Comparable> void SelectionSort(vector<Comparable>& vec) { for (int i = 0; i < vec.size(); i++) { int minIndex = i; for (int j = i + 1; j < vec.size(); j++) { if (vec[j] < vec[minIndex]) { minIndex = j; } } if (minIndex != i) { swap(vec[i], vec[minIndex]); } } } ``` #### 归并排序 **二路归并排序** 归并排序是一种采用分治法的排序算法。其核心思想是将待排序的数据分成两个子集，分别对这两个子集进行排序，然后再将排好序的子集合并成最终的排序结果。 ```cpp template<typename Comparable> void Merge(vector<Comparable>& vec, vector<Comparable>& tempVec, int left, int mid, int right) { int i = left, j = mid + 1, k = left; while (i <= mid && j <= right) { if (vec[i] < vec[j]) { tempVec[k++] = vec[i++]; } else { tempVec[k++] = vec[j++]; } } while (i <= mid) { tempVec[k++] = vec[i++]; } while (j <= right) { tempVec[k++] = vec[j++]; } for (int i = left; i <= right; i++) { vec[i] = tempVec[i]; } } template<typename Comparable> void MergeSort(vector<Comparable>& vec, vector<Comparable>& tempVec, int left, int right) { if (left < right) { int mid = (left + right) / 2; MergeSort(vec, tempVec, left, mid); MergeSort(vec, tempVec, mid + 1, right); Merge(vec, tempVec, left, mid, right); } } template<typename Comparable> void MergeSort(vector<Comparable>& vec) { vector<Comparable> tempVec(vec.size()); MergeSort(vec, tempVec, 0, vec.size() - 1); } ``` #### 堆排序 堆排序是一种基于完全二叉树结构的比较排序算法。首先构建一个大顶堆（或小顶堆），然后不断移除堆顶元素，并调整剩余的元素继续构成堆，直到所有元素都被移除。 ```cpp template<typename Comparable> void Heapify(vector<Comparable>& vec, int i, int heapSize) { int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < heapSize && vec[left] > vec[largest]) { largest = left; } if (right < heapSize && vec[right] > vec[largest]) { largest = right; } if (largest != i) { swap(vec[i], vec[largest]); Heapify(vec, largest, heapSize); } } template<typename Comparable> void HeapSort(vector<Comparable>& vec) { int size = vec.size(); // 构建初始大顶堆 for (int i = (size - 2) / 2; i >= 0; i--) { Heapify(vec, i, size); } // 排序过程 for (int i = size - 1; i >= 0; i--) { swap(vec[0], vec[i]); Heapify(vec, 0, i); } } ``` #### STL排序算法 C++标准库提供了一系列高效的排序函数，如 `std::sort` 和 `std::stable_sort` 等。这些函数通常使用更复杂的算法组合，例如 TimSort 或者 Introsort，它们能够在大多数情况下提供 O(n log n) 的平均时间复杂度。 ```cpp #include <algorithm> template<typename Comparable> void STLSort(vector<Comparable>& vec) { std::sort(vec.begin(), vec.end()); } template<typename Comparable> void STLSortStable(vector<Comparable>& vec) { std::stable_sort(vec.begin(), vec.end()); } ``` ### 性能比较 - **插入排序**：适用于小规模数据或者部分有序的数据集，时间复杂度为 O(n^2)，空间复杂度为 O(1)。 - **希尔排序**：是插入排序的一种改进版，通过增量序列减少了比较和移动的次数，时间复杂度取决于增量序列的选择，通常介于 O(n) 和 O(n^2) 之间。 - **冒泡排序**：简单但效率低，时间复杂度为 O(n^2)，空间复杂度为 O(1)。 - **快速排序**：高效的排序算法之一，基于分治法，平均时间复杂度为 O(n log n)，但在最坏的情况下退化为 O(n^2)。 - **简单选择排序**：简单但效率不高，时间复杂度为 O(n^2)，空间复杂度为 O(1)。 - **堆排序**：基于堆结构，时间复杂度稳定为 O(n log n)，空间复杂度为 O(1)。 - **二路归并排序**：稳定排序，时间复杂度稳定为 O(n log n)，但需要额外的空间 O(n)。 - **STL排序算法**：结合多种排序策略，通常能提供较好的性能，平均时间复杂度为 O(n log n)，空间复杂度取决于具体的实现。 ### 结论 不同排序算法的选择取决于具体的应用场景和需求。对于小规模数据集或部分有序的数据，可以选择插入排序或希尔排序；对于大规模数据集或追求高效性能的应用，推荐使用快速排序、堆排序或归并排序。在实际应用中，可以根据具体情况灵活选择最适合的排序算法。