|
#include <stdio.h>
#include <windows.h>
void merge(int a[], int b[], int start, int mid, int end);
void mergeSort(int a[], int b[], int start, int end);//递归
void mergeSort2(int a[], int b[], int n);//非递归
void mergePass(int a[], int b[], int n, int h);
int main(void)
{
?? ?int a[] = {6, 2, 3, 5, 4, 7, 8, 1, 9};
?? ?int n = sizeof(a)/sizeof(int);
?? ?int * b = (int*)malloc(sizeof(int)*n);
?? ?if(b != NULL)
?? ?{
?? ??? ?mergeSort(a, b, 0, n-1);
?? ??? ?//mergeSort2(a, b, n);
?? ??? ?free(b);
?? ?}
?? ?for(int i = 0; i < n; i++)
?? ??? ?printf("%d ", a[i]);
?? ?printf("\n");
?? ?system("pause");
?? ?return 0;
}
void merge(int a[], int b[], int start, int mid, int end)
{?? ?
?? ?int i = start;
?? ?int j = mid + 1;
?? ?int k = start;
?? ?while(i <= mid && j <= end)
?? ?{
?? ??? ?if(a[i] <= a[j])
?? ??? ??? ?b[k++] = a[i++];
?? ??? ?else
?? ??? ??? ?b[k++] = a[j++];
?? ?}
?? ?while(i <= mid)
?? ??? ?b[k++] = a[i++];
?? ?while(j <= end)
?? ??? ?b[k++] = a[j++];
?? ?while(start <= end)
?? ??? ?a[start++] = b[start];
}
//递归
void mergeSort(int a[], int b[], int start, int end)
{?? ?
?? ?if(start < end)
?? ?{
?? ??? ?int mid = (start+end)/2;
?? ??? ?mergeSort(a, b, start, mid);
?? ??? ?mergeSort(a, b, mid+1, end);
?? ??? ?merge(a, b, start, mid, end);
?? ?}
}
//非递归
void mergeSort2(int a[], int b[], int n)
{
?? ?int h = 1;
?? ?while(h < n)
?? ?{
?? ??? ?mergePass(a, b, n, h);
?? ??? ?h *= 2;
?? ??? ?mergePass(b, a, n, h);
?? ??? ?h *= 2;
?? ?}
}
void mergePass(int a[], int b[], int n, int h)
{
?? ?int i = 0;
?? ?while(i <= n-2*h)
?? ?{
?? ??? ?merge(a, b, i, i+h-1, i+2*h-1);
?? ??? ?i += 2*h;
?? ?}
?? ?if(i < n-h)
?? ??? ?merge(a, b, i, i+h-1, n-1);
?? ?else
?? ?{
?? ??? ?for(int j = i; j < n; j++)
?? ??? ??? ?b[j] = a[j];
?? ?}
}
|