以下是十大经典排序算法，按常见排序方式分为不同的类别，且各自有不同的特点和使用场景：

1. 冒泡排序 (Bubble Sort)

  • 原理：重复遍历待排序的序列，比较相邻元素，如果顺序错误就交换它们，直到没有交换为止。
  • 时间复杂度：最坏和平均情况是 O(n2)O(n^2)，最好情况是 O(n)O(n)（已排序的情况下）。

2. 选择排序 (Selection Sort)

  • 原理：每次从未排序部分中选择最小（或最大）元素，放到已排序部分的末尾。
  • 时间复杂度：最坏和平均情况是 O(n2)O(n^2)。

3. 插入排序 (Insertion Sort)

  • 原理：从未排序部分取出一个元素，插入到已排序部分的适当位置，直到所有元素都排好序。
  • 时间复杂度：最坏情况 O(n2)O(n^2)，最好情况 O(n)O(n)。

4. 归并排序 (Merge Sort)

  • 原理：采用分治法，将数组分成两半，递归地排序每一半，然后合并两个已排序的部分。
  • 时间复杂度：无论最坏、平均还是最好情况都是 O(nlog⁡n)O(n \log n)。

5. 快速排序 (Quick Sort)

  • 原理：采用分治法，选择一个基准元素，将比基准小的元素放到左边，比基准大的放到右边，然后递归地排序两个子数组。
  • 时间复杂度：最坏情况是 O(n2)O(n^2)，平均情况是 O(nlog⁡n)O(n \log n)。

6. 希尔排序 (Shell Sort)

  • 原理：对间隔递减的子序列进行插入排序。通过不断减小间隔值来提升排序效率。
  • 时间复杂度：最坏情况下是 O(n2)O(n^2)，但在某些情况下可以接近 O(nlog⁡n)O(n \log n)。

7. 堆排序 (Heap Sort)

  • 原理：利用堆这种数据结构，先构建最大堆或最小堆，然后将堆顶元素与末尾元素交换，再调整堆。
  • 时间复杂度：最坏、最好和平均情况是 O(nlog⁡n)O(n \log n)。

8. 计数排序 (Counting Sort)

  • 原理：通过统计每个元素出现的次数来确定每个元素的位置，然后直接在数组中填充元素。
  • 时间复杂度：O(n+k)O(n + k)，其中 kk 是元素的范围。

9. 桶排序 (Bucket Sort)

  • 原理：将数据分到有限数量的桶里，每个桶内使用排序算法进行排序，然后将所有桶中的数据合并。
  • 时间复杂度：最好情况下是 O(n+k)O(n + k)，但需要依赖桶内的排序算法。

10. 基数排序 (Radix Sort)

  • 原理：根据数字的每个位进行排序，从低位到高位（或从高位到低位）。
  • 时间复杂度：O(nk)O(nk)，其中 nn 是元素数量，kk 是数字的位数。

总结

这些排序算法各有优缺点，适合不同的使用场景。比如：

  • 冒泡排序 和 插入排序 很适合数据量小且已经部分排序的场景；
  • 归并排序 和 快速排序 是常用的高效排序算法；
  • 计数排序 和 基数排序 对于整数或范围较小的元素非常高效。

选择合适的排序算法时，考虑数据的大小、排序的稳定性和性能等因素。