归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
写这个算法很简单，原理也很简单，但是陷阱在与这个算法中对数组的使用，下标的访问和控制。一般归并排序都是用1作下标，但是今天作死想用0作下标。恩~一直没有转过脑筋来，但是最终还是实现了。
源代码如下：
<pre class="brush:cpp;toolbar:false">#include<iostream> #include<ctime> #include<cstdlib> using namespace std; const int N = 204800; void Merge(int arr[], int p, int q, int r){ int n1 = q - p 1; int n2 = r - q 1; int left[n1 1], right[n2]; for (int i = 0; i != n1; i){ left[i] = arr[p i]; } left[n1] = N; for (int j = 0; j != n2 - 1; j){ right[j] = arr[q j 1]; } right[n2 - 1] = N; int i = 0, j = 0; for(int k = p; k != r 1; k){ if(left[i] > right[j]){ arr[k] = right[j]; j; } else{ arr[k] = left[i]; i; } } } void MergeSort(int arr[], int p, int r){ if(p < r){ int q = (p r)/2; MergeSort(arr, p, q); MergeSort(arr, q 1, r); Merge(arr, p, q, r); } } int main(){ int arr[10] = {300, 60, 22, 16, 85, 89, 30, 99, 103, 55}; MergeSort(arr, 0, 9); for(int i = 0; i < 10; i){ cout<<arr[i]<<endl; } return 0; }</pre>
开始的ctime本来打算用时间做种子出随机数。但是这个随机数和正态分布略符合，弃之。随机数部分代码如下：
<pre class="brush:cpp;toolbar:false">srand(time(NULL)); int arr[rand()0]; for (int i = 0; i != sizeof(arr)/sizeof(int); i){ arr[i] = rand()P0; } for (int i = 0; i != sizeof(arr)/sizeof(int); i){ cout<<arr[i]<<" "; if((i 1) % 10 == 0) cout<<endl; } cout<<"end"<<endl; MergeSort(arr, 0, sizeof(arr)/sizeof(int)); for (int i = 0; i != sizeof(arr)/sizeof(int); i){ cout<<arr[i]<<" "; if((i 1) % 10 == 0) cout<<endl; }</pre>
C 归并排序实现（算法导论）
基本思想：设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array[low..m]，array[m 1..high]，先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中，待合并完成后将 temp 复制回 array[low..high]中，从而完成排序。
<pre class="brush:cpp;toolbar:false">#include <iostream> using namespace std; void merge(int *data, int p, int q, int r) { int n1, n2, i, j, k; int *left=NULL, *right=NULL; n1 = q-p 1; n2 = r-q; left = (int *)malloc(sizeof(int)*(n1)); right = (int *)malloc(sizeof(int)*(n2)); for(i=0; i<n1; i ) //对左数组赋值 left[i] = data[p i]; for(j=0; j<n2; j ) //对右数组赋值 right[j] = data[q 1 j]; i = j = 0; k = p; while(i<n1 && j<n2) //将数组元素值两两比较，并合并到data数组 { if(left[i] <= right[j]) data[k ] = left[i ]; else data[k ] = right[j ]; } for(; i<n1; i ) //如果左数组有元素剩余，则将剩余元素合并到data数组 data[k ] = left[i]; for(; j<n2; j ) //如果右数组有元素剩余，则将剩余元素合并到data数组 data[k ] = right[j]; } void mergeSort(int *data, int p, int r) { int q; if(p < r) //只有一个或无记录时不须排序 { q = (int)((p r)/2); //将data数组分成两半 mergeSort(data, p, q); //递归拆分左数组 mergeSort(data, q 1, r); //递归拆分右数组 merge(data, p, q, r); //合并数组 } } int main() { int n; int* input = NULL; //输入数据 cout<<"请输入数组的长度: "; cin>>n; input = (int *)malloc(sizeof(int)*(n)); cout<<"请对数组赋值: "; for(int i=0; i<n; i) { cin>>input[i]; } //处理数据 mergeSort(input,0,n-1); //输出结果 for(int i=0; i<n; i) cout<<input[i]<<" "; cout<<endl; system("pause"); return 0; }</pre>
您可能感兴趣的文章：
php 实现冒泡排序的简单例子
php数组排序方法大全(脚本学堂整理奉献)
javascript排序算法之合并排序与归并排序的例子
javascript排序算法代码解析
php排序算法 PHP版快速排序与冒泡排序
PHP中经典的四大排序算法
PHP二维数组排序的函数
java数组降序和升序排序例子
排序算法—归并排序【附代码】
php基础算法有哪几种
