ITeye博客

yyang900427的博客

yyang900427 · 共 12 篇文章

快速排序

/** * 快速排序使用分治法策略来把一个串行分为两个子串行,步骤为: * 从数列中挑出一个元素,称为 "基准",重新排序数列,所有元素比基准值小的 * 摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一 * 边)。这个分区退出之后,该基准就处于数列的中间位置。这个称为分区操作。 * 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排 * 序。递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。 * 排序n个项目要O(nlog(n))次比较,在最坏状况下则需要O(n ^ 2)次比较! */ #include <stdio.h> …

2013-05-02 11:04 · 排序算法 · 评论(0)

判断二叉树是否平衡

/** * 题目:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树 * 中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树 */ int is_balanced(struct node * root_node, int * depth) { if(root_node == NULL) { *depth = 0; return 1; } int left, right; if(is_balanced(root_node->left_node, &left) && \ is_balanced(root_node->right_node, &right)) { int …

2013-04-28 10:54 · 每日算法练习 · 评论(0)

字符串的组合

/** * 题目:输入一个字符串,输出该字符串中字符的所有组合。举个例子,如果输入 * abc,它的组合有a、b、c、ab、ac、bc、abc。 */ public class Launch { public static void main(String ...args) { combination("abcd"); } public static void combination(String str) { int strLength; strLength = str.length(); tmpArray = new char[strlength]; for(int len = 1; l…

2013-04-28 10:06 · 每日算法练习 · 评论(0)

字符串的排列

/** * 题目:输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则 * 输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。 */ #include <stdio.h> static void swap(char array[], int i, int j) { char tmp = array[i]; array[i] = array[j]; array[j] = tmp; } static int contains(char array[], int m, int n) { for(int i = m; i < n; ++i…

2013-04-27 10:24 · 算法分析 · 评论(0)

判断一字符串是否对称,如:abccba

# 1.判断一字符串是不是对称的,如:abccba def is_symmetrical(str): length = len(str) for index in range(length / 2): if str[index] == str[length - index - 1]: pass else: return False return True if __name__ == "__main__": print is_symmertrical("abcdcba"), print is_symmertrical("abccaa"), 运行结果: True False # 2.用递归的方…

2013-04-26 12:38 · 每日算法练习 · 评论(0)

选择排序

/** * 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置(末尾位置) * 然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末 * 尾(首处)。以此类推,直到所有元素均排序完毕。选择排序的主要优点与数据移动 * 有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换 * 一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排 * 序总共进行至多n-1次交换,选择排序最优和最差时间复杂度均为O(n ^ 2) */ #include <stdio.h> void select_sort(int array[], int …

2013-04-26 11:25 · 排序算法 · 评论(0)

冒泡排序

/** * 依次比较相邻的两个个数,将小数放在前面,大数放在后面。即在第一 * 趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2 * 个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两 * 个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最 * 后。若一趟下来始终满足小数在前,则排序结束,否则记录不满足小数在 * 前的数组最大位置,置为待排数组长度,然后重复上述过程,直到结束,冒 * 泡排序的时间杂度为O(n) ~ O(n ^2) */ #include <stdio.h> void bubble_sort(int array[], int n) { …

2013-04-25 13:13 · 排序算法 · 评论(0)

Treap(树堆)

/** * 如果一个二叉搜索树节点插入的顺序是随机的,这样我们得到的二叉搜索树大多 * 数情况下是平衡的,即使存在一些极端情况,但是这种情况发生的概率很小, * 所以我们可以这样建立一棵二叉搜索树,而不必要像AVL那样旋转,可以证明随 * 机顺序建立的二叉搜索树在期望高度是O(log n),但是某些时候我们并不能得 * 知所有的待插入节点,打乱以后再插入。所以我们需要一种规则来实现这种想法, * 并且不必要所有节点。也就是说节点是顺序输入的,我们实现这一点可以用Treap。 * Treap=Tree+Heap。Treap本身是一棵二叉搜索树,它的左子树和右子树 * 也分别是一个Treap,和…

2013-04-25 10:13 · 数据结构 · 评论(0)

希尔排序

/** * 希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长 * 最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插 * 入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些! * 希尔排序时间复杂度为O(nlog(n)) ~ O(n ^ 2) */ #include <stdio.h> void shell_sort(int array[], int n) { // increment为步长 int tmp, i, j, increment; for(increment = n / 2; increment > 0;…

2013-04-23 16:54 · 排序算法 · 评论(0)

插入排序

/** * 插入排序有一个已经有序的数据序列,要求在这个已经排好的数据 * 序列中插入一个数,但要求插入后此数据序列仍然有序,这就是插入 * 排序,插入排序算法时间复杂度为O(n) ~ O(n ^ 2),平均为O(n ^ 2) */ #include <stdio.h> void insert_sort(int array[], int n) { int tmp, i, j; for(i = 1; i < n; ++i) { // 记录当前待插入元素 tmp = array[i]; for(j = i; j > 0 && tmp < array[j - 1]; --j) { array[j]…

2013-04-23 09:40 · 排序算法 · 评论(0)

归并排序

/** * 归并(Merge)排序法是将两个有序表合并成一个新的有序表,即把待排序 * 序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为 * 整体有序列。算法时间复杂度为O(nlog(n)),空间复杂度为O(n)。 */ #include <stdio.h> #include <stdlib.h> #include <assert.h> void sort(int array[], int tmp_array[], int low, int mid, int high) { int lpos = low, rpos = mid + 1, index = low; // 开始…

2013-04-22 13:04 · 排序算法 · 评论(0)

折半查找法

/** * 折半查找又称二分查找,算法复杂度为O(log(n)),但缺点是要求 * 待查表为有序表,此算法充分利用了数组的有序性,采用分治策略 * 找出待查元素在数组中的位置,若数组中不存在该元素,则返回-1 */ #include <stdio.h> int binary_search(int array[], int n, int data) { int low = 0, high = n - 1, mid; while(high >= low) { mid = (low + high) / 2; if(array[mid] == data) return mid; else if(ar…

2013-04-22 11:03 · 算法分析 · 评论(0)