归并排序
（一） 归并排序介绍
归并排序是一种稳定的排序方法，时间复杂度O（n log（n）），主要思路是递归实现，把数组a[] ，分成两部分，分别进行排序，然后从新排序的两个（其中实现的时候用一个子数组就搞定了，这是个牛X的地方）子数组中取较小的数放入保存最后结果的数组中。核心思想：就是把两个已经排好的数组合成一个排序的数组。（显然是递归了）
（二） 归并排序的代码实现
代码一： #include<iostream> using namespace std; int Sort(int a[],int merge[],int low,int high)//把a中的值排序到merge中 { int b[100];//这是个temp局部值，它能保存两个半区 int mid=(high+low)/2; int i=low,j=mid+1,k=low; ///////////////////////////////////////////////////////////////////////////////////// if(low>=high) //递归出口 { if(low==high) merge[low]=a[low]; return 0; } ////////////////////////////////////////////////////////////////////////////////////// Sort(a,b,low,mid); //分成两个子数组，进行排序 Sort(a,b,mid+1,high); ///////////////////////////////////////////////////////////////////////////////////// while((i<=mid)&&(j<=high)) //进行合并操作 { if(b[i]<=b[j]) { merge[k++]=b[i++]; } else { merge[k++]=b[j++]; } } while(i<=mid) { merge[k++]=b[i++]; } while(j<=high) { merge[k++]=b[j++]; } return 0; } ////////////////////////////////////////////////////////////////////////////////////// int main() { int a[]={3,1,4,5,2,7,9,8,10}; int merge[100]; Sort(a,merge,0,8); for(int i=0;i<9;i++) cout<<merge[i]<<endl; return 0; }
其实，该算法是递归排序中套一个合并（merge），所以可以改成两个函数，一个是merge_sort(),一个是merge() 。这样代码分割比较好：
代码2 #include<iostream> using namespace std; void merge(int a[],int low,int mid,int high) { int b[100]; //合并排序结果先保存到b中 int i=low,j=mid+1,k=low; while((i<=mid)&&(j<=high)) { if(a[i]<=a[j]) { b[k++]=a[i++]; } else { b[k++]=a[j++]; } } while(i<=mid) { b[k++]=a[i++]; } while(j<=high) { b[k++]=a[j++]; } //把b中的值复制给a for(i=low;i<=high;++i) { a[i]=b[i]; } } void Sort(int a[],int low,int high) { int mid=(high+low)/2; if(low<high) { Sort(a,low,mid); Sort(a,mid+1,high); merge(a,low,mid,high); } } int main() { int a[]={3,1,4,5,2,7,9,8,10}; Sort(a,0,8); for(int i=0;i<9;i++) cout<<a[i]<<endl; return 0; }
（三）归并排序的应用：
（1）排序:
（2）求逆序数：逆序数就是对于一个数列a[] ,若存在i<j && a[i] > a[j] ，则说（i,j）是一对逆序。其实就是在归并排序中合并的时候，加一个计数器就完事了。 。
代码如下：
#include<iostream> using namespace std; int merge(int a[],int low,int mid,int high) { int b[100]; //合并排序结果先保存到b中 int i=low,j=mid+1,k=low; int count=0; //计数 int flag=0; while((i<=mid)&&(j<=high)) { if(a[i]<=a[j]) { b[k++]=a[i++]; } else { b[k++]=a[j++]; count+=(mid-i+1); } } while(i<=mid) { b[k++]=a[i++]; } while(j<=high) { b[k++]=a[j++]; } //把b中的值复制给a for(i=low;i<=high;++i) { a[i]=b[i]; } return count; } int InvertedNum(int a[],int low,int high) { int num1,num2,num3; int mid=(high+low)/2; int i=low,j=mid+1; if(low>=high)return 0; num1=InvertedNum(a,low,mid); num2=InvertedNum(a,mid+1,high); num3=merge(a,low,mid,high); return (num1+num2+num3); } int main() { int a[]={3,1,4,5,7,6,2}; cout<<InvertedNum(a,0,6)<<endl; return 0; }
函数学习：
qsort
语法:
| #include <stdlib.h> void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) ); |
功能： 对buf 指向的数据(包含num 项,每项的大小为size)进行快速排序。如果函数compare 的第一个参数小于第二个参数，返回负值；如果等于返回零值；如果大于返回正值。函数对buf 指向的数据按升序排序。
intcompare(constvoid*a,constvoid*b) { return*((int*)a)-*((int*)b); } qsort(array,num,sizeof(int),compare);
memset
语法:
#include <string.h> void *memset( void *buffer, int ch, size_t count ); |
功能: 函数拷贝ch 到buffer 从头开始的count 个字符里, 并返回buffer指针。 memset() 可以应用在将一段内存初始化为某个值。例如：
memset( the_array, '\0', sizeof(the_array) );
这是将一个数组的所以分量设置成零的很便捷的方法。
memcpy
语法:
#include <string.h>
void *memcpy( void *to, const void *from, size_t count ); |
功能：函数从from中复制count 个字符到to中，并返回to指针。 如果to 和 from 重叠，则函数行为不确定。