"chaos"的算法--之归并排序 【 声明：版权所有，欢迎转载。 联系信箱：yiluohuanghun@gmail.com】
归并排序（Merge sort）的基本思想是合并两个有序表，设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。
归并排序的时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)，空间复杂度为O(N)，它是一种稳定的排序方法。归并排序在最坏的情况下都是O(NlogN)的时间复杂度，缺点是Merge的时候要有O(N)的额外的空间.
整体来说，对于归并排序可以运用分而治之方法来解决排序问题，该问题是将n 个元素排成非递减顺序。分而治之方法通常用以下的步骤来进行排序算法：若n 为1，算法终止；否则，将这一元素集合分割成两个或更多个子集合，对每一个子集合分别排序，然后将排好序的子集合归并为一个集合。
假设仅将n 个元素的集合分成两个子集合。现在需要确定如何进行子集合的划分。一种可能性就是把前面n- 1个元素放到第一个子集中（称为A），最后一个元素放到第二个子集里（称为B）。按照这种方式对A递归地进行排序。由于B仅含一个元素，所以它已经排序完毕，在A排完序后，只需要用程序中的函数insert将A和B合并起来。把这种排序算法与InsertionSort进行比较，可以发现这种排序算法实际上就是插入排序的递归算法。该算法的复杂性为O(n2)。把n个元素划分成两个子集合的另一种方法是将含有最大值的元素放入B，剩下的放入A中。然后A被递归排序。为了合并排序后的A和B，只需要将B添加到A中即可。假如用函数M a x来找出最大元素，这种排序算法实际上就是SelectionSort的递归算法。
分治思想：
将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解建立原问题的解，归并排序完全遵循分治模式：
分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列
解决：使用归并排序递归地排序两个子序列
合并：合并两个已排序的子序列以产生已排序的答案
归并排序算法：
归并排序算法的关键操作是"合并"步骤中两个已排序序列的合并。我们通过调用一个辅助过程merge(A, p, q, r, T)来完成合并，其中A是一个数组，p，q，r是数组下标，满足p <= q < r， T是一个辅助数组空间。该过程假设子数组A[p..q]和A[q+1..r]都已排好序。它合并这两个子数组形成单一的已排好的子数组并代替当前的子数组A[p..r]n
过程merge需要O(n)的时间，其中n = r p + 1是待合并元素的总数。
//将有二个有序数列a[first...mid]和a[mid...last]合并。 void mergearray(int a[], int first, int mid, int last, int temp[]) int i = first, j = mid + 1; int m = mid, n = last; //逐个进行排序，并将排序结果保存在对应的临时数组中 while (i <= m && j <= n) if (a <= a[j]) temp[k++] = a; temp[k++] = a[j++]; //后半部分已遍历完，对前半部分剩下的直接拷贝 temp[k++] = a; //前半部分已遍历完，对后半部分剩下的直接拷贝 temp[k++] = a[j++]; //将存放在临时数组中的数据拷贝到原数组中 for (i = 0; i < k; i++) a[first + i] = temp; |
现在，我们可以过程merge作为归并排序算法中的一个子程序来用。下面的过程mereg_sort(A, p, r)排序子数组A[p...r]中的元素。若p >= r,则该子数组最多有一个元素，所以已经排好序。否则，分解步骤简单地计算一个下标q，将A[p...r]分成两个子数组A[p...q]和A[q...r],前者包含n / 2个元素，后者包含n / 2个元素。
void mergesort(int a[], int first, int last, int temp[]) if (first < last) int mid = (first + last) / 2; mergesort(a, first, mid, temp); //对前半部分进行排序 mergesort(a, mid + 1, last, temp); //对后半部分进行排序 mergearray(a, first, mid, last, temp); //合并前后两部分 int MergeSort(int a[], int n) int *p = new int[n]; mergesort(a, 0, n - 1, p); |
当然了，每到这个时候我都会说一样的话，测试程序一定要写，在程序可控范围内一定要将测试程序补上。
| dede后台空白或者登录以后空白,点注销以后也是空白的解决方式 阅读原文» 最近一段时间一直没有写博文，一直都在找工作，刚找到工作，接手以后第一件事儿就是要做一个dede的移站，都是linux系统，网站转移完毕以后，却发现输入以后地址是空白的，必须在后面加login.php才可以登录，而且点击注销也是空白页。百度了很多也没有找到，现在把方法总结一下，公布给大家。 解决方式一: 原因:include/common.inc.php,data/common.inc.php被修改，保存的时候有BOM头，一般是在utf8的编码下才存在这个问题。 方法:ftp下载下来，然后用notepad++或者dw打开，选择UTF8无BOM头保存试试 解决方式二 原因:这个一般是因为环境是PHP5.4的原因，dede中的session_register被移除了 方法: 找include/userlogin.class.php里面的keepuser()函数， 把@session_register 全部改写， 虽然不知道这个@是什么意思 把@session_register($this->keepUserIDTag); 注释掉，然后改为 if (!isset($_SESSION[$this->keepUserIDTag])) 全部有6个。 如下： if (!isset($_SESSION[$this->keepUserIDTag])) //@session_register($this->keepUserIDTag); $_SESSION[$this->keepUserIDTag] = $this->userID; if (!isset($_SESSION[$this->keepUserTypeTag])) //@session_register($this->keepUserTypeTag); $_SESSION[$this->keepUserTypeTag] = $this->userType; if (!isset($_SESSION[$this->keepUserChannelTag])) //@session_register($this->keepUserChannelTag); $_SESSION[$this->keepUserChannelTag] = $this->userChannel; if (!isset($_SESSION[$this->keepUserNameTag])) //@session_register($this->keepUserNameTag); $_SESSION[$this->keepUserNameTag] = $this->userName; if (!isset($_SESSION[$this->keepUserPurviewTag])) //@session_register($this->keepUserPurviewTag); $_SESSION[$this->keepUserPurviewTag] = $this->userPurview; if (!isset($_SESSION[$this->keepAdminStyleTag])) //@session_register($this->keepAdminStyleTag); $_SESSION[$this->keepAdminStyleTag] = $adminstyle; 然后就可以登入后台了。 解决方式三: 找到:include/common.inc.php文件，打开，查找程序代码： //error_reporting(E_ALL); 解决方法四:在include/common.inc.php最开始添加ob_start()试试，如果不行的话就看php.ini中是否开启了output_buffering是否为on如果不是则试试改成on试试，记得重启apache(我就是用这种方法解决的) 解决方法五：某些版本的dede中可能会存在此问题，看install中的install_lock.txt是否存在，不存在的话新建试试。 时间很短，也没时间去看源代码，百度了很多都很不靠谱，误导了很多朋友，这次专门总结了一下。呵呵，希望大家可以加群252799167一起交流讨论。 本文出自 "雷" 博客，请务必保留此出处http://a3147972.blog.51cto.com/2366547/1272057
订阅：
博文评论 (Atom)
|
没有评论:
发表评论