void SelectSort(int *arr, int size)
{
  if (arr == NULL)
    return;

  //1.找到无序区中最小的元素和它的下标
  int i, j;
  for (i = 0; i < size - 1; i++)
  {
    int k = i;
    for (j = i + 1; j < size; j++)
    {
      if (arr[j] < arr[k])
      {
        k = j;
      }

    }
    //2.把最小的元素与无序区第一个元素交换
    //swap(arr[i], arr[k]);
    if (k != i)
    {
      int tmp = arr[i];
      arr[i] = arr[k];
      arr[k] = tmp;
    }
  }
}

//优化，每趟排序同时找出最大值和最小值
void SelectSort1(int *arr, int size)
{
  if (arr == NULL)
    return;

  int left = 0;
  int right = size - 1;
  while (left < right)
  {
    for (int i = left; i < right; i++)
    {
      if (arr[i] < arr[left])
        swap(arr[i], arr[left]);
      if (arr[i] > arr[right])
        swap(arr[i], arr[right]);
    }
    left++;
    right--;
  }
}

void AdjustDown(int *arr, int size, int parent)
{
  int child = 2 * parent + 1;

  while (child < size)
  {
    if (child + 1 < size && arr[child] < arr[child + 1])
    {
      child++;
    }

    if (arr[parent] < arr[child])
    {
      swap(arr[parent], arr[child]);
      parent = child;
      child = 2 * parent + 1;
    }
    else
      break;
  }
}

void HeapSort(int *arr, int size)
{
  if (arr == NULL)
    return;

  //1.建立初始堆（此处为大堆）
  int root;
  for (root = (size / 2)-1; root >= 0; root--)
  {
    AdjustDown(arr, size, root);
  }

  //2.将arr[0]与arr[n-1]交换，然后再调整arr[0...n-1]，使其满足大堆，如此反复操作
  for (root = size-1; root >= 1; root--)
  {
    swap(arr[root], arr[0]);
    AdjustDown(arr, root, 0);
  }
}