递归的归并排序

归并排序主要流程是拆分 -- 排序 -- 合并 -- 排序 -- 合并

//拆分
void mergeSort(vector<int>& nums,int start, int end)
{
	if(start>=end) return ;
	int mid = start+(end-start)/2;
	mergeSort(nums,start,mid);
	mergeSort(nums,mid+1,end);
	//最后一层排序
	merge(nums,start,mid,end);
}
//排序
void merge(vector<int>& nums,int start, int mid, int end)
{
	vector<int> temp(end-start+1);
	int p1 = start;
	int p2 = mid+!;
	int p = 0;
	while(p1<=mid && p2<=end)
	{
		if(nums[p1] < nums[p2])
		{
			temp[p++] = nums[p1++];
		}
		else
		{
			temp[p++] = nums[p2++];
		}
	}
	while(p1<=mid)
	{
		temp[p++] = nums[p1++]; 
	}
	while(p2<=end)
	{
		temp[p++] = nums[p2++];
	}
	for(int i = 0;i<temp.size();i++)
	{
		nums[i] = temp[i];
	}
}
//实际调用
void sort(vector<int>& nums)
{
	mergeSort(nums,0,nums.size()-1);
}

对于链表的递归归并排序

最主要的就是如何找到中间节点，可以利用快慢指针来寻找中间节点，然后在mergeSort函数中记录中间节点的下一个节点，然后断开mid->next = nullptr;

class Solution {
public:
    //寻找中点
    ListNode* FindMid(ListNode* head)
    {
        if(head == nullptr) return nullptr;
        //快慢指针
        ListNode* fast = head->next;
        ListNode* slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    //合并
    ListNode* merge(ListNode* left,ListNode* right)
    {
        ListNode* dummy = new ListNode(-1,left);
        ListNode* cur = dummy;
        while(left && right)
        {
            if(left->val < right->val)
            {
                cur->next = left;
                left = left->next;
            }
            else
            {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        while(left)
        {
            cur->next = left;
            left = left->next;
            cur = cur->next;
        }
        while(right)
        {
            cur->next = right;
            right = right->next;
            cur = cur->next;
        }
        return dummy->next;
    }
    //归并排序
    ListNode* mergeSort(ListNode* head)
    {
        //当为空或者只有一个节点时直接返回
        if(head == nullptr || head->next == nullptr)
        {
            return head;
        }
        //寻找中间节点
        ListNode* mid = FindMid(head);
        ListNode* next = mid->next;
        //断开分段
        mid->next = nullptr;
        //划分
        ListNode* left = mergeSort(head);
        ListNode* right = mergeSort(next);

        //合并
        return merge(left,right);
    }
public:
    ListNode* sortList(ListNode* head) {
        return mergeSort(head);
    }
};

快速排序

冒泡排序基础上使用了递归分治法，快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移到数列一边，比他小的移动到另一边，进行拆解。

int partition(vector<int>& nums,int start, int end)
{
	//假设以最后一个值为基准
	int resval = nums[end];
	int res = start-1;
	for(int i = start;i<end;i++)
	{
		if(nums[i] <= resval)
		{
			swap(nums[i],nums[++res]);
		}
	}
	//将基准点交换到分割点的右侧
	swap(nums[res+1],nums[end]);
	return res+1;
}


void quickSort(vector<int>& nums,int start, int end)
{
	if(start >= end)
	{
		return ;
	}
	//获取基准的准确位置
	int mid = partition(nums,start,end);
	quickSort(nums,start,mid-1);
	quickSort(nums,mid+1,end);
}

快速排序链表

/**
 * 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* FindMid(ListNode* head)
    {
        //if(head == nullptr || head->next == nullptr) return head;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next)
        {
            fast= fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    ListNode* quickSort(ListNode* head)
    {
        if(head == nullptr || head->next == nullptr) return head;
        //3组指针：小于 等于 大于 基准值的边界节点
        ListNode* leftmin = new ListNode(-1);
        ListNode* rightmin = leftmin;
        ListNode* lefteq = new ListNode(-1);
        ListNode* righteq = lefteq;
        ListNode* leftmax = new ListNode(-1);
        ListNode* rightmax = leftmax;

        ListNode* cur = head;
        //选择中间节点为基准
        int pivot = FindMid(head)->val;

        while(cur)
        {
            //记录当前分段头节点的下一个节点
            ListNode* next = cur->next;

            //当当前分段的第一个值小于当前分段的基准，截断
            //更新小于的区间
            if(cur->val < pivot)
            {
                cur->next = nullptr;
                rightmin->next = cur;
                rightmin = rightmin->next;
            }
            else if(cur->val > pivot)
            {
                cur->next = nullptr;
                rightmax->next = cur;
                rightmax = rightmax->next;
            }
            else
            {
                cur->next = nullptr;
                righteq->next = cur;
                righteq = righteq->next;
            }
            //对下一个节点开始判断
            cur = next;
        }
        //对小于和大于的链表快排
        leftmin = quickSort(leftmin->next);
        leftmax = quickSort(leftmax->next);

        //leftmin 可能为空
        lefteq = lefteq->next;
        righteq->next = leftmax;
        if(leftmin == nullptr) return lefteq;
        else
        {
            rightmin = leftmin;
            while(rightmin->next)
            {
                rightmin = rightmin->next;
            }
            rightmin->next = lefteq;
            return leftmin;
        }
    }
public:
    ListNode* sortList(ListNode* head) {
        return quickSort(head);
    }
};