堆排序：

关于堆排序的讲解 大家可以看一下我的这篇文章：【数据结构】堆的建立 (时间复杂度计算-堆排序)---超细致_luck++的博客-CSDN博客

快速排序：

实际上快速排序和 冒泡排序被分在同一类：都是比较后进行交换的操作

快速排序这里我知道的有三个版本：

hoare版本：

这个版本是原始发明快速排序的人 想出来的

我们之前写排序也是先把 单趟排序 写出来 在来解决多趟排序

咋们这里的单趟排序的要求：

首先要选出一个 keyi 的 标准值

我们排序后的数组是：

左边都是小于keyi的值的数

右边都是大于keyi的值的数

大家发现这个动图的特点了嘛？

首先我们的keyi的选择 一般都是选择 最左边 或者是 最右边 的数

🥇 我们的右边的 猩猩惺惺先走 找比keyi小的数 找到停下

🥈 左边的熊猫后走 找比keyi大的数 找到停下 与猩猩的位置的数据交换

🥉 直到熊猫与猩猩相遇 再将相遇点与keyi的数据交换

这样就达到我们的目的了 大家思考一下有没有什么问题

一定会相遇？

首先他们之间相遇肯定是必然的 因为我们每次移动都是移动一边的动物 永远都只有一个动物在动所以是一定会有个动物动并又可能相遇的

为什么与keyi交换就达到目标？

① 因为 我们每次停下的都是找小的猩猩 所以相遇的时候的位置也是一个小于keyi的位置 当然这是右边的 熊猫 来与 猩猩 相遇 注意：我们的猩猩是停下来的 猩猩没停下来而相遇是下面的这些情况

② 还有一种可能就是我们的猩猩一直没找到一直往前面走 直到相遇 此时我们的熊猫是没有动的 所以相遇交换也只是原地交换

③ 还有一种可能就是我们得左右已经交换过了现在轮到右边得猩猩走 但是一直没有找到最终与左边还没有走得熊猫相遇 此时与keyi交换依旧是满足条件的 因为交换过后 我们还没来得及走的熊猫的位置已经因为交换变成一个小于keyi的值了 所以不需要担心相遇的时候交换会是一个比keyi大的数

还有一点就是我们的猩猩从右边往左走 找的是小 这样隐含的意思就是不找大呗 那么我们的猩猩就会略过大的数 让那些大的数依旧留在那边  左边找大也是同样的道理 让小的数留在左边(注意：这个也许可以帮助你理解 排升序 还是 降序)

上述就是为什么我们这样操作会达到我们的目标了

那现在大家想想为什么要我们的右边的猩猩先走呢 不能左边先走呢？

为了解决我们上面的问题  现在我们假设我们依然要排序 一个左小有大的数组(keyi依旧选择左边得数) 假设我们右边的熊猫先走 要排一个左小右大的数组 那我们有右边先走就是找大 把小的数留在左边 那就只右边后走找小咯 根据上面的道理类推 可以得出最终相遇得点是一个比keyi大得位置  最后与keyi交换 那么咋们这个数组不就成了 大-小-大 了嘛

总结： 如果keyi在左 那么一定是右先走  keyi在右 一定是左先走 至于找大找小 就涉及到是排升序还是降序 后面会说到哦

    int keyi = left;
  while (left < right)//升序
  {
    while (a[right] > a[keyi])
    {
      right--;
    }
    while (a[left] < a[keyi])
    {
      left++;
    }
    swap(a + right, a + left);
  }
  swap(a + keyi, a + right);

这个是我们初步写成的代码 还是让大家找找问题吧(大家可以对照着下面这两组数据查找)

首先我们不加 = 号的话是会死循环的 大家看：

我们的右边先走 我们找小 6小于6嘛 不小唉 那我右边不能走了 左边呢是不是也是一样 我们左边的其实位置是在keyi的位置 这样咋们不就死循环了嘛

不加限制条件就会越界(注意：这里我们已经加上)：

如果不加限制条件 我们右边先走 6>1 5>1 4>1 都是大于keyi的值的 我们已经加了 = 符号了最后 1=1 right 又 减减 一次那我们的right不就越界了嘛？

大家应该知道问题该怎么解决了吧 来看我们正确的代码：

    int keyi = left;
  while (left < right)//升序
  {
    while (left < right && a[right] >= a[keyi])
    {
      right--;
    }
    while (left < right && a[left] <= a[keyi])
    {
      left++;
    }
    swap(a + right, a + left);
  }
  swap(a + keyi, a + right);

现在问题来了 我们单趟已经排完序了 接下来的多趟怎么排呢？

写之前大家想一想 我们单趟排序给我们带来的是什么 给我们队数组的排序提供了什么帮助？

其实结果很简单  我们不是在最后 猩猩 与 熊猫 相遇后 keyi的值与相遇点的值进行了交换嘛那我们此时相遇点的位置放的keyi的值

我们keyi的值是不是放到那里就可以不变了呢？因为它左边是比他小的 右边是比他大的数  假设我们本身排完序之后 keyi 的值要大于 5 个数 那我这里把小于它的数排到它的左边不正好就满足keyi的位置在这 5 个位置的前面了嘛 只不过左边和右边还不一定就有序了 这样我们此时keyi的值的位置就是 正确✔ 的不用再移动它了

我们提到了单趟排完之后 左边和右边是不一定有序  但是如果我们把左边和右边变得有序那我们整体是不是就有序了 大家想想是不是这个道理？ 可是怎么解决左右的问题呢？ 

我们此时就要用到 二叉树中提到的一个 分治 的思想 可以这么理解：

就是这种一边的工作完成完 最后一起提交给上一级 上一级也是同样的操作

所以对于这种分治的思想 我们一般是采用递归来实现

 我们是在我们目前第一次单趟排序后keyi的值 左边 和 右边再进行一次同样的排序 紧接着继续递归到下一层

大家看这样能理解嘛  每选出一个 keyi 那么这个keyi位置的数就会排到应该在的位置上 而他两边的数也会接近有序 也可能已经有序

我们要递归到下一层 就必须选出该层的keyi 最终结果：

当然大家要注意 我们选择区间的时候要注意 有的区间只有一个数 有的区间不存在

int PartSort1(int* a, int left, int right)//key在左那先走得一方必在右 选大选小 取决于排升序 or 
{                                         //排降序
  int keyi = left;
  while (left < right)//升序
  {
    while (left < right && a[right] >= a[keyi])
    {
      right--;
    }
    while (left < right && a[left] <= a[keyi])
    {
      left++;
    }
    swap(a + right, a + left);
  }
  swap(a + keyi, a + right);
  return right;
}
void QuickSort(int* a, int left, int right)
{
  if (left >= right) return; = 意思只有一个值 > 意思区间不存在
  int keyi = PartSort1(a, left, right);
    //分区间
  QuickSort(a, left, keyi - 1);
  QuickSort(a, keyi + 1, right);
}

 这个是我们部分的栈帧展开图 希望可以帮助大家理解