归并排序-分治递归_设递归函数max对数组的处理区间是[low, high],以中间位置mid将原问题分解为两个子

目录

1、归并排序-分治递归原理

根据线性表分类

链表归并

顺序表归并

1、归并排序-分治递归原理

        将待排原始链表分成大小大致相同的2个新链表，分别对2个子链表进行排序，同理将以上2个链表继续拆分，最终将排好序的子集合合并就会得到一个排好序的集合 即为所求。(参考二叉树后序递归遍历)

---

2、根据线性表分类

        设归并排序的当前区间是R[low..high]，分治法的三个步骤是:
         ① 分解操作：将当前区间一分为二，即求分裂点 
        ② 求解递归：递归地对两个子区间R[low..mid]和R[mid+1..high] 进行归并排序；
        ③ 归并组合：将已排序的两个子区间R[low..mid]和R[mid+1..high] 归并为一个有序的区间                R[low..high]。

       顺序表归并

        通过数组上下限来确定中间位置mid。

#include <stdio.h>
#include <stdlib.h>
 
void Merge(int A[],int low,int mid,int high){
//表A的两段A[low...mid]和A [mid+l...high]各自有序，将它们合并成一个有序表
	int *B= (int*)malloc((high-low+1) *sizeof (int) ) ; 
	int i,j,k;
	for(k=low;k<=high;k++)
		B[k]=A[k]; //将A中所有元素复制到B中
		
	for (i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) 
	{
	
	if(B[i]<=B[j]) //〃比较B的左右两段中的元素
		A[k]=B[i++]; //将较小值复制到A中
	else
		A[k]=B[j++];
	}
	
	while (i<=mid) A[k++] =B [i++]; //〃若第一个表未检测完，复制
	while (j<=high) A[k++]=B[j++]; //若第二个表未检测完，复制
	
}
 
void MergeSort (int A[], int low, int high) {
	int mid;
	if(low<high){
	
	  mid=(low+high)/2; //从中间划分两个子序列
	  MergeSort (A, low, mid) ; //对左侧子序列进行递归排序
	  MergeSort (A, mid+1, high) ; //对右侧子序列进行递归排序
	  Merge (A,low,mid, high) ; //归并
	}	//if *
}
 
 int main()
 {
 	int a[5]={5,6,9,8,7};
 	int i;
 	
 	for(i=0;i<5;i++)
 	printf("%d",a[i]);
 	printf("\n");
 	
 	MergeSort(a,0,4);
 	for(i=0;i<5;i++)
 	printf("%d",a[i]);
 	printf("\n");
 }

        链表归并

通过快慢指针fast、slow来确定中间结点位置。

slow = slow->next;
fast = fast->next->next;

遍历完成后，right=slow->next；生成右边新链表的头结点。slow->next=NULL来拆分成两个新链表

#include <stdio.h>
#include <stdlib.h>
 
struct ListNode {
	int val;
 	struct ListNode *next;
};
 
void see(struct ListNode*head);
 
 //对递归分开后的链表两两相治 
struct ListNode* mergeSort(struct ListNode* left, struct ListNode* right) {
    struct ListNode* res = (struct ListNode*)malloc(sizeof(struct ListNode));
    res->val = 0;
    res->next = NULL;
    struct ListNode* head = res;
    //归并中的 "合"
    while (left && right) {
        if (left->val < right->val) {
            //左边小
            head->next = left;
            head = head->next;
            left = left->next;
        } else {
            //右边小
            head->next = right;
            head = head->next;
            right = right->next;
        }
    }
    //剩下的左边
    while (left) {
        head->next = left;
        head = head->next;
        left = left->next;
    }
    //剩下的右边
    while (right) {
        head->next = right;
        head = head->next;
        right = right->next;
    }
    return res->next;
}
 
struct ListNode* MSort(struct ListNode* head)//对初始链表进行递归分开 
{
 
	
	if (head == NULL || head->next == NULL) {
        return head;
    }
    
    struct ListNode* slow = head;
    struct ListNode* fast = head->next;
      // 使用快慢指针划分链表
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    struct ListNode* right = slow->next;
    slow->next = NULL;
 
    // 递归地对链表的两个部分进行归并排序
    struct ListNode* sortedLeft = MSort(head);
    struct ListNode* sortedRight = MSort(right);
    
    // 合并已排序的两个部分
    return mergeSort(sortedLeft, sortedRight);
	
 
}
 
 
//固定添加一组用力来测试 ，生成一个链表 ，头插法建立
struct ListNode* Add()
{
	struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
	newhead->next=NULL;
	int a[5]={1,6,2,3,4};// 4 3 2 6 1
	int i;
	for(i=0;i<5;i++)
	{
		struct ListNode* s=(struct ListNode*)malloc(sizeof(struct ListNode));
		
		s->val=a[i];
		s->next=newhead->next;
		newhead->next=s;
	}
	return newhead->next;
}
//输出链表数据 
void see(struct ListNode*head)
{
		while(head!=NULL)
	{	
		printf("%d",head->val);
		head=head->next;
	}
	printf("\n");
}
 
int  main()
{
	struct ListNode* head;
	head=Add();
	see(head);
	head=MSort(head);
	see(head);
	
 } 

此时MSort()算法中，参数head是不带头结点的链表。欲对带头结点的链表进行归并排序，则MSort()做如下更改：

 
struct ListNode* MSortD(struct ListNode* head) {
    if (head == NULL || head->next == NULL || head->next->next == NULL) {
        return head;
    }
    
    struct ListNode* slow = head->next;
    struct ListNode* fast = head->next->next;
    
    // 使用快慢指针划分链表
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    struct ListNode* right = slow->next;
    slow->next = NULL;
 
    // 递归地对链表的两个部分进行归并排序
    struct ListNode* sortedLeft = MSort(head->next);//重新将头结点取消
    struct ListNode* sortedRight = MSort(right);  //拆开的右边的新链表也是不带头结点
    
    // 合并已排序的两个部分
    return mergeSort(sortedLeft, sortedRight);
}