归并排序(Merging Sort)----(排序算法十三)

谁践踏了优雅 2022-09-17 14:25 176阅读 0赞

# 1.算法原理 #

# 2.代码实现 #

#include <stdio.h>
    
    //printArray打印出数组
    void printArray(int a[],int size){  
        printf("数组为：%d ",a[0]);  
        for (int i=1;i<size;i++)  
        {  
            printf(" %d ",a[i]);  
        }  
        printf("\n");  
    }
    
    
    //将有二个有序数列a[first...mid]和a[mid...last]合并。
    void mergearray(int a[], int first, int mid, int last, int temp[])
    {
    	printArray(a,last);
    	int i = first, j = mid + 1;
    	int m = mid,  n = last;
    	int k = 0;
    	while (i <= m && j <= n)
    	{
    		if (a[i] <= a[j])
    			temp[k++] = a[i++];
    		else
    			temp[k++] = a[j++];
    	}
    	while (i <= m)
    		temp[k++] = a[i++];
    	while (j <= n)
    		temp[k++] = a[j++];
    	for (i = 0; i < k; i++)
    		a[first + i] = temp[i];
    }
    
    //递归归并排序
    void mergesort(int a[], int first, int last, int temp[])
    {
    	if (first < last)
    	{
    		int mid = (first + last) / 2;
    		mergesort(a, first, mid, temp);    //左边有序
    		mergesort(a, mid + 1, last, temp); //右边有序
    		mergearray(a, first, mid, last, temp); //再将二个有序数列合并
    	}
    }
    
    bool MergeSort(int a[], int n)
    {
    	int *p = new int[n];
    	if (p == NULL)
    		return false;
    	mergesort(a, 0, n - 1, p);
    	delete[] p;
    	return true;
    }
    
    void main()
    {
    	int  a[10] ={9,8,7,6,5,4,3,2,1,0};  
    	MergeSort(a,10);
    	printArray(a,10);
    }

# 3.结果 #

数组为：9
    数组为：8  9
    数组为：7  8  9  6
    数组为：7  8  9  5
    数组为：5  6  7  8  9  4
    数组为：5  6  7  8  9  3  4
    数组为：5  6  7  8  9  2  3  4  1
    数组为：5  6  7  8  9  2  3  4  0
    数组为：5  6  7  8  9  0  1  2  3
    数组为：0  1  2  3  4  5  6  7  8  9