标签 原创 下的文章

算法(algorithms)基础之:归并排序的递归实现

  1. 归并排序(merge-sort)是建立在归并操作上的一种有效的排序算法,该算法采用分治法(divide and conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。
  2. 归并排序过程:比较a[i]和a[j]的大小,将第一个有序表中的a[i]复制到r[k]中,并令i和k分别加1;否则讲第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的元素,从此得到一个新的有序表。
  3. 通常来讲,我们采用递归方式实现完整的归并排序,先把原始数组a中下标[start,end]用中点mid二分,接着把左边子区间A[start,mid]排序,再把右边子区间B[mid+1, end]排序,最后再用一次归并操作把A\B合并成最终有序表C[start,end]。

- 阅读剩余部分 -

算法(algorithms)基础之:插入排序

插入排序,对于少量的元素的数据,它是一个有效的算法。它的工作方式就像许多人排序一副扑克牌。开始时,我们的左手为空并且桌子上的牌面向下。然后,我们每次从桌上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右往左将它与已在手中的每张牌进行比较,拿在左手上的牌总是排序好的。如图:

- 阅读剩余部分 -