引言：

感觉今天更冷了，码字更加的不易，所以引言就简单的写一下啦！今天我们就来了解一下什么是直接选择排序和堆排序。

1.直接选择排序

时间复杂度：O（N^2）

我们今天主要是学习堆排序但是此时我们知道堆排序其实就是一个直接选择排序，所以我们这边先来学一下直接选择排序，为我们待会学习堆排序提供一些理解，因为在实际生活中直接选择排序是没有什么太大的意义的（因为效率很低），所以我们重点就是学习堆排序就行

1.1 直接选择排序实现原理：在元素集合arr[i]-arr[n-1]中选择关键码值最大或最小的数据元素，若这个元素不是这个数组中的最后一个元素或者第一个元素，则将它与这组元素中的最后一个或者第一个元素交换

然后在剩余的arr[i] - arr[n-2] ，(arr[i+1]-arr[n-1])集合中，重复上述步骤，直到集合中剩余一个元素

动态图原理如下：

1.2 直接选择排序的特性总结：

1.2.1.直接选择排序思考非常好理解，但是效率不是很好，实际中很少使用

1.2.2.时间复杂度：O(N^2)

1.2.3.空间复杂度：O(1)

1.2.4.稳定性：不稳定

1.3 直接选择排序的代码实现：

1.3.1一次只进行一个数的排序

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]);
    }
  }
}

1.3.2 优化，一次同时进行两个数的排序

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--;
  }
}

注意点：

Swap(&arr[begin], &arr[mini]);

if (begin == maxi)

{

maxi = mini;

}

Swap(&arr[maxi], &arr[end]);

begin++;

end–;`

但是此时要注意的是，有一个特殊情况就是当我的begin和maxi的位置重叠了，就要重新修正一下maxi的位置，从上面的代码可以看到，在交换函数之前，如果begin和max正好重合了，那么久会出现在arr[begin]和arr[min]交换后，下一步要和arr[end]进行交换的arr[max]被改变了，被改变成了现在的arr[min]，而实际上要和arr[end]进行交换的数的下标变成了min。所以要对max进行调整，即max=min。

2.堆排序

时间复杂度：O（N*log2N）

2.1 堆排序的基础知识

堆排序（涉及到二叉树（二叉树可以用数组实现也可以用链表实现，所以我们用数组实现就涉及到层序实现））；

其实在实际当中是不存在二叉树这种结构的，在内存中只是把数据的存储想象成一个二叉树的形式进行存储，最后在内存中的存储形式还是一个数组类型的形式存储；

此时这个位置我们着重强调二叉树就是因为我的堆的逻辑结构就是一颗完全二叉树，堆的物理结构（因为二叉树是一个逻辑结构，真实是不存在的，物理结构还是一个数组），所以堆的物理结构也是一个数组；

并且此时这个堆的父子关系是有一定的关系的（可以通过下标来确定父子结点的关系），leftchild = parent * 2+1; rightchild = parent * 2+2;前面的公式是算孩子结点位置的，后面这个是通过孩子结点算父亲结点的位置的 parent = （child-1）/2;(这个位置只要画一个二叉树的图和一个数组的图就可以理解)；

待会实现堆排序的时候我们操作的依然是一个数组（通过下标），但是我们依然可以把这个数组想象成是一个二叉树的结构，这样我们就可以实现堆排序了；

用数组的原理：就是利用这个下标来计算他们的父子关系，从而间接的实现一颗树的结构（规律就是上面的那些公式）；

动态图原理展示：

2.2 堆的两个特性：

结构性：用数组表示的完全二叉树：

有序性：任一结点的关键是其子树所有结点的最大值或最小值

2.3 堆的特殊结构

最大堆（MaxHeap）,也称“大顶堆”：最大值

最小堆（MinHeap），也称“小顶堆”：最小值

大顶堆要求：树中所有的父亲都大于等于孩子（注意：是所有的父亲）

小顶堆要求：数中所有的父亲都小于等于孩子

此时有了上述的这些知识我们才有可能玩转堆排序，否则……

2.4 所以当我们知道了上述的这些基础知识之后，我们就可以开始尝试将堆排序用代码实现一下了

首先就是把一个数组想象成一个堆：（因为堆（完全二叉树）的物理结构就是一个数组） 3,5,2,7,8,6,1,9,4,0 想象成是一个堆此时就可以使用层序遍历的方法，弄成4层，第一层一个元素，第二层两个元素，第三层四个元素，以2的平方规律层序下去，所以得到：一个完全二叉树

第一层： 3

第二层： 5 2

第三层：7 8 6 1

第四层：9 4 0

2.5 代码如下:（注释详解每一步）

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.建堆
此时说着容易，但是建堆这个过程是比较复杂的
所以这里就有一个建小顶堆的好办法：向下调整算法（前提：左右子树都是小顶堆）
建小顶堆的原理：选出左右孩子中小的那一个去跟父亲比较，如果比父亲小就交换，然后再继续往下比较，比较到叶子结点就可以终止了（可以使用递归，也可以使用循环进行）
所以这边想要实现堆我就要有一个向下调整算法函数的实现