堆排序 (大顶堆)

堆排序 (大顶堆)

不稳定，建堆需要时间较长

#include <iostream>
using namespace std;

void Swap(int *x, int *y)
{
  int t;
  t = *x;
  *x = *y;
  *y = t;
}

void HeapAdjust(int *a, int i, int size)
{
  int lchild = 2 * i;
  int rchild = 2 * i + 1;
  int max = i;
  if (i <= size / 2)
  {
    if (lchild <= size && a[lchild] > a[max])
    {
      max = lchild;
    }
    if (rchild <= size && a[rchild] > a[max])
    {
      max = rchild;
    }
    if (max != i)
    {
      Swap(&a[i], &a[max]);
      HeapAdjust(a, max, size);
    }
  }
}

void BuildHeap(int *a, int size)
{
  int i;
  for (i = size / 2; i >= 1; i--)
  {
    HeapAdjust(a, i, size);
  }
}

void HeapSort(int *a, int size)
{
  BuildHeap(a, size);
  for (int i = size; i >= 1; i--)
  {
    Swap(&a[1], &a[i]);
    HeapAdjust(a, 1, i - 1);
  }
}

int main()
{
  int n, i;
  cin >> n;
  int *a = new int[n + 1];
  for (i = 1; i <= n; i++)
  {
    cin >> a[i];
  }

  HeapSort(a, n);

  for (i = 1; i <= n; i++)
  {
    cout << a[i] << " ";
  }
  cout << endl;
  return 0;
}

• 时间复杂度： O(n*log2(n))

测试

[blazehu@MacBook ~]$ g++ -o HeapSort HeapSort.cpp
[blazehu@MacBook ~]$ ./HeapSort
5
3
6
8
7
2
2 3 6 7 8
[blazehu@MacBook ~]$