经典排序算法总结

在计算机科学领域，排序算法是数据结构中至关重要的一部分，它涉及到如何有效地重新排列一组数据，使其按照特定顺序排列。以下是对几种经典排序算法的详细解释和C++实现： 1. **冒泡排序**： 冒泡排序是最基础的排序算法之一，通过不断交换相邻的逆序元素来逐步将大的元素“冒”到序列末尾。时间复杂度为O(n^2)。 ```cpp template<typename T> void BubbleSort(T* r, int n){ T temp; int i, j; for (i = 0; i < n - 1; i++){ for (j = 0; j < n - i - 1; j++){ if (r[j] > r[j + 1]){ temp = r[j]; r[j] = r[j + 1]; r[j + 1] = temp; } } } } ``` 2. **快速排序**： 快速排序由C.A.R. Hoare提出，使用分治策略，通过选取一个基准值，将数组分为两部分，一部分的元素都小于基准，另一部分的元素都大于基准，然后对这两部分递归进行快速排序。时间复杂度平均为O(n log n)，最坏情况为O(n^2)。 ```cpp template<typename T> void QuickSort(T a[], int low, int high){ if(low < high){ T elem = a[low]; int l = low, r = high; while(l < r){ while(l < r && a[r] >= elem) r--; if (l < r){a[l++] = a[r];} while(l< r && a[l] <= elem) l++; if (l < r){a[r--] = a[l];} } a[r] = elem; QuickSort(a,low,r-1); QuickSort(a,r+1,high); } } ``` 3. **插入排序**： 插入排序是简单直观的排序方法，将每个元素插入到已排序的部分，类似于打扑克牌时将新牌插入正确位置。时间复杂度为O(n^2)。 ```cpp template<typename T> void insert_sort(T a[], int n){ int i, j; T elem; for (i = 1; i < n ; ++i){ j = i - 1; elem = a[i]; while(j >= 0 && elem < a[j]){ a[j + 1] = a[j]; j--; } a[j + 1] = elem; } } ``` 4. **希尔排序**： 希尔排序是插入排序的一种优化版本，通过间隔地对元素进行插入排序，减小了局部不稳定性，提高了效率。时间复杂度通常优于O(n^2)，但具体依赖于间隔序列的选择。 ```cpp template<typename T> void shell_insert(T array[], int d, int len){ int i, j; T elem; for (i = d; i < len; i++){ j = i; elem = array[i]; while(j >= d && elem < array[j - d]){ array[j] = array[j - d]; j -= d; } array[j] = elem; } } ``` 5. **选择排序**： 选择排序每次找出未排序部分中的最小（或最大）元素，放到已排序部分的末尾。时间复杂度为O(n^2)。 6. **堆排序**： 堆排序利用了堆这种数据结构，将待排序的数组构建为一个大顶堆或小顶堆，然后依次将堆顶元素与末尾元素交换，最后调整成堆。时间复杂度为O(n log n)。 7. **归并排序**： 归并排序采用分治策略，将数组拆分成两个子数组，分别排序，再合并两个有序子数组。时间复杂度为O(n log n)，但需要额外的空间。 以上是七种经典的排序算法，它们各有优缺点，适用于不同的场景。例如，快速排序通常比其他算法更快，但在最坏情况下性能会下降；而归并排序则总是保持稳定的O(n log n)时间复杂度，但需要更多的空间。理解这些排序算法有助于在实际编程中选择最合适的排序方法。