常见排序算法的时间复杂度和空间复杂度分析

排序算法是计算机科学中的基础内容，了解不同排序算法的时间复杂度和空间复杂度对于选择合适的算法至关重要。下面我将详细分析几种常见排序算法的复杂度特性。

常见排序算法复杂度对比

各排序算法详解

1. 冒泡排序

原理：重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

时间复杂度：

• 平均情况：O(n²)
• 最好情况：O(n)（当数组已经有序时，只需一次遍历）
• 最坏情况：O(n²)（当数组逆序时）

空间复杂度：O(1)，仅使用常数级别的额外空间。

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    // 标志位，若一轮比较中没有发生交换，说明数组已有序
    let swapped = false;
    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]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return arr;
}

2. 选择排序

原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

时间复杂度：

• 平均情况：O(n²)
• 最好情况：O(n²)
• 最坏情况：O(n²)

空间复杂度：O(1)，仅使用常数级别的额外空间。

function selectionSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

3. 插入排序

原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

时间复杂度：

• 平均情况：O(n²)
• 最好情况：O(n)（当数组已经有序时）
• 最坏情况：O(n²)

空间复杂度：O(1)，仅使用常数级别的额外空间。

function insertionSort(arr) {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

4. 快速排序

原理：选择一个元素作为基准，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。

时间复杂度：

• 平均情况：O(n log n)
• 最好情况：O(n log n)
• 最坏情况：O(n²)（当数组已经有序或逆序时，且每次选择的基准都是最小或最大元素）

空间复杂度：O(log n)，主要是递归调用栈的空间。

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;
  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

5. 归并排序

原理：采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

时间复杂度：

• 平均情况：O(n log n)
• 最好情况：O(n log n)
• 最坏情况：O(n log n)

空间复杂度：O(n)，需要额外的空间来合并数组。

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

6. 堆排序

原理：利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

时间复杂度：

• 平均情况：O(n log n)
• 最好情况：O(n log n)
• 最坏情况：O(n log n)

空间复杂度：O(1)，仅使用常数级别的额外空间。

function heapSort(arr) {
  // 构建最大堆
  buildMaxHeap(arr);
  
  // 逐个从堆顶取出元素
  for (let i = arr.length - 1; i > 0; i--) {
    // 将当前堆顶元素（最大值）与末尾元素交换
    [arr[0], arr[i]] = [arr[i], arr[0]];
    // 调整剩余元素为最大堆
    heapify(arr, i, 0);
  }
  return arr;
}

function buildMaxHeap(arr) {
  const len = arr.length;
  // 从最后一个非叶子节点开始调整
  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
    heapify(arr, len, i);
  }
}

function heapify(arr, heapSize, index) {
  const left = 2 * index + 1;
  const right = 2 * index + 2;
  let largest = index;
  
  if (left < heapSize && arr[left] > arr[largest]) {
    largest = left;
  }
  
  if (right < heapSize && arr[right] > arr[largest]) {
    largest = right;
  }
  
  if (largest !== index) {
    [arr[index], arr[largest]] = [arr[largest], arr[index]];
    heapify(arr, heapSize, largest);
  }
}

7. 计数排序

原理：不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

时间复杂度：

• 平均情况：O(n+k)，其中k是整数的范围
• 最好情况：O(n+k)
• 最坏情况：O(n+k)

空间复杂度：O(k)，需要一个额外的计数数组。

function countingSort(arr, max) {
  const count = new Array(max + 1).fill(0);
  const output = new Array(arr.length);
  
  // 统计每个元素出现的次数
  for (let i = 0; i < arr.length; i++) {
    count[arr[i]]++;
  }
  
  // 计算每个元素在输出数组中的位置
  for (let i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }
  
  // 构建输出数组
  for (let i = arr.length - 1; i >= 0; i--) {
    output[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
  }
  
  return output;
}

8. 基数排序

原理：按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

时间复杂度：

• 平均情况：O(d*(n+k))，其中d是位数，k是基数
• 最好情况：O(d*(n+k))
• 最坏情况：O(d*(n+k))

空间复杂度：O(n+k)，需要额外的空间来存储中间结果。

function radixSort(arr) {
  if (!arr.length) return arr;
  
  const max = Math.max(...arr);
  let exp = 1;
  
  while (Math.floor(max / exp) > 0) {
    countingSortByDigit(arr, exp);
    exp *= 10;
  }
  
  return arr;
}

function countingSortByDigit(arr, exp) {
  const output = new Array(arr.length);
  const count = new Array(10).fill(0);
  
  // 统计每个数字出现的次数
  for (let i = 0; i < arr.length; i++) {
    const digit = Math.floor(arr[i] / exp) % 10;
    count[digit]++;
  }
  
  // 计算每个数字在输出数组中的位置
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }
  
  // 构建输出数组
  for (let i = arr.length - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }
  
  // 将结果复制回原数组
  for (let i = 0; i < arr.length; i++) {
    arr[i] = output[i];
  }
}

9. 桶排序

原理：将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

时间复杂度：

• 平均情况：O(n+k)
• 最好情况：O(n+k)
• 最坏情况：O(n²)（当所有元素都放在同一个桶中时）

空间复杂度：O(n+k)，需要额外的空间来存储桶。

function bucketSort(arr, bucketSize = 5) {
  if (arr.length === 0) return arr;
  
  // 确定最小值和最大值
  let min = arr[0];
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
  }
  
  // 计算桶的数量
  const bucketCount = Math.floor((max - min) / bucketSize) + 1;
  const buckets = new Array(bucketCount);
  for (let i = 0; i < bucketCount; i++) {
    buckets[i] = [];
  }
  
  // 将元素分配到桶中
  for (let i = 0; i < arr.length; i++) {
    const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
    buckets[bucketIndex].push(arr[i]);
  }
  
  // 对每个桶进行排序并合并结果
  const result = [];
  for (let i = 0; i < bucketCount; i++) {
    if (buckets[i].length > 0) {
      // 这里可以使用插入排序或其他排序算法
      insertionSort(buckets[i]);
      result.push(...buckets[i]);
    }
  }
  
  return result;
}

排序算法性能对比可视化

排序算法选择指南

1. 当数据规模较小时：可以使用简单的排序算法，如插入排序，因为它们的常数因子较小，在小规模数据上可能比高效排序算法更快。

2. 当数据规模较大时：应选择时间复杂度为O(n log n)的排序算法，如快速排序、归并排序或堆排序。

3. 当内存空间有限时：应选择空间复杂度较低的算法，如堆排序(O(1))，而不是归并排序(O(n))。

4. 当需要稳定排序时：应选择稳定的排序算法，如归并排序、插入排序、冒泡排序，而不是不稳定的快速排序或堆排序。

5. 当数据分布有特殊性质时：

   • 如果数据范围较小且是整数，可以使用计数排序。
   • 如果数据有明显的分布特征，可以使用桶排序。
   • 如果数据是字符串或多位数，可以使用基数排序。

6. 当数据基本有序时：插入排序表现很好，时间复杂度接近O(n)。

7. 当需要外部排序（数据不能全部装入内存）时：归并排序是一个很好的选择，因为它可以有效地处理外部数据。

总结

不同排序算法有各自的优势和适用场景。在实际应用中，我们需要根据数据规模、数据特性、内存限制和稳定性要求等因素来选择合适的排序算法。了解各种排序算法的时间复杂度和空间复杂度是做出正确选择的基础。

参考资料

• MDN - 排序算法
• GeeksforGeeks - Sorting Algorithms
• 维基百科 - 排序算法
• 算法导论（第3版）