标签归档:算法实现

单链表快速排序算法

快速排序的算法思想是:确定一个枢轴元素,通过一趟排序将待排关键字分成两个部分,其中一部分元素均比枢轴元素小,另一部分元素均比枢轴元素大,这样的一趟排序称为快速排序的一次划分。再对两个部分分别再递归进行划分操作,最后获得的序列就是排好序的关键字序列。可见,快速排序的性能与枢轴元素的选取有关,快排的时间复杂度在最好、最坏、平均的情况下分别为:O(nlog2n)、O(n2)和O(nlog2n),空间复杂度在最好、最坏、平均情况下分别为:O(log2n)、O(n)和O(log2n),快排的C++实现和效率分析见『六种基本内部排序算法的C++实现』『六种基本内部排序算法效率分析』

上述快排算法的实现中采用的存储结构是数组,采用数组有一个好处,就是待排元素可以随机存取。而以单链表方式存储的待排序列就无法随机存取元素了,其实根据快排思想,稍作改动,对单链表的快速排序算法也能实现。

因为快排最核心的思想就是划分,确定一个枢轴元素(pivot),每一趟划分的目的就是把待排序列分为两部分,前一部分比枢轴小(序列A),后一部分比枢轴大(序列B)。经过一趟划分之后序列变为:{A} pivot {B}。以下是具体步骤:
1、确定每一次划分的枢轴元素为当前待排序列的头节点。
2、设置Slow和Fast两个游标,Slow指向序列A中的最后一个元素,初始化为枢轴本身(待排序列头节点)。让Fast遍历一遍待排序列,当所指元素比枢轴小时,将Slow往前游一格,交换Slow和Fast所指元素的值,这样仍能保证Slow指向的元素是序列A中的最后一个元素。
3、交换Slow所指元素和枢轴元素的值。
4、对序列A和B重复步骤1~4。

下面是单链表快速排序算法的Java实现:
1、单链表节点的定义。

1
2
3
4
5
/* 单链表节点 */
class Element {
    public int     data;
    public Element next;
}

2、单链表的快排算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * @param ListHead 待排序列的头节点
 * @param ListEnd 待排序列的尾节点
 */
public static void qsort(Element ListHead, Element ListEnd) {
    if (ListHead == null || ListEnd == null)
        return;
    if (ListHead == ListEnd) {
        return;
    }
    //Slow游标,指向序列A的最末尾元素。
    Element Slow = ListHead;
    //Fast游标,用于遍历整个待排序列。
    Element Fast = ListHead.next;
    //TempEnd游标,总是指向Slow游标的前驱节点,递归调用时需要。
    Element TempEnd = ListHead;
    int temp;
    while (Fast != null) {
        //当前节点的值比枢轴小,进行交换。
        if (Fast.data < ListHead.data) {
            //TempEnd游标总是指向Slow的前驱。
            TempEnd = Slow;
            Slow = Slow.next;
 
            //交换Slow和Fast游标所指的元素的值
            temp = Slow.data;
            Slow.data = Fast.data;
            Fast.data = temp;
        }
        Fast = Fast.next;
    }
 
    //交换Slow游标所指的元素和枢轴元素的值,使序列成为{A} povit {B}形式
    temp = ListHead.data;
    ListHead.data = Slow.data;
    Slow.data = temp;
 
    //递归调用
    qsort(ListHead, TempEnd);
    qsort(Slow.next, ListEnd);
}

--EOF--

Fibonacci数列的O(log2n)解法

Fibonacci数列(斐波那契数列)用递归实现最符合其定义要求,但是计算机实现起来的时间复杂度为O(2n)。改进一点的做法是通过一个O(n)的空间换取时间复杂度为O(n)的非递归计算方法。更好一些的方法就是通过Fibonacci数列的递归公式构建出一个矩阵方程,通过对矩阵方程的代数运算,可以在O(log2n)时间复杂度内得到任意第n个Fibonacci数列中数字。

