LC周报-快速排序(20221107-20221113)

本周做题记录

LC-136、LC-147、LC-148、LC-912、LC-215，涉及知识点位运算、归并排序、快速排序。本文重点讲解快速排序相关知识，并介绍一部分归并排序相关内容。

本周总结 1-快速排序

知识点介绍主要参考《算法导论》。

快速排序的简单描述：快速排序共分“分解”—“解决”两个步骤，具体来说，分解指的是将数组\(A[p..r]\)划分为子数组\(A[p..q-1]\)和\(A[q+1..r]\)，使得\(A[q+1..r]\)中的所有元素均大于\(A[q]\)，\(A[p..q-1]\)中所有元素均小于\(A[q]\)。解决指的是通过递归调用快速排序，对于数组\(A[p..q-1]\)和\(A[q+1..r]\)进行排序。

实现伪代码如下所示：
1
2
3
4
5
Quicksort(A, p, r)
if(p<r)
q = partion(A, p, r)
Quicksort(A, p, q-1)
Quicksort(A, q+1, r)
算法的关键部分是如何实现partion功能。具体有以下几种实现方式：

2.1 hoare 方法

这个方法取自于快排的发明者本人。其单趟排序的思路是：取区间中最左或最右边的元素为\(key\)，定义两个变量，这里假设是\(p\)和\(q\)，\(q\)从区间的最右边向左走，找到比\(key\)小的元素就停下。\(p\)从最左边向右走，找到比\(key\)大的元素就停下。然后交换\(p\)和\(q\)所指向的元素。重复上面的过程，直到\(pq\)相遇，交换\(key\)和\(p\)、\(q\)相遇位置的元素

2.2 双指针方法

取最左边的数为\(key\)，定义两个快慢指针，都从\(key\)的下一位往右走，\(fast\)每走一步判断一下它指向的元素是否小于\(key\)，若小于则交换\(fast\)和\(slow\)位置的元素，并且让\(slow\)向前走，直到\(fast\)走到底，结束循环。最后让\(slow\)和\(key\)位置的值交换。再返回\(key\)的位置。

2.3 挖坑法

这个方法单趟排序的思路是：取最左或最右边的元素为\(key\)，假设把这个位置“挖空”，让最右边的\(q\)向左走，直到遇到比\(key\)小的数，将其放到\(key\)的位置，自己的位置变“空”。直到\(p\)、\(q\)相遇，那么这个位置就是最终的坑位，再将\(key\)填入这个坑位，就完成了一趟排序。

非递归实现快排

参考链接：https://blog.csdn.net/LiangXiay/article/details/121421920

该方法记住栈来实现，参考代码如下：

void QuickSortNonR(int* a, int left, int right)
{
	stack<int> st;//建立栈
	st.push(left);//将区间入栈
	st.push(right);
	while (!st.empty())//当栈不为空进入循环
	{
		right = st.top();//取区间最右值
		st.pop();//出栈
		left = st.top();//取区间最左值
		st.pop();//出栈
		int key = PartSort3(a, left, right);//对区间进行一趟排序，取得key值
		if (left < key - 1)//如果左区间可以再分，就入栈
		{
			st.push(left);
			st.push(key - 1);
		}
		if (key + 1 < right)//如果右区间可以再分，就入栈
		{
			st.push(key + 1);
			st.push(right);
		}
	}
}

快速排序的性能分析

快排的最坏情况是每次划分产生的两个子问题分别包含了\(n-1\)和 0 个元素。划分的时间复杂度为\(\Theta(n)\)，对一个大小为 0 的数组进行递归调用会直接返回，因此其时间复杂度\(T(0) = \Theta(1)\)。所以，算法运行时间的递归表达式为\(T(n) = T(n-1) + T(0) + \Theta(n) = T(n-1) + \Theta(n)\)。递归求解可得\(T(n) = \Theta(n^2)\)。

快排的最好情况是每次得到的两个子问题的规模都不大于\(\frac{n}{2}\)。这种情况下\(T(n) = 2T(\frac{n}{2})+\Theta(n)\)。递归求解可得，\(T(n) = \Theta(n\log n)\)。
快排的随机化版本

随机选取主元，通过这种方式，可以让快速排序算法更加趋于平均情况，使得出现极不平衡的情况概率下降。
两种优化快速排序的思想 6.1 三数取中

面对完全有序的数组，快速排序每趟排序后，\(key\)的位置都在边缘，每层递归都只能固定一个数，时间复杂度变成了\(O(N^2)\)。

