【C++面试刷题】快排(quick_sort)和堆排(priority

【C++面试刷题】快排(quick_sort)和堆排(priority_queue)的细节问题

一、快排的快速选择算法两种思路（面试会考）O(N)

快排的三数取中思路：
重要的是将它三个数进行排序最左为最小，中间为次小，最右为最大的数。（错误原因：我刚开始没有将这三个数进行排序，只是找出其最中间的值，导致时间超时了，这是因为
1、避免最坏情况：如果数组已经部分排序或完全排序，直接选择第一个数或最后一个数作为枢轴值可能会导致分割极不平衡，即一个子数组包含大部分元素，而另一个子数组只包含少数元素。这种情况会使快速排序的性能退化到O(n^2)。通过三数取中法，我们可以选择一个更居中的数作为枢轴值，从而在一定程度上避免这种不平衡的分割。
2、提高分割效率：当选择的枢轴值比较居中时，数组被分割成两个大小相近的子数组，这使得后续的递归排序过程更加高效。因为每次递归调用都需要对两个子数组进行排序，如果子数组的大小相近，则递归的深度会更小，从而减少了排序所需的总时间。
3、减少比较次数：虽然三数取中法本身需要一些额外的比较操作来确定中间数，但这些比较操作的开销相对于整个排序过程来说是微不足道的。而且，通过选择一个更好的枢轴值，我们可以减少后续分割和递归过程中的比较次数，从而提高整体排序效率。）
在这里插入图片描述
快排的随机值思想：
仅仅是随机，是概率求期望，因为是对于随机序列，存在一种称为“Linear Time Median Finding”的算法，该算法能够在最坏情况下也达到O(n)的时间复杂度。

二、TopK问题–用堆求前K个大/小or第K大/小的元素O（N*logK）

1、开胃小菜

思考一下，既然前K个大/小的元素，那么其实就可以用优先级队列来解决这个问题，可是，我们要注意的是面试中大概率不会说你是否会用这个优先级队列（对于一个C++程序员这个应该是基操吧！？），而大概率是考一下topk问题的这个堆是怎么整出来的，其实也就是我们数据结构中的堆（二叉树）这个部分的向上调整和向下调整建堆的过程，我们先来看一下下面这道题的具体做法（堆和快排），再来讲解一下建堆的具体过程用以我们暂时的理解应对面试。
这是题目：
在这里插入图片描述
这是答案：

这是解析：
我们简单思考一下这里其实我们建立的是一个小根堆，因为有个greater<int>，所以是小根堆，这里为什么要建立小根堆是因为，当我们新插入的元素比堆顶元素大的时候，那么就交换与堆顶元素，再向下调整就ok了，那么也就是每次插入的时候替换掉最小的元素呗！
而如果是对于找前K小的元素的时候，那么就建立个大根堆即可，因为我堆顶的元素是最大的，那么当比堆顶的数小的数进来的时候就替换掉并向下调整呗！

这是快排部分：
在这里插入图片描述
这是快排部分解析：
假设我们建立的是升序，那么我们只需要判断第k大的元素是否在最右区间，也就是数量可以比较一下，不在的话就判断是否在等于区间，不在的话就判断是否在最左区间，这里的细节就是在最左区间的时候传进去的大小只有k-b-c这是因为剩下两个区间都已经判断过确实没有，到最左区间就是减去前两个区间的数量的个数。

2、正式说明堆排序的问题

要想弄清楚堆排序，那么就必须先了解建堆的过程，也就是向上调整算法和向下调整算法。

up就是孩子比父亲大就交换，迭代上去，再判断孩子比父亲大就交换。

typedef int HPDataType;
void Swap(HPDataType* p1, HPDataType* p2) 
{ 
	HPDataType temp = *p1; 
	*p1 = *p2; 	
	*p2 = temp; 
}
//向上调整（除了child，其余全是堆）
//时间复杂度：O(N*logN)
void AdjustUp(HPDataType* a, HPDataType child)
{
    //判断孩子和父母的关系
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            //迭代
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

down就是因为我们前面是把大根堆的堆顶结点和新进入的值比较小的节点交换了，所以需要向下调整一下，依旧保持此时除了最后一个最大的元素以外的第二大元素当大头，只需要与孩子节点一直比较就ok了，直到孩子节点到最后一个节点了。

//向下调整
//时间复杂度：O(N)
void AdjustDown(HPDataType* a, HPDataType n, HPDataType parent)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child + 1] > a[child])
        {
            ++child;
        }
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapSort(int* a, int n)
{
    //插入建堆
    //建堆 -- 向上调整
    //时间复杂度为O（N*logN）
    //升序 -- 建大堆
    int i = 1;
    for (i = 1; i < n; i++)
    {
        AdjustUp(a, i);
    }
    //从后往前调整
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        --end;
    }
}