中山论坛建站模板,工厂招工信息,企业网站如何建设和推广,商贸公司网站建设极致发烧归并排序 归并排序#xff08;Merge Sort#xff09;是建立在归并操作上的一种有效#xff0c;稳定的排序算法#xff0c;该算法是采用分治法#xff08;Divide and Conquer#xff09;的一个非常典型的应用。将已有序的子序列合并#xff0c;得到完全有序的序列#x…归并排序 归并排序Merge Sort是建立在归并操作上的一种有效稳定的排序算法该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。
归并操作也叫归并算法指的是将两个顺序序列合并成一个顺序序列的方法。 如 设有数列{62021003013881} 初始状态6,202,100,301,38,8,1 第一次归并后{6,202},{100,301},{8,38},{1}比较次数3 第二次归并后{6,100,202,301}{1,8,38}比较次数4 第三次归并后{1,6,8,38,100,202,301},比较次数4 总的比较次数为34411 逆序数为14
#includeiostream
using namespace std;
void m_sort(int *a,int l,int mid,int r)
{int* temp new int[r-l1];//开辟新的数组用来存储两个有序数组合并后的结果int l_left l;int mid_left mid;int mid_right mid1;int r_right r;int k 0;//temp数组下标while (l_left mid_left mid_right r_right)//两有序数组合并 模板{if (a[l_left] a[mid_right]){temp[k] a[l_left];}else if(a[l_left]a[mid_right]){temp[k] a[mid_right];}}while (l_left mid_left){temp[k] a[l_left];}while (mid_right r_right){temp[k] a[mid_right];}for (int i l; ir; i)//需要将有序的数组temp重新赋值给a{a[i] temp[i-l];}
}
void merge(int* a, int l, int r)//分治
{if (l r){int mid (l r) / 2;//对半merge(a, l, mid);merge(a, mid1, r);m_sort(a, l,mid, r);}
}
void main()
{int a[10]{ 6,202,100,301,38,8,1 };merge(a, 0, 6);for (int i 0; i 7; i){cout a[i] ;}
}
