- 相干保举
C说话合并排序及实例代码详解
合并排序也称合并排序，其算法思惟是将待排序序列分为两局部，顺次对分得的两个局部再次利用合并排序，以后再对其停止合并。本文是小编搜刮清算的对于C说话合并排序及实例代码详解，供参考进修，但愿对大师有所赞助!
仅从算法思惟上领会合并排序会感觉很笼统，接上去就以对序列A[0], A[l]…, A[n-1]停止升序摆列来停止讲授，在此接纳自顶向下的完成方式。
操纵步骤以下：
(1)将所要停止的排序序列分为摆布两个局部，若是要停止排序的序列的肇端元素下标为first，最初一个元素的下标为last，那末摆布两局部之间的临界点下标mid=(first+last)/2，这两局局部别是A[first … mid]和A[mid+1 … last]。
(2)将下面所分得的两局部序列持续根据步骤(1)持续停止分别，直到分别的区间长度为1。
(3)将分别竣事后的序列停止合并排序，排序方式为对所分的n个子序列停止两两合并，获得n/2或n/2+l个含有两个元素的子序列，再对获得的子序列停止合并，直至获得一个长度为n的有序序列为止。
下面经由过程一段代码来看若何完成合并排序。
#include
#include
#define N 7
void merge(int arr[], int low, int mid, int high){
int i, k;
int *tmp = (int *)malloc((high-low+1)*sizeof(int));
//请求空间，使其巨细为两个
int left_low = low;
int left_high = mid;
int right_low = mid + 1;
int right_high = high;
for(k=0; left_low<=left_high && right_low<=right_high; k++){ // 比拟两个指针所指向的元素
if(arr[left_low]<=arr[right_low]){
tmp[k] = arr[left_low++];
}else{
tmp[k] = arr[right_low++];
}
}
if(left_low <= left_high){ //若第一个序列有残剩，间接复制出来粘到合并序列尾
//memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
for(i=left_low;i<=left_high;i++)
tmp[k++] = arr[i];
}
if(right_low <= right_high){
//若第二个序列有残剩，间接复制出来粘到合并序列尾
//memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
for(i=right_low; i<=right_high; i++)
tmp[k++] = arr[i];
}
for(i=0; i<high-low+1; i++)
arr[low+i] = tmp[i];
free(tmp);
return;
}
void merge_sort(int arr[], unsigned int first, unsigned int last){
int mid = 0;
if(first<last){
mid = (first+last)/2; /* 注重避免溢出 */
/*mid = first/2 + last/2;*/
//mid = (first & last) + ((first ^ last) >> 1);
merge_sort(arr, first, mid);
merge_sort(arr, mid+1,last);
merge(arr,first,mid,last);
}
return;
}
int main(){
int i;
int a[N]={32,12,56,78,76,45,36};
printf ("排序前 ");
for(i=0;i<N;i++)
printf("%d ",a[i]);
merge_sort(a,0,N-1); // 排序
printf (" 排序后 ");
for(i=0;i<N;i++)
printf("%d ",a[i]); printf(" ");
system("pause");
return 0;
}
运转成果：
排序前
32 12 56 78 76 45 36
排序后
12 32 36 45 56 76 78
阐发下面的运转成果，经由过程合并排序胜利地完成了对给定序列的排序操纵。接上去经由过程图来领会合并排序的详细操纵流程。
鄙人图先对所要停止排序的序列停止分化，直到分为单个元素为止，而后将其停止两两合并。因为终究分化成单个元素，是以在合并的时辰.将小数放在前面，大数放在前面，获得一个有序序列。接上去对两个相连的有序序列停止排序，先比拟有序序列中的第一个元素，将较小的元素放入姑且数组中，接着将较小元素地点数组的下一个元素与另外一个数组中的较小元素比拟，一样将较小元素放入姑且数组中，顺次停止，直到两个数组的一切元素都放入姑且数组中，最初再将姑且数组的元素放入原始数组中的对应地位。
【C说话合并排序及实例代码详解】相干文章：
C说话疾速排序实例代码06-04
C说话挑选排序算法及实例代码07-25
C说话拔出排序算法及实例代码07-02
C说话典范冒泡排序法详解08-03
C说话以数据块的情势读写文件实例代码10-09
C说话中利用疾速排序算法对元素排序的实例06-20
C说话完成合并排序算法实例09-18
c++疾速排序详解10-18
桶排序算法的懂得及C说话版代码示例07-11