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

 //1.找到無序區(qū)中最小的元素和它的下標
 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.把最小的元素與無序區(qū)第一個元素交換
  //swap(arr[i], arr[k]);
  if (k != i)
  {
   int tmp = arr[i];
   arr[i] = arr[k];
   arr[k] = tmp;
  }
 }
}

//優(yōu)化，每趟排序同時找出最大值和最小值
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]交換，然后再調(diào)整arr[0...n-1]，使其滿足大堆，如此反復(fù)操作
 for (root = size-1; root >= 1; root--)
 {
  swap(arr[root], arr[0]);
  AdjustDown(arr, root, 0);
 }
}