面对这种情况，我们可以在取\(key\)时动手脚。每次取\(key\)我们不再只取最左或最右的值。而是对比最左、最右、中间的三个元素，取三个元素中，值在另外两者中间的元素作为\(key\)。这样，就打乱了有序数组，大大加快了快速排序在面对这种情况时的速度。 6.2 小区间优化

快速排序对一个元素不多的数组排序，仍需要进行多次递归调用，而递归是比较消耗资源的，所以为了避免在快速排序递归的最后几层大量调用函数，我们可以在数组元素较少时不再递归，而是采用选择排序替代，这样就能在不损失多少速度的情况下减少大量的递归次数，达到优化速度的目的。

LC-215 数组中的第 K 个最大元素

寻找书序中第\(k\)大的元素，借助快排思想，若选取的主元位置为第\(k\)位则直接返回。

int quickSelect(vector<int> &a, int l, int r, int index)
{
    int q = randomPartition(a, l, r);
    if (q == index)
        return a[q];
    else
        return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
}

int randomPartition(vector<int> &a, int l, int r)
{
    int q = rand() % (r - l + 1) + l;
    swap(a[q], a[r]);
    int x = a[r], i = l - 1;
    for (int j = l; j < r; ++j)
    {
        if (a[j] <= x)
            swap(a[++i], a[j]);
    }
    swap(a[i + 1], a[r]);
    return i + 1;
}

int findKthLargest(vector<int> &nums, int k)
{
    srand(time(0));
    return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
}

本周总结 2-归并排序

LC-148 链表的归并排序

该题目主要考察归并排序在链表上的应用。归并排序是一种分治思想，思路如下：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。该算法的实现有两种方法，一种是 top-down 的方法，将整个链表不停地进行二分操作。跳出条件为若链表中元素个数为 0，返回空指针。若只有一个元素，返回该元素。接着通过合并两个有序链表的方式进行归并。另一种思想是 bottom-up 的方法，子序列的大小为 2,4,8，...指数式递增，直到完成整个链表的归并操作。两种方法的具体实现如下所示：

//自顶向下方法实现归并排序
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode *sortlist1(ListNode *head, ListNode *tail)
    {
        if (head == nullptr)
            return nullptr;
        if (head->next == tail)
        {
            head->next = nullptr;
            return head;
        }
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast != tail)
        {
            slow = slow->next;
            fast = fast->next;
            if (fast != tail)
                fast = fast->next;
        }
        return merge(sortlist1(head, slow), sortlist1(slow, tail));
    }

    ListNode *merge(ListNode *l1, ListNode *l2)
    {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;
        if (l1->val <= l2->val)
        {
            l1->next = merge(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = merge(l1, l2->next);
            return l2;
        }
    }
    ListNode *sortList(ListNode *head)
    {
        return sortlist1(head, nullptr);
    }
};

//自底向上实现归并排序
class Solution
{
public:
    ListNode *sortList(ListNode *head)
    {
        if (head == nullptr)
        {
            return head;
        }
        int length = 0;
        ListNode *node = head;
        while (node != nullptr)
        {
            length++;
            node = node->next;
        }
        ListNode *dummyHead = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1)
        {
            ListNode *prev = dummyHead, *curr = dummyHead->next;
            while (curr != nullptr)
            {
                ListNode *head1 = curr;
                for (int i = 1; i < subLength && curr->next != nullptr; i++)
                {
                    curr = curr->next;
                }
                ListNode *head2 = curr->next;
                curr->next = nullptr;
                curr = head2;
                for (int i = 1; i < subLength && curr != nullptr && curr->next != nullptr; i++)
                {
                    curr = curr->next;
                }
                ListNode *next = nullptr;
                if (curr != nullptr)
                {
                    next = curr->next;
                    curr->next = nullptr;
                }
                ListNode *merged = merge(head1, head2);
                prev->next = merged;
                while (prev->next != nullptr)
                {
                    prev = prev->next;
                }
                curr = next;
            }
        }
        return dummyHead->next;
    }

    ListNode *merge(ListNode *head1, ListNode *head2)
    {
        ListNode *dummyHead = new ListNode(0);
        ListNode *temp = dummyHead, *temp1 = head1, *temp2 = head2;
        while (temp1 != nullptr && temp2 != nullptr)
        {
            if (temp1->val <= temp2->val)
            {
                temp->next = temp1;
                temp1 = temp1->next;
            }
            else
            {
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        if (temp1 != nullptr)
        {
            temp->next = temp1;
        }
        else if (temp2 != nullptr)
        {
            temp->next = temp2;
        }
        return dummyHead->next;
    }
};