文章列表
/**
* 快速排序使用分治法策略来把一个串行分为两个子串行,步骤为:
* 从数列中挑出一个元素,称为 "基准",重新排序数列,所有元素比基准值小的
* 摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一
* 边)。这个分区退出之后,该基准就处于数列的中间位置。这个称为分区操作。
* 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排
* 序。递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。
* 排序n个项目要O(nlog(n))次比较,在最坏状况下则需要O(n ^ 2)次比 ...
/**
* 题目:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树
* 中任意结点的左右子树的深度相差不超过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, ...
/**
* 题目:输入一个字符串,输出该字符串中字符的所有组合。举个例子,如果输入
* 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();
t ...
/**
* 题目:输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串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 ...
# 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"),
...
/**
* 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置(末尾位置)
* 然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末
* 尾(首处)。以此类推,直到所有元素均排序完毕。选择排序的主要优点与数据移动
* 有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换
* 一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排
* 序总共进行至多n-1次交换,选择排序最优和最差时间复杂度均为O(n ^ 2)
*/
#include <stdio.h>
void s ...
/**
* 依次比较相邻的两个个数,将小数放在前面,大数放在后面。即在第一
* 趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2
* 个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两
* 个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最
* 后。若一趟下来始终满足小数在前,则排序结束,否则记录不满足小数在
* 前的数组最大位置,置为待排数组长度,然后重复上述过程,直到结束,冒
* 泡排序的时间杂度为O(n) ~ O(n ^2)
*/
#include <stdio.h>
void bubbl ...
/**
* 如果一个二叉搜索树节点插入的顺序是随机的,这样我们得到的二叉搜索树大多
* 数情况下是平衡的,即使存在一些极端情况,但是这种情况发生的概率很小,
* 所以我们可以这样建立一棵二叉搜索树,而不必要像AVL那样旋转,可以证明随
* 机顺序建立的二叉搜索树在期望高度是O(log n),但是某些时候我们并不能得
* 知所有的待插入节点,打乱以后再插入。所以我们需要一种规则来实现这种想法,
* 并且不必要所有节点。也就是说节点是顺序输入的,我们实现这一点可以用Treap。
* Treap=Tree+Heap。Treap本身是一棵二叉搜索树,它的左子树和右子树 ...
/**
* 希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长
* 最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插
* 入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比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;
...
/**
* 插入排序有一个已经有序的数据序列,要求在这个已经排好的数据
* 序列中插入一个数,但要求插入后此数据序列仍然有序,这就是插入
* 排序,插入排序算法时间复杂度为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 = ar ...
/**
* 归并(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)
...