常见的排序算法有哪些？它们的特点是什么？

以下是一些常见的排序算法及其特点：

1. 冒泡排序 (Bubble Sort)
   • 基本原理：通过相邻元素比较和交换，每一轮将最大值“冒泡”到末尾。重复遍历直到无交换。
   • 时间复杂度：最好 O(n)（已有序时），最坏和平均 O(n²)。
   • 空间复杂度：O(1)，原地排序。
   • 稳定性：稳定（相等元素不交换顺序）。
   • 优化：可通过标志变量（flag）检测是否已有序来提前结束。
2. 选择排序 (Selection Sort)
   • 基本原理：每一轮遍历查找未排序序列的最小值，并放入已排序序列的末尾。
   • 时间复杂度：总是 O(n²)，无最好最坏区分。
   • 空间复杂度：O(1)，原地排序。
   • 稳定性：不稳定（可能改变相等元素的顺序）。
3. 插入排序 (Insertion Sort)
   • 基本原理：将未排序元素逐个插入到已排序序列的合适位置，初始时已排序序列只有一个元素。
   • 时间复杂度：最好 O(n)（已有序时），最坏和平均 O(n²)。
   • 空间复杂度：O(1)，原地排序。
   • 稳定性：稳定。
4. 快速排序 (Quick Sort)
   • 基本原理：采用分治策略，选取一个基准元素（如首个元素），将序列分为“小于基准”和“小于基准”的子序列，递归排序子序列。
   • 时间复杂度：平均 O(n log n)，最坏 O(n²)（当序列已全序时）。
   • 空间复杂度：O(log n)（递归栈空间）。
   • 稳定性：不稳定。
5. 归并排序 (Merge Sort)
   • 基本原理：分治法，将序列递归拆分成最小单元（单元素），再合并有序子序列。
   • 时间复杂度：平均、最好和最坏均为 O(n log n)。
   • 空间复杂度：O(n)（辅助数组）。
   • 稳定性：稳定。

总结特点：

• 简单排序（冒泡、选择、插入）：适用于小规模数据；时间复杂度通常 O(n²)。
• 高效排序（快速、归并、堆排序）：平均 O(n log n)。
• 稳定性：冒泡、插入、归并排序保持元素原序；选择和快速不保持。

参考代码示例（JavaScript）：

// 冒泡排序  
function bubbleSort(arr) {  
  let len = arr.length;  
  for (let i = 0; i < len - 1; i++) {  
    for (let j = 0; j < len - 1 - i; j++) {  
      if (arr[j] > arr[j + 1]) {  
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];  
      }  
    }  
  }  
  return arr;  
}