学步园

/*合并排序：merge sort
  1.分解Divide：将n个元素分成各含n/2个元素的子序列
  2.解决Conquer：递归 用合并排序法对2个子序列递归的排序
  3.合并Combine:合并2个已排序的子序列以得到排序结果
*/
#include <stdio.h>
#include <iostream>
using namespace std; 
#define N 8
#define MAX 100  //哨兵 
 
 void merge(int a[N],int p,int q,int r){
         int n1=q-p+1;
         int n2=r-q;
         int L[N],R[N];
         for(int i=0;i<n1;i++)
             L[i]=a[p+i];
         for(int i=0;i<n2;i++)
             R[i]=a[q+i+1];
         L[n1]=MAX;
         R[n2]=MAX;
         int i=0;
         int j=0;
         for(int k=p;k<=r;k++){
              if(L[i]<=R[j]){
                   a[k]=L[i];
                   i++;               
              }else{
                     a[k]=R[j];
                     j++;
              }
                      
         }
 } 
 
void merge_sort(int a[],int p,int r){
     if(p<r){
        int q=(p+r)/2;
        merge_sort(a,p,q);
        merge_sort(a,q+1,r);
        merge(a,p,q,r);        
     }
}

int main(){
 int a[N]={5,2,4,7,1,3,2,6};
 merge_sort(a,0,N-1);
 for(int i=0;i<N;i++){
    printf("%d ",a[i]);        
 }
 printf("\n");
 
 return 0;   
}

public class insertsort{
	public static int MAX=1000;//哨兵
	public static void main(String[] args){
		int[] a={5,2,4,6,1,3};
		insertsort.mergeSort(a,0,a.length-1);
		//for(int e:a){
		for(int i=0;i<6;i++){
			System.out.printf("%d ",a[i]);
		}
		System.out.println();
	}

	public static void mergeSort(int[] a,int p,int r) {
		if(p<r){
			int q=(p+r)/2;
			mergeSort(a,0,q);
			mergeSort(a,q+1,r);
			merge(a,p,q,r);
		}
		
		
	}

	public static void merge(int[] a, int p, int q,int r) {
		int n1=q-p+1;
		int n2=r-q;
		int[] L=new int[n1+1];
		int[] R=new int[n2+1];
		for(int i=0;i<n1;i++)
			L[i]=a[p+i];
		for(int i=0;i<n2;i++)
			R[i]=a[q+i+1];
		L[n1]=MAX;
		R[n2]=MAX;
		int k=p;//原先写成k=0;老报错
		int i=0;
		int j=0;
		while(k<r+1){
			if(L[i]<=R[j]){
				a[k]=L[i];
				i++;
			}else if(L[i]>R[j]){
				a[k]=R[j];
				j++;
			}
			k++;
		}
		
		
	}

	
}


class mergesort(object):
    MAX=100
    def merge_sort(self,a,p,r):
        if p<r:
            q=int(p+r)//2
            s.merge_sort(a,p,q)
            s.merge_sort(a,q+1,r)
            s.merge(a,p,q,r)

    def merge(self,a,p,q,r):
        left=a[p:q+1]
        right=a[q+1:r+1]
        left.append(s.MAX)
        right.append(s.MAX)
        for i in range(p,r+1):
            if left[0]<=right[0]:
                a[i]=left.pop(0)
            else:
                a[i]=right.pop(0)



if __name__=="__main__":
    array=[5,2,4,6,1,3]
    s=mergesort()
    s.merge_sort(array,0,5)

    for a in array:
        print("%d " %a,end="")
    print("\n")