常用排序算法――归并排序法 - JAVA

归并排序采用的是分治思想，将数组不断分解为子数组，直到子数组只有一个元素，每次分解对应一个归并函数，归并函数可以将当前分解的两个子数组合并起来。有两种方式可以实现归并排序，第一种是递归方式实现的，代码如下：

#include 
  
   

static void merge( int* array, int* tmp, size_t start, size_t end){
    size_t i = start, j = (start+end)/2, pos = start;
    while(i != (start+end)/2 && j != end){
        if(array[i] < array[j]){
            tmp[pos++] = array[i++];
        }
        else{
            tmp[pos++] = array[j++];
        }
    }

    for(;i != (start+end)/2; ++i){
        tmp[pos++] = array[i];
    }

    for(;j != end; ++j){
        tmp[pos++] = array[j];
    }

    for(i = start; i != end; ++i){
        array[i] = tmp[i];
    }
}

static void merge_sort_service (int * array, int* tmp, size_t start, size_t end){
    if(end-start > 2){
        merge_sort_service(array, tmp, start, (start+end)/2);
        merge_sort_service(array, tmp, (start+end)/2, end);
    }
    merge(array, tmp, start, end);
}

void merge_sort( int* array, size_t len){
    int* pArray = new int[len];
    merge_sort_service(array, pArray, 0, len);
    delete [] pArray;
}

int main(){
    int array[10] = {3, 9, 5, 1, 8, 7, 2, 4, 6, 0};
    merge_sort(array, 10);

    for(int i = 0; i != 10; ++i){
        std::cout << array[i] << " ";
    }
    std::cout << std:: endl;
    return 0;
}

第二种是基于循环的非递归方式实现的，整体性能要高于递归方式实现的归并排序，代码如下：

#include 
  
   

void merge( int* array, int* tmp, size_t length, size_t step){
    size_t i, j, pos, i_stop, j_stop;
    size_t k = 0;
    size_t stop = length-step;

    while(k < stop){
        pos = k;
        i_stop = k+step-1;
        j_stop = (k+2*step)<(length) (k+2*step-1):(length-1);

        for(i = k, j = k+step; i <= i_stop && j <= j_stop; ){
            if(array[i] < array[j]){
                tmp[pos++] = array[i++];
            }
            else{
                tmp[pos++] = array[j++];
            }
        }

        while(i <= i_stop){
            tmp[pos++] = array[i++];
        }

        while(j <= j_stop){
            tmp[pos++] = array[j++];
        }

        k += 2*step;
    }

    for(i = 0; i != length; ++i){
        array[i] = tmp[i];
    }
}

void merge_sort( int* array, size_t length ){
    int* tmp = new int[length ];
    size_t k = 1;
    while(k < length){
        merge(array, tmp, 10, k);
        k *= 2;
    }
    delete [] tmp;
}

int main(){
    int array[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

    merge_sort(array, 10);

    for(int i = 0; i != 10; ++i){
        std::cout << array[i] << " ";
    }
    std::cout << std:: endl;
    return 0;
}

由于后一种方法使用的是循环而非递归，减少了函数调用及堆栈开销，效率上高于第一种，但编写起来比第一种实现方式麻烦。

本文链接：http://blog.csdn.net/girlkoo/article/details/17606331

本文作者：girlkoo