由Fibonacci数列公式F(n+1) = F(n) + F(n-1),我们可以构建出下列的矩阵方程:

由此可以推导出:

因为F(0)=1,F(1)=1是已知的,所以只要求出矩阵(1, 1, 1, 0)n的值,那么F(n)值也就知道了。

对于两个数的乘方,我们可以用分而治之在O(log2n)的时间复杂度内求得,将它运用在矩阵计算中也是一样的。如下:

程序中只需先定义两个矩阵的乘法,然后便可以递归求得Mn的值。

1、首先定义矩阵类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * | m00 m01 |
 * | m10 m11 |
 */
class Matrix {
    public long m00;
    public long m01;
    public long m10;
    public long m11;
 
    public Matrix(long m00, long m01, long m10, long m11) {
        this.m00 = m00;
        this.m01 = m01;
        this.m10 = m10;
        this.m11 = m11;
    }
}

2、定义矩阵乘法

1
2
3
4
5
6
7
public static Matrix multiplyMatrix(Matrix m1, Matrix m2) {
    return new Matrix(
        m1.m00 * m2.m00 + m1.m01 * m2.m10, 
        m1.m00 * m2.m01 + m1.m01 * m2.m11,
        m1.m10 * m2.m00 + m1.m11 * m2.m10, 
        m1.m10 * m2.m01 + m1.m11 * m2.m11);
}

3、对矩阵M进行n次幂运算

1
2
3
4
5
6
7
8
9
10
11
12
13
public static Matrix calculate(int n) {
    if (n == 1) {
        return new Matrix(1, 1, 1, 0);
    }
    if (n % 2 == 0) { //n为偶数
        Matrix m = calculate(n / 2);
        return multiplyMatrix(m, m);
    } else { //n为奇数
        Matrix m = calculate((n - 1) / 2);
        m = multiplyMatrix(m, m);
        return multiplyMatrix(m, new Matrix(1, 1, 1, 0));
    }
}

这样,求解第n个Fabonacci数列中数字的问题就被转化成为矩阵(1, 1, 1, 0)的n次幂运算,时间复杂度降为O(log2n)。

完整代码参见这里

Reference:
[1] Fibonacci Sequence. Wikipedia. 2011-10-21 accessed.

--EOF--

在一个有序数组中查找给定数

题目要求为在一个有序数组中查找一个给定值的数,这个数组是升序还是降序未知。这样就比普通的二分查找要多一步骤,用于判定该数组是升序还是降序,其余就跟普通二分查找一样了。

详见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/***
 * args:	IN num[]: 有序数组
 *		IN start: 起始下标
 *		IN end: 终点下标
 *		IN value: 待查数值
 *		OUT pos: 待查数值下标
 * return:	true:命中 false:未命中
 */
