2015年9月17日

Merge Sort 合併排序法

#include "iostream"

void mergesort(int a[],int left,int right);
void merge(int a[],int left,int mid,int right);
int main()
{
    int number=9;
    int data[]={5,6,4,8,2,3,7,9,1};
    int i;

    for (i=0;i<number;i++){
        printf("%d",data[i]);
    }
    printf("\n");

    mergesort(data,0,number-1);

    printf("\n");
    for (i=0;i<number;i++){
        printf("%d",data[i]);
    }

    printf("\n");
    system("PAUSE");
    return 0;
}

void mergesort(int data[],int left,int right){
  int mid;
  if (right>left){
      mid=(right+left)/2;
      mergesort(data,left,mid);
      mergesort(data,mid+1,right);
      merge(data,left,mid,right);
  }
}

void merge(int data[],int left,int mid,int right){
  int rux[right-left+1];
  int i=left;
  int j=mid+1;
  int k;
  for (k=0;k<right-left+1;k++){
    if (i==mid+1){
       rux[k]=data[j];
       j++;
    }else if (j==right+1){
       rux[k]=data[i];
       i++;
    }else{
       rux[k]= data[i]<data[j] ? data[i++]:data[j++];
    }
  }
  for (k=0,j=left;j<right+1;j++,k++)
  data[j]=rux[k];
}

沒有留言:

張貼留言