站长工具怎么关闭,公司怎么样做网站,做网站反复修改,宁波自助建网站归并排序思想#xff1a; 归并排序可以解释为是将放在数组里的一串数字进行拆分#xff0c;拆分之后再判断大小合并的过程#xff0c;每次都是从中间位置拆分#xff0c;例如有七个数#xff0c;第一次拆分就将它们分成前三个数为一个数组#xff0c;后四个数为一个数组 归并排序可以解释为是将放在数组里的一串数字进行拆分拆分之后再判断大小合并的过程每次都是从中间位置拆分例如有七个数第一次拆分就将它们分成前三个数为一个数组后四个数为一个数组我们拆分之后在堆区开辟空间来存放这两个数组将拆分的两个数组按照第一次拆分一样的方法对它俩再进行拆分直到每个数组里面都只有一个元素就结束拆分之后从最后往前依次判断合并。 #include stdio.h
#include stdlib.h
void sort(int *a,int n); //拆分
void merge(int *a,int *left,int leftlen,int *right,int rightlen); //合并
void show(int *a,int n);
int main(int argc, char *argv[])
{ int a[10] {5,46,12,34,55,9,48,79,23,10};puts(排序前);show(a,10);sort(a,10);puts(排序后);show(a,10);return 0;
}
void merge(int *a,int *left,int leftlen,int *right,int rightlen) //合并
{int i0; //左边数组的下标int j0; //右边数组的下标int k0; //归并数组的下标while(leftleni rightlenj){if(left[i]right[j]) //从小到大排列合并{a[k] left[i];}elsea[k] right[j];}if(leftleni) //如果右边数组拿完左边数组还有就将剩下的全部放入合并数组{a[k] left[i];}if(rightlenj) //反之{a[k] right[j];}
}
void sort(int *a,int n) //拆分
{if(n2) //递归终止条件当数组中元素只有一个时就结束return;int mid n/2; //求中间值int *left (int *)malloc(sizeof(int)*mid); //开存放拆分数据的空间int *right (int *)malloc(sizeof(int)*(n-mid));for(int i0;imid;i) //将a左边的数据存入left{left[i] a[i];}for(int jmid;jn;j) //将a右边的数据存入right{right[j-mid] a[j];}sort(left,mid); //将left中的数再进行拆分sort(right,n-mid); //将right中的数据再进行拆分merge(a,left,mid,right,n-mid);free(left); //释放空间free(right);
}
void show(int *a,int n)
{for(int i0;in;i){printf(%d ,a[i]);}puts();
}
解析在上述思想中我们提到了对不同的数组做同样的操作因此这里就可以通过使用递归函数来实现我们将代码分为两个函数来写一个是拆分函数另一个是合并函数
拆分函数 拆分函数我们需要传进去的参数为数组元素首地址和数组长度既然拆分函数为递归函数那我们就需要有结束条件在这里结束条件就为数组长度n为1时就结束拆分首先是找到数组中间的元素下标从中间拆分为左右两个数组根据左右数组长度来开辟对应大小的空间开辟完空间之后将左右数组元素存入到空间中存入之后再调用拆分函数自己将左右函数的元素首地址和长度当做参数传入这样就可以再次对函数进行拆分拆分结束之后就是合并函数
合并函数 合并函数需要传入的参数有五个第一个就是原来需要拆分的数组的首地址用来存放合并后的元素后面四个参数分别是左边数组的元素首地址、左边数组的长度、右边数组的元素首地址、右边数组的长度在合并函数里面我们首先需要定义三个变量分别来代表左边数组的元素下标、右边数组的元素下标和合并数组的元素下标在合并的时候只要左右两边数组都有元素就需要进行判断大小于是循环表达式为leftleni rightlenj在比较完之后就是将数存入合并数组存入哪个数组的数就让对应数组的下标自加1这样下次就能判断下一个数直到有一边数组中的元素被全部拿出存入到合并数组就结束循环判断这时需要判断左右数组中是否有剩余的元素有的话依次存入到合并数组中 合并函数写完之后我们就可以在拆分函数中调用它在左右数组拆分完之后就调用合并函数进行合并合并完成之后还有一件事宝子们不要忘啦那就是释放空间因为存放左右数组元素的空间是我们自己开辟的堆区空间所以需要我们自己释放。释放之后排序也就结束了最后再循环遍历一下原数组就可以看到已经排好序啦。
