• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

归并排序c++代码及详细注释

原作者: [db:作者] 来自: [db:来源] 收藏 邀请
  1 #include <iostream>
  2 using namespace std;
  3 template <class T>
  4 void MSort(T a[], int left, int right)
  5 {
  6       if (left < right)
  7       {
  8             int center = (left + right) / 2;//取得中点
  9             //将原来序列分为两段
 10             MSort(a, left, center);
 11             MSort(a, center+1, right);
 12             //合并刚才分开的两段,得到原来序列的有序序列
 13             Merge(a, left, center, right, right-left+1);
 14       }
 15 }
 16 
 17 template <class T>
 18 void MergeSort(T a[], int n)
 19 {
 20     //调用递归归并排序函数
 21       MSort(a, 0, n-1);
 22 }
 23 template <class T>
 24 void Merge(T a[], int left, int center, int right, int n)
 25 {
 26       T *t = new T[n];//存放被排序的元素
 27       int i = left;
 28       int j = center + 1;
 29       int k = 0;
 30       //合并数组,用插入排序,如果左边大就插入左边的数,右边的计数器等待,与下一个左边的数比较;右边大就插入右边的数,左边的计数器等待,与下一个右边的数比较(这里指的插入是插入到新数组t[])
 31       while (i<=center && j<=right)
 32       {
 33             if (a[i] <= a[j])
 34                   t[k++] = a[i++];
 35             else
 36                   t[k++] = a[j++];
 37       }
 38       //上面的步骤在执行完后,左或右边都有可能剩余若干个元素,而另一边的元素肯定已全部复制到新数组,这时需要特殊对待剩下的元素
 39       if (i == center+1)
 40       {
 41             while (j <= right)
 42                   t[k++] = a[j++];
 43       }
 44       else
 45       {
 46             while (i <= center)
 47                   t[k++] = a[i++];
 48       }
 49       //把t[]的元素复制回a[]中left到right段
 50       for (i=left,k=0; i<=right; i++,k++)
 51             a[i] = t[k];
 52       //释放内存
 53       delete []t;
 54 }
 55 int main()
 56 {
 57     int intArray[5] = { 5 , 6 , 2 , 5 , 9 };
 58     MergeSort(intArray,5);
 59     for(int i = 0; i < 5; i++)
 60         cout << intArray[i] << endl;
 61 }
 62 -------------------------------------------------------------------------------------
 63 //非递归实现
 64 #include <iostream>
 65 using namespace std;
 66 
 67 template <class T>
 68 void MergeSort(T a[], int n)
 69 {
 70     /*非递归形式:
 71 算法介绍:先介绍三个变量beforeLen,afterLen和i的作用:
 72 int beforeLen; //合并前序列的长度
 73 int afterLen;//合并后序列的长度,合并后序列的长度是合并前的两倍
 74 int i = 0;//开始合并时第一个序列的起始位置下标,每次都是从0开始
 75 i,i+beforeLen-1,i+afterLen-1定义被合并的两个序列的边界。
 76 算法的工作过程如下:
 77 开始时,beforeLen被置为1,i被置为0。外部for循环的循环体每执行一次,都使beforeLen和afterLen加倍。内部的while循环执行序列的合并工作,他的循环体每执行一次,i都向前移动afterLen个位置。当n不是afterLen的倍数时,如果被合并序列的起始位置i,加上合并后序列的长度afterLen,超过输入数组的边界n,就结束内部循环;此时如果被合并序列的起始位置i,加上合并前序列的长度 beforeLen,小于输入数组的边界n,还需要执行一次合并工作,把最后长度不足afterLen,但超过beforeLen的序列合并起来。这个工作由算法的语句Merge(a, i, i+beforeLen-1, n-1, n);完成。*/
 78      /*  int beforeLen; //合并前序列的长度
 79       int afterLen = 1;//合并后序列的长度
 80 
 81      for (beforeLen=1; afterLen<n; beforeLen=afterLen)
 82       {
 83             int i = 0;//开始合并时第一个序列的起始位置下标,每次都是从0开始
 84             afterLen = 2 * beforeLen; //合并后序列的长度是合并前的两倍
 85 
 86             while (i+afterLen < n)
 87             {
 88                   Merge(a, i, i+beforeLen-1, i+afterLen-1, afterLen);
 89                   i += afterLen;
 90             }
 91 
 92             if (i+beforeLen < n)
 93                   Merge(a, i, i+beforeLen-1, n-1, n);
 94       }*/
 95       //我自己写的主函数代码
 96       int lengthTocombine = 1;//定义将要被合并的长度,开始时为1;
 97       int begin;
 98       for(lengthTocombine = 1;lengthTocombine < n; lengthTocombine *= 2)
 99       {
100           begin = 0;//开始合并时第一个序列的起始位置下标,每次都是从0开始
101           while(begin + 2*lengthTocombine < n )
102           {
103               Merge(a, begin, (2*begin+2*lengthTocombine-1)/2, begin+2*lengthTocombine-1, 2*lengthTocombine);
104               begin += 2*lengthTocombine;
105           }
106           //剩下长度小于lengthTocombine序列
107           if (begin + lengthTocombine < n)
108               Merge(a, begin, begin+lengthTocombine-1, n-1, n);
109       }
110 }
111 template <class T>
112 void Merge(T a[], int left, int center, int right, int n)
113 {
114       T *t = new T[n];//存放被排序的元素
115       int i = left;
116       int j = center + 1;
117       int k = 0;
118       //合并数组,用插入排序,如果左边大就插入左边的数,右边的计数器等待,与下一个左边的数比较;右边大就插入右边的数,左边的计数器等待,与下一个右边的数比较(这里指的插入是插入到新数组t[])
119       while (i<=center && j<=right)
120       {
121             if (a[i] <= a[j])
122                   t[k++] = a[i++];
123             else
124                   t[k++] = a[j++];
125       }
126       //上面的步骤在执行完后,左或右边都有可能剩余若干个元素,而另一边的元素肯定已全部复制到新数组,这时需要特殊对待剩下的元素
127       if (i == center+1)
128       {
129             while (j <= right)
130                   t[k++] = a[j++];
131       }
132       else
133       {
134             while (i <= center)
135                   t[k++] = a[i++];
136       }
137       //把t[]的元素复制回a[]中left到right段
138       for (i=left,k=0; i<=right; i++,k++)
139             a[i] = t[k];
140       //释放内存
141       delete []t;
142 }
143 
144 int main()
145 {
146     int intArray[5] = { 23 , 8 , 1 , 6 , 10};
147     MergeSort(intArray,5);//执行排序
148     for( int i = 0; i < 5; i++)
149         cout << intArray[i] << endl;
150 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
(一)s3c2440地址分配讲解(很难很纠结)发布时间:2022-07-14
下一篇:
linux以下C利用openssl的AES库加密,解密发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap