堆排序稳定吗？

什么是堆排序？

堆排序是一种基于二叉堆的排序算法，它的时间复杂度为 O(nlogn)。它的基本思路是将待排序的序列构建成一个二叉堆，然后依次从堆中取出最大（或最小）的元素，并将其放到序列的末尾。重复这个过程直到整个序列有序。

// 堆排序实现（JavaScript）
function heapSort(arr) {
  // 构建大根堆
  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
    heapify(arr, i, arr.length);
  }
  // 取出堆顶元素并放到序列末尾
  for (let i = arr.length - 1; i > 0; i--) {
    swap(arr, 0, i);
    heapify(arr, 0, i);
  }
  return arr;
}

// 维护大根堆
function heapify(arr, i, len) {
  let left = 2 * i + 1;
  let right = 2 * i + 2;
  let largest = i;
  if (left  arr[largest]) {
    largest = left;
  }
  if (right  arr[largest]) {
    largest = right;
  }
  if (largest !== i) {
    swap(arr, i, largest);
    heapify(arr, largest, len);
  }
}

// 交换元素
function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

什么是稳定排序？

稳定排序是指如果两个相等的元素在排序前后的相对位置不变，那么这个排序算法就是稳定的。例如，对于序列 [3, 2, 2, 1]，如果我们对它进行稳定排序，那么排序后的结果应该是 [1, 2, 2, 3]，其中两个相等的 2 的相对位置不变。

堆排序是否稳定？

堆排序不是稳定排序。原因在于，在堆排序中，我们将堆顶元素与序列末尾的元素交换，这会破坏相等元素的相对位置。

例如，对于序列 [3, 2, 2, 1]，如果我们将它进行堆排序，那么第一次构建大根堆后得到的堆是 [3, 2, 2, 1]。此时我们将堆顶的 3 与序列末尾的 1 交换，得到序列 [1, 2, 2, 3]。可以看到，原本相等的两个 2 的相对位置发生了改变。

堆排序的优缺点

堆排序的时间复杂度为 O(nlogn)，与快速排序和归并排序相同。但与这两种算法不同的是，堆排序是一种“就地排序”，即它不需要额外的内存空间来存储中间结果。

堆排序的缺点在于它不是稳定排序，这会导致在某些情况下无法满足排序的需求。此外，堆排序的常数因子比较大，因此在实际应用中可能并不是最优的选择。

结论

堆排序是一种高效的排序算法，但它不是稳定排序。在实际应用中，我们需要根据具体的需求来选择排序算法，以便满足排序的稳定性和效率要求。