排序——归并排序（递归实现+迭代实现 ）

递归实现

//归并排序  递归实现 
#include <iostream>
using namespace std;

#define MAXSIZE 10

// 实现归并，并把最后的结果存放到 list1里 
void  merging(int *list1, int list1_size , int *list2, int list2_size)
{
    int i , j ,k ,m ;
    int temp[MAXSIZE];
    
    i = j = k = 0;
    
    while( i < list1_size && j < list2_size )
    {
        if( list1[i] < list2[j] )
        {
            temp[k++] = list1[i++];
        }
        else
        {
            temp[k++] = list2[j++];
        }
    }
    
    while( i < list1_size )
    {
        temp[k++] = list1[i++];
    }
    
    while( i < list2_size )
    {
        temp[k++] = list2[j++];
    }
    
    for( m=0; m < (list1_size + list2_size); m++ )
    {
        list1[m] = temp[m]; 
    }
}


void MergeSort( int k[], int n )
{
    if( n > 1)
    {
        int *list1 = k;
        int list1_size = n/2;
        int *list2 = k + n/2;
        int list2_size = n - list1_size; 
        
        MergeSort(list1, list1_size);
        MergeSort(list2, list2_size);
        
        merging(list1, list1_size , list2, list2_size);//归并
    }
    
}

int main()
{
    int i ,a[10] = {5,2,6,0,3,9,1,7,4,8};
    
    MergeSort(a,10);
    
    for( i=0; i < 10 ;i++ )
    {
        cout << a[i];
    }
    
    cout << endl;
    
    return 0;
}

迭代实现

//归并排序  迭代实现 
#include <iostream>
#include <stdlib.h>
using namespace std;

#define MAXSIZE 10

void MergeSort( int k[], int n )
{
    int i, left_min, left_max, right_min, right_max;
    
    int *temp = (int *)malloc(n * sizeof(int));
     
    for( i=1; i < n; i*=2 )//步长 
    {
        for( left_min=0; left_min < n-i; left_min = right_max )
        {
            right_min = left_max = left_min + i ;
            right_max = left_max + i;
            
            if( right_max > n ) //不能大于元素的个数  
            {
                right_max = n;
            }
            
            int next = 0;
            
            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++];
                }
            } 
            
            while( left_min < left_max ) //如果Lmin 没有走到LMAX的位置 说明L还有元素 
            {
                k[--right_min] = k[--left_max ]; //把L的元素放在R的头部位置 
            }
            
            while( next > 0 )
            {
                k[--right_min] = temp[--next]; //把整个数组还原到 刚刚剩下那个最大元素的后面 
            }
            
        }
    }
}

int main()
{
    int i ,a[10] = {5,2,6,0,3,9,1,7,4,8};
    
    MergeSort(a,10);
    
    for( i=0; i < 10 ;i++ )
    {
        cout << a[i];
    }
    
    cout << endl;
    
    return 0;
}