void SelectSort(ShellDataType* a, int n)
{
  //左下标 和右下标
  int left = 0;
  int right = n - 1;
  //不需要left <= right，最后一个元素不需要再交换,当然给<=也没问题
  while (left < right)
  {
    //假设最小最大全部在left
    int mini = left, maxi = left;
    //单趟查找最小值和最大值下标
    for (int i = left; i < right; i++)
    {
      //找到最小的，更新下标
      if (a[i] < a[mini])
      {
        mini = i;
      }
      //找到最大的，更新下标
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
    }
    //maxi和right交换，mini和left交换
    Swap(&a[left], &a[mini]);
    //这里存在特殊情况，如果maxi在left位置，left和mini交换了之后，最大值的下标就是mini了
    //所以这里需要判断一下，如果真的是这种情况，就更新最大值下标。
    if (maxi == left)
    {
      maxi = mini;
    }
    Swap(&a[right], &a[maxi]);
    //后面的不需要再更新了，因为后面就算mini是在right位置，这轮也已经结束了，所以不需要再管它
    //更新left和right 的下标
    left++;
    right--;
  }
}

void HeapSort(int* a, int n)
{
  assert(a);
  //1.先建堆，向上调整建堆,建堆的时间复杂度为O(N*logN)
  //也可以采用向下调整的方法建堆，向下调整的方法建堆的时间复杂度为O(N)
  //强烈建议采用向下调整的建堆方式
  //for (int i = 0; i < n; ++i)
  //{
  //  AdjustUp(a, i);
  //}
  //向下调整建堆，是从第一个非叶子节点开始调整，因为所有的叶子节点都不需要进行向下调整
  //child = (parent-1)/2
  //此时parent就是n-1
  for (int i = (n - 1 - 1) / 2; i >=0; -- i)
  {
    AdjustDown(a, n, i);
  }
  //现在是大根堆
  //2.堆排序，采用向下调整算法进行排序,让最后一个节点和堆顶节点进行交换，然后堆顶节点向下调整
  //调整完后继续倒数第二个节点和堆顶节点交换,以此类推
  for (int i = n-1; i >0; --i)
  {
    swap(&a[0], &a[i]);
    //这里传参不能传n，传n-1,因为交换之后最后一个数字就不需要参与进来了，相当于size--
    //堆排序使用交换之后再向下调整原理：
    //在建了大根堆之后，堆顶的左右子树都是大根堆，不管最后一个元素是否是最小的，与堆顶元素交换后
    //堆顶元素就被放到了堆尾，然后再让堆顶元素向下调整，因为此时堆顶元素是一个较小的元素，会向下调整，调整之后是第二大的元素在堆顶
    // 
    //下一次再排序时，排的是堆尾的前一个了，那个最大的元素不用再排了，排的就是第二大的元素，
    //再让堆的最后一个元素与堆顶元素交换，再进行向下调整，调整完后第三大的元素就上来了。
    AdjustDown(a, i, 0);
  }
  //总结：排升序的话，建大根堆
  //排降序建小根堆
  for (int i = 0; i < n; i++)
  {
    printf("%d ", a[i]);
  }
}