void Swap(int* child, int* parent)
{
  int tmp = *child;
  *child = *parent;
  *parent = tmp;
}
void SelectSort1(int arr[], int n)
{
  int i;
  for ( i = 0; i < n - 1; i++)    //i同样是记录已排序数字的，i代表已排序序列的队尾
  {
    int min = i;  //min记录当前最小数字的下标
    int j;
    for (j = i + 1; j < n; j++)  //for循环后 将找出未排序数列中的最小值的下标（min）
    {
      if (arr[j] < arr[min])
      {
        min = j;
      }
    }
    if (min != i) //当本趟本来就有序的时候，不需要自己和自己进行交换。
    {
      Swap(&arr[i], &arr[min]);
    }
  }
}

void Swap(int* child, int* parent)
{
  int tmp = *child;
  *child = *parent;
  *parent = tmp;
}
void SelectSort(int* arr, int n)//时间复杂度O(n^2)  同时进行两个数的排序是一个数排序的小优化
{
  //这个是最简单的排序
  int begin = 0;
  int end = n - 1;
  while (begin < end)
  {
    int i;
    int mini = begin;
    int maxi = begin;
    for (i = begin; i <= end; i++)
    {
      if (arr[i] < arr[mini])
      {
        mini = i;
      }
      if (arr[i] > arr[maxi])
      {
        maxi = i;
      }
    }
    Swap(&arr[begin], &arr[mini]);
    //此时这个位置会有可能不能解决负数的问题，所以这个位置还要给一个条件
    //也就是当我的begin和maxi的位置重叠了，就要重新修正一下maxi的位置
    if (begin == maxi)
    {
      maxi = mini;
    }
    Swap(&arr[maxi], &arr[end]);
    begin++;
    end--;
  }
}

void Swap(int* child, int* parent)//人才的我，交换两个数写成这个样子
{
  //parent = child;//两个错误：1.没有使用中间变量，直接赋值，神仙下凡写法 2.地址交换，没有解引用交换，天神下凡写法
  int tmp = *child;
  *child = *parent;
  *parent = tmp;
}
void AdjustDown(int* arr, int n, int root)//注意：前提（左右子树都是小顶堆）
{
  //都是下标操作，不明白就是画图，然后把下标给搞明白就行了
  int parent = root;//获取我的根结点
  //获取我的左右子树中码值小的那个孩子
  int child = parent * 2 + 1;//不需要考虑是左孩子还是右孩子，默认是左孩子就行
  while (child < n)//此时的这个循环条件意思：找到叶子结点之后就停止向下比较
  {
    //1.选出左右孩子码值小的那一个
    //if (arr[child+1] < arr[child])//因为此时的child默认是左孩子了，所以此时的child+1就是默认为右孩子（因为左右孩子的下标位置永远只差1而已）
    if (child + 1 < n && arr[child + 1] < arr[child])
    {
      child++;//因为左孩子大，所以就可以让我的左孩子加1,让左孩子变成右孩子，就可以得到此时右孩子是我要的那个码值小的
      //但是此时可能是有的父亲结点只要左孩子没有右孩子，所以此时的if条件中就还要加一个条件，才不会导致越界的可能
    }
    //程序来到这个位置说明，右孩子大，左孩子小
    if (arr[child] < arr[parent])
    {
      //满足条件就是交换就行
      //arr[parent] = arr[child];//两个数交换，不敢直接写成下面这个样子，下面这个是直接赋值的写法，这样就只是把一个数据重新复制了一次的意思，并不是交换的作用
      Swap(&arr[child], &arr[parent]);
      //交换完为了实现一个迭代的思想，就是让父亲结点一直往下走
      parent = child;//这个位置不敢不懂，parent就是一个名字，child才是我要的，所以就是把我要的给名字，让这个我要的地方成为这个名字的原理而已
      child = parent * 2 + 1;//此时就是为了找到另一个小树的左孩子的结点
    }
  }
}
void HeapSort(int* arr, int n)
{
  //所以这边想要实现堆我就要有一个向下调整算法函数的实现
  //AdjustDwon();
  //此时有了这个向下调整的函数，但是我们还要解决这个向下调整函数的前提
  //防止此时的左右子树不是小堆，不能直接使用向下调整算法
  //解决方法：
  int i;
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(arr, n, i);
  }
  int end = n - 1;
  while (end > 0)
  {
    Swap(&arr[0], &arr[end]);
    AdjustDown(arr, n, i);
    end--;
  }
}

按照最上面的一系列的原理，此时我要实现堆，第一步就是要把这个数组建成一个大顶堆或者小顶堆（因为只有这样我才可以利用规律和原理进行排序）
1.建堆
此时说着容易，但是建堆这个过程是比较复杂的
所以这里就有一个建小顶堆的好办法：向下调整算法（前提：左右子树都是小顶堆）
建小顶堆的原理：选出左右孩子中小的那一个去跟父亲比较，如果比父亲小就交换，然后再继续往下比较，比较到叶子结点就可以终止了（可以使用递归，也可以使用循环进行）
所以这边想要实现堆我就要有一个向下调整算法函数的实现