bool binary_search(int num[], int start, int end, int value, int& pos)
{
    int order = 1; //顺序标记,默认升序
 
    if (num[start] > num[end-1])
    {
        order = 0; //逆序
    }
 
    while (start <= end)
    {
        int mid = (start+end)/2;
 
        if(num[mid] == value){
            pos = mid;
            return true;
        }else{
            if (order == 1) //如果是升序数组
            {
                if (value < num[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } 
            else //如果是降序数组
            {
                if (value < num[mid]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
    }
 
    return false;
}

--EOF--

二叉树根据前序中序得到后序序列

根据二叉树的前序和中序序列,能求得它的后序序列,同样道理,根据中序和后序序列,能求得它的前序序列。但是根据前序和后序序列,无法求得它的中序序列,因为单凭前序和后序序列无法唯一确定一颗二叉树。

以下是根据二叉树的前序和中序序列求其后序序列的算法思想和实现。
关于二叉树的题,最先想到的总是递归。根据二叉树的前序、中序和后序定义,可以找出规律:
1、前序序列的第一个元素肯定是根节点。
2、中序序列中,根节点左边的序列都属于左子树,根节点右边的序列都属于右子树。如此一来,中序序列都划分成三个部分:左子树节点集合、根节点、右子树节点集合。
3、根据中序的三个部分,前序的序列也可以划分成:根节点、左子树节点集合、右子树节点集合。
4、分别对前序和中序序列中的左子树节点集合和右子树节点集合重复步骤1~3。
5、根据后序定义,当左右子树处理完毕后,最后才输出根节点。

对于某前序序列(1245673),中序序列(4265713),根据以上步骤,首先,用根节点1将中序序列分成三个部分(42657-1-3),同时,这样一来,前序序列也可以分成三部分了(1-24567-3),然后分别对子序列(24567)和(3)重复以上步骤,最后输出根节点1。over~~

C++程序实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 *根据二叉树的前序、中序序列得到其后序遍历序列
 *preorder:前序序列 inorder:中序序列 len:序列长度
 */
void process(char* preorder, char* inorder, int len)
{
    int i;
    //当前层次为不再包含元素,退出递归
    if (len <= 0) {
        return;
    }
    //得到当前层次root节点(前序0号元素)在中序的位置
    for(i=0; inorder[i]!=preorder[0]; i++); 
    //递归处理左子树
    process(preorder+1, inorder, i);
    //递归处理右子树
    process(preorder+i+1, inorder+i+1, len-i-1);
    //打印根节点root。
    cout << preorder[0];
}

根据中序和后序序列求前序序列也一样道理,C++实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 *根据二叉树的中序、后序序列得到其前序遍历序列
 *inorder:中序序列 postorder:后序序列 len:序列长度
 */
void process2(char*inorder, char* postorder, int len)
{
    int i;
    if(len <= 0){
        return;
    }
 
    for (i = 0; inorder[i]!=postorder[len-1]; i++);
    cout << postorder[len-1];
    process2(inorder, postorder, i);
    process2(inorder+i+1, postorder+i, len-i-1);
}

测试程序见附件: 源代码

--EOF--

二叉树遍历的非递归实现

二叉树的定义是递归的,因此要遍历二叉树,用递归方法最为简便和直观,但是,二叉树的遍历也可以用非递归方法实现。

 一、非递归前序遍历二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 前序遍历二叉树  非递归法
 * @param root
 */
public static void preOrderNoRecusive(BTree root) {
    Stack<BTree> s = new Stack<BTree>();
    while (root != null || !s.empty()) {
        while (root != null) {
            System.out.print(root.getValue());
            s.push(root);
            root = root.getlChild();
        }
        if (!s.empty()) {
            root = s.pop();
            root = root.getrChild();
        }
    }
}
 二、非递归中序遍历二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 中序遍历二叉树  非递归法
 * @param root
 */
public static void inOrderNoRecusive(BTree root) {
    Stack<BTree> s = new Stack<BTree>();
    while (root != null || !s.empty()) {
        while (root != null) {
            s.push(root);
            root = root.getlChild();
        }
        if (!s.empty()) {
            root = s.pop();
            System.out.print(root.getValue());
            root = root.getrChild();
        }
    }
}
 三、非递归后序遍历二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 后序遍历二叉树  非递归法
 * @param root
 */
public static void postOrderNoRecusive(BTree root) {
    Stack<BTree> s = new Stack<BTree>();
    while (root != null || !s.empty()) {
        while (root != null) {
            s.push(root);
            root = root.getlChild();
        }
        if (!s.empty()) {
            root = s.peek();
            if (root.getTag() == false) {
                root.setTag(true);
                root = root.getrChild();
            } else {
                System.out.print(root.getValue());
                s.pop();
                root = null;
            }
        }
    }
}

非递归的后序遍历与前两者有些不同,它需要在二叉树的定义中加入一个tag标签,初始为false,只有当一个节点的右孩子已经遍历过之后,才将它置为true,表示下次可以访问它并输出值了。

附件提供的源代码是二叉树前序、中序、后序遍历的递归和非递归算法,以及一个层序遍历的Java实现:源代码

--EOF--