归并排序及改进

 基本的递归排序

使用下面的归并方法，每次归并都使用一个额外数组，归并完之后再将有序的数组复制到目的数组中

/*归并A和B*/

void mergeAB(Item c[], Item a[], int N, Item b[], int M) {

    int i, j, k;

    for(i = 0, j = 0, k = 0; k < N + M; k++) {

        if(i == N) {c[k] = b[j++]; continue;}

        if(j == M) {c[k] = a[i++]; continue;}

        if(a[i] < b[j]) c[k] = a[i++];

        else c[k] = b[j++];

    }

}

 

改进的递归排序1

改进归并方法，每次都使用一个额外数组来存储，再下面的函数中，使用额外数组aux来存储零时的待排序数组，存储待排序数组时候需要将start到mid之间的元素按照原来的顺序放在aux中，而mid到end之间的元素则按照原来的顺序的倒序存放与aux中

如待排序数组为：A R S T G I N  

start = 0, mid = 3, end = 6

那么元素存放于aux中的顺序为：A R S T N I G

使用这种方式，则可以减少基本排序中的判断子序列是否已经到达末尾，即上面基本排序代码中的

if(i == N) {c[k] = b[j++]; continue;}

if(j == M) {c[k] = a[i++]; continue;}

这两个if语句。

/**

改进的归并方法，这样就可以减少检测是否到队尾的比较次数

*/

void merge(Item a[], int start, int mid, int end) {

    int i, j, k;

    Item *aux = (Item*)malloc(sizeof(Item) * (end-start+1));

    for(i = mid + 1; i > start; i--) aux[i-1] = a[i-1];

    for(j = mid; j < end; j++) aux[end+mid-j] = a[j+1];

 

    for(k = start; k <= end; k++)

        if(aux[i] < aux[j])

            a[k] = aux[i++];

        else

            a[k] = aux[j--];

}

 

 

改进的递归排序2

第二种改进方法避免了排序完之后的复制操作

#include <stdio.h>

#include <stdlib.h>

 

typedef char Item;

 

void mergeAB(Item c[], Item a[], int N, Item b[], int M);

void mergeSortAB(Item a[], Item b[], int l, int r);

void mergeSort(Item a[], int l, int r);

 

void main() {

    int i;

    Item a[] = {'A', 'R', 'S', 'T', 'G', 'I', 'N'};

    Item b[7];

    mergeSort(a, 0, 6);

    for(i = 0; i < 7; i++) {

        printf("%4c", a[i]);

    }

}

 

void mergeSort(Item a[], int l, int r) {

    int i;

    Item *aux = (Item*)malloc(sizeof(Item) * (r-l+1));

    for(i = 0; i < (r-l+1); i++) {

        aux[i] = a[i];

    }

    mergeSortAB(a, aux, l, r);

}

 

/*排序A，使用B作为辅助数组，然后在子调用中交换A，B的作用*/

void mergeSortAB(Item a[], Item b[], int l, int r) {

    if(r <= l) return;

    int m = (r + l) / 2;

    mergeSortAB(b, a, l, m);

    mergeSortAB(b, a, m+1, r);

    mergeAB(a+l, b+l, (m-l)+1, b+m+1, r-m);

}

 

/*归并A和B*/

void mergeAB(Item c[], Item a[], int N, Item b[], int M) {

    int i, j, k;

    for(i = 0, j = 0, k = 0; k < N + M; k++) {

        if(i == N) {c[k] = b[j++]; continue;}

        if(j == M) {c[k] = a[i++]; continue;}

        if(a[i] < b[j]) c[k] = a[i++];

        else c[k] = b[j++];

    }

}