|
|
Posted on 2009-09-24 13:10 赞劲小子 阅读(491) 评论(0) 编辑 收藏 引用 所属分类: 算法设计与分析
算法基本思想：将要排序的数组分成两部分，先对每部分进行排序，然后再将两部分已经排序好的子数组的元素按从小到大的顺序交替地摆放在一个新的数组中。这一过程时常需要多次分解和组合，因而是一个递归过程。
 #include "stdio.h"
#include "malloc.h"
#define arraySize 11
void mergeSort(int a[], int low, int high);
void merge(int a[], int low, int mid, int high);
void print(int a[], int n);
static int count = 1; //***************测试语句
  int main() {
  int a[11] = {0,-1,5,6,2,8,10,3,56,32,43};
 int i;
mergeSort(a,0,arraySize-1);
for(i = 0; i < arraySize; i++)
printf("%d ",a[i]);
return 0;
 }
void mergeSort(int a[], int low, int high){
int mid;
printf("mergeSort 进行了%d次\n",count);
if(low < high){
mid = (low + high) / 2;
mergeSort(a,low,mid);
mergeSort(a,mid+1,high);
merge(a,low,mid,high); //将数组A[low:mid]和A[mid+1:high]进行合并。
 }
count++;
}
void merge(int a[], int low, int mid, int high){
/**//*
* 将数组a[low : mid] 和数组a[mid+1 : high]进行有序合并
*/
int *tempArray = (int *)malloc(sizeof(int) * (high + 1));
int h,i,j,k;
h = low; //游离第一个数组的下标
i = low; //用于
j = mid + 1; //用于要合并的第二个数组的出下标
while(h <= mid && j <=high)
{
if(a[h] <= a[j]){
tempArray[i] = a[h];
h = h+1;
}
else
{
tempArray[i] = a[j];
j = j+1;
}
i = i + 1;
}
/**//*
* 元素没取尽时的处理
*/
if(h > mid){ //第一个数组取尽，第二个数组未被取尽
for(k = j; k <= high; k++){
tempArray[i] = a[k];
i++;
}
}
else
{
for(k = h; k <= mid; k++){
tempArray[i] = a[k];
i++;
}
}
/**//*
* 最后将tempArray数组赋值给a
*/
for( k = low; k <= high; k++)
{
a[k] = tempArray[k];
}
/**//* print(tempArray,10);*/
free(tempArray);
}
void print(int a[], int n){
int i;
printf("数组是");
for(i = 0; i < n ; i++){
printf("%d ",a[i]);
}
printf("\n");
}
|