目 录
一、归并排序
二、基本算法
1、分离
2、合并
3、图片讲解
三、C++代码实现
1、分离函数
2、合并函数
3、C++完整代码
四、总结
一、归并排序
归并排序(Merge Sort)是建立在归并操作上的一种既有效又稳定的排序算法,该算法是采用
分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的
序列。即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二
路归并。
二、基本算法
1、分离
将已有数列不断分离成两段长度基本相同(当已有数列长度是奇数时,则一半长一半短),直到分离成长度为 1 的 n 个数列(其实就是 n 个数)。
2、合并
将数列两两合并,每次合并时进行比较和排序,直到完成排序。
3、图片讲解
将一个无序数列排好序:
先是分离成长度为 1 的 n 个数列,然后再合并,合并过程中两个红色区域代表两两比较,然后将小的放在前面。
三、C++代码实现
1、分离函数
void mergesort(int x,int y) //分离,x 和 y 分别代表要分离数列的开头和结尾
{
if (x>=y) return; //如果开头 ≥ 结尾,那么就说明数列分完了,就要返回
int mid=(x+y)/2; //将中间数求出来,用中间数把数列分成两段
mergesort(x,mid);
mergesort(mid+1,y); //递归,继续分离
merge(x,mid,y); //分离玩之后就合并
}
2、合并函数
void merge(int low,int mid,int high) //归并
//low 和 mid 分别是要合并的第一个数列的开头和结尾,mid+1 和 high 分别是第二个数列的开头和结尾
{
int i=low,j=mid+1,k=low;
//i、j 分别标记第一和第二个数列的当前位置,k 是标记当前要放到整体的哪一个位置
while (i<=mid && j<=high) //如果两个数列的数都没放完,循环
{
if (a[i] b[k++]=a[i++]; else b[k++]=a[j++]; //将a[i] 和 a[j] 中小的那个放入 b[k],然后将相应的标记变量增加 } // b[k++]=a[i++] 和 b[k++]=a[j++] 是先赋值,再增加 while (i<=mid) b[k++]=a[i++]; while (j<=high) b[k++]=a[j++]; //当有一个数列放完了,就将另一个数列剩下的数按顺序放好 for (int i=low;i<=high;i++) a[i]=b[i]; //将 b 数组里的东西放入 a 数组,因为 b 数组还可能要继续使用 } 3、C++完整代码 #include #include #include using namespace std; int n,a[12000],b[12000]; void merge(int low,int mid,int high) { int i=low,j=mid+1,k=low; while (i<=mid && j<=high) { if (a[i] b[k++]=a[i++]; else b[k++]=a[j++]; } while (i<=mid) b[k++]=a[i++]; while (j<=high) b[k++]=a[j++]; for (int i=low;i<=high;i++) a[i]=b[i]; } void mergesort(int x,int y) { if (x>=y) return; int mid=(x+y)/2; mergesort(x,mid); mergesort(mid+1,y); merge(x,mid,y); } int main() { cin >>n; for (int i=1;i<=n;i++) cin >>a[i]; mergesort(1,n); //调用函数 for (int i=1;i<=n;i++)
发表评论