C语言-数据结构-归并排序(merge sort)-递归迭代-源代码及分析

布满荆棘的人生 2022-07-11 12:24 191阅读 0赞

**1. 归并排序**

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序常用递归的方式实现，但是由于递归的固有缺陷，比如占用较大的运行空间，有些场合也会用迭代的方式。归并排序的时间复杂度为O(n\*logn).

**2. 源代码**

**2.1 递归**

#include <stdio.h>
    #define MAX_SIZE 10
    
    /**
     * @para l is left group start point
     * @para l_size is left group length
     * @para r is right group start point
     * @para r_size is right group length
    */
    void merging(int *l, int l_size, int *r, int r_size)
    {
    	int i, j, k, temp[MAX_SIZE];
    	i = j = k = 0;
    	while (i<l_size && j<r_size)
    	{
    		if (l[i]<r[j])
    		{
    			temp[k++] = l[i++];
    		}
    		else
    		{
    			temp[k++] = r[j++];
    		}
    	}
    	while (i<l_size)
    	{
    		temp[k++] = l[i++];
    	}
    	while (j<r_size)
    	{
    		temp[k++] = r[j++];
    	}
    
    	for (i = 0; i<l_size + r_size; i++)
    	{
    		l[i] = temp[i];
    	}
    }
    
    /**
     * @para a[] the array contain data need be sorted
     * @array length need be sorted, started from inde 0
     */
    void mergesort(int a[], int n)
    {
    	// left start point
    	int *l = a;
    	// right start point
    	int *r = a + n / 2;
    	// left size
    	int l_size = n / 2;
    	// right size
    	int r_size = n - l_size;
    
    	if (n>1)	// recursion condition
    	{
    		mergesort(l, l_size);	//sort left group
    		mergesort(r, r_size);	//sort right group
    		merging(l, l_size, r, r_size);	//merge left and right group together
    	}
    }
    
    int main(void)
    {
    	int i;
    	int a[10] = { 8,5,2,6,0,3,9,1,7,4 };
    	printf("排序前：");
    	for (i = 0; i<10; i++)
    	{
    		printf("%d", a[i]);
    	}
    	mergesort(a, 10);
    	//printf("\n\n共交换数据%d次\n\n", c);
    	printf("排序后：");
    	for (i = 0; i<10; i++)
    	{
    		printf("%d", a[i]);
    	}
    	printf("\n\n\n");
    	return 0;
    }

**2.2 迭代**

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 10
    
    void MergeSort(int k[], int n)
    {
    	int i, next, left_min, left_max, right_min, right_max;
    	int *temp = (int *)malloc(n * sizeof(int));
    
    	for( i=1; i < n; i*=2 ) //i 为步长， 1， 2， 4， 8...
    	{
    		for( left_min=0; left_min < n-i; left_min = right_max )//从0开始，根据步长，向右分组排序
    		{
    			right_min = left_max = left_min + i;
    			right_max = left_max + i;
    
    			if( right_max > n )
    			{
    				right_max = n;
    			}
    
    			next = 0;
    
    			//将k[]数组中小的数据备份到temp[]数组中，
    			//结束条件是left部分或者right部分有一个已经完全拷贝到temp[]中
    			while( left_min < left_max && right_min < right_max )
    			{
    				if( k[left_min] < k[right_min] )
    				{
    					temp[next++] = k[left_min++];
    				}
    				else
    				{
    					temp[next++] = k[right_min++];
    				}
    			}
    
    			//现在k[]数组中没有备份的都是大的数据，有两种可能性，
    			//一种是left部分拷贝完成，另一种可能性是right部分拷贝完成,对于后一种情况，
    			//无需考虑，因为right部分本来就排在k[]数组中靠后的位置，
    			//也就是存放大数据的位置，这里只需要考虑第一种情况，将left部分的较大的数据，从k[left_max]，开始，
    			//覆盖到k[right_min]的位置（k[right_min]中的数据上一部已经拷贝到temp[]数组中）
    			while( left_min < left_max )
    			{
    				k[--right_min] = k[--left_max];
    			}
    
    			while( next > 0 )//，将temp[]数组中备份的数据重新拷贝回k[]数组中
    			{
    				k[--right_min] = temp[--next];
    			}
    		}
    	}
    }
    
    int main()
    {
    	int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    
    	MergeSort(a, 10);
    
    	printf("排序后的结果是：");
    	for( i=0; i < 10; i++ )
    	{
    		printf("%d", a[i]);
    	}
    	printf("\n\n");
    
    	return 0;
    }