FunctionGHW

立志成为真正程序员的码农,伪全栈,目前主要写C#

基数排序(Radix Sort)是 非比较排序算法,其时间复杂度是线性的, 即\(O(n)\)。刚刚接触这个算法的时候,本以为该算法只适合输入时非负整数的情况, 不过最近在整理以前写的排序算法的Demo时,偶然想到该算法应该也可以用于字符串的排序。 根据算法的特点,直观感觉是:待排序字符串应该都是等长的。不过, 只要稍加改造,该算法也可以用于不等长字符串排序。

继续阅读

希尔排序(Shell Sort)算法学习

希尔排序是对插入排序的改进。 如果把排序的过程看作消除序列中 逆序对 的过程,那么排序的最终结果就是序列中没有逆序对。 普通的插入排序每次交换相邻元素,一次交换只能消除一个逆序对; 希尔排序允许交换相距一定间隔的元素,一次交换可以消除多个逆序对,因此速度更快。

继续阅读

堆排序(Heap Sort)算法学习

堆排序可以看作选择排序的进化版。选择排序通过遍历来选出最大(最小)元素, 堆排序利用数据结构二叉堆更快的选出最大(最小)元素。堆排序有两个优势: 1.)最好、最坏和平均时间复杂度均为\(O(nlogn)\); 2.)可以原地进行,空间复杂度\(O(1)\)。

继续阅读

归并排序(Merge Sort)是分治法的一个典型应用,相对于冒泡排序、插入排序和选择排序,其性能上有所提升,同时也是基于比较的排序算法中最好的算法之一。

归并排序的步骤如下:

  1. (Divide):将待排序序列(原问题)分成两个规模大致相等的子序列(子问题)
  2. (Conquer):递归地排序两个子序列,当子序列规模足够小的时候直接完成排序
  3. (Combine):合并两个已序的子序列得到原序列的排序结果
此算法中分解问题的过程类似于二分,关键步骤在合并。当分解出的子序列只有一个元素时,视为已序序列。

 

继续阅读

今日无闲扯。难得发一篇新的,所以没有旧文链接。

正文

题目是这样的:如果已知二叉树的中序遍历序列和后序遍历序列, 能否构造出这个树并输出其先序序列?假设序列中不存在重复的值。

首先要知道,一棵二叉树的中序遍历序列中,其根节点分布在序列的"中间" ——在序列中,其任何左子树上的节点的位置都在根节点的左侧,任何右子树上的节点都在右侧, 因此找出中序序列中的根节点的位置就能确定其左子树和右子树的子(中序)序列。 而后序遍历的一个明显特点就是: 根节点始终在后序序列的末尾,即最右端的那个。 同一棵树(子树也是一棵树),不管中序后序,序列长度都是一样的。根据这些条件, 我们就能够得到一棵二叉树的根节点,以及左右两棵子树的中序序列和后续序列, 然后递归地找出左右子树的根节点。

对于叶子结点,把它看成是单节点的树,它的左右子树都是空树。

继续阅读

最近两个星期,用C语言写了几小段示例代码,外加几个算法题的实现, 无奈自身水平捉鸡,总是出错问题,尤其是有指针的地方,每次都要调试好大一会儿,当真是苦不堪言啊。 C语言确实是小巧而又强大,不过也是让人又爱又恨。水平低如我等目测是没办法在大学期间搞定它了。 为了生存,还是先学点C#,python之类的语言吧<^_^>。

正文

题目大概是这样的:
已知两个给定的整数数组,数组长度都是n, 记为x[n], y[n]。 两个数组已被排序(升序),求这2n个整数的中位数。

继续阅读