while在算法中的用法收集

103 阅读 0 评论 68 点赞

我是靠谱客的博主高高招牌，这篇文章主要介绍while在算法中的用法收集，现在分享给大家，希望可以做个参考。

出处：算法第四版

表达一个用的角度，此处代码实际用在heapSort的时候会发现index边界问题没有考虑

复制代码

public class Helper {
    public static boolean isLess(int[] a, int i, int j) {
        return a[i] < a[j];
    }

public static void exch(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

/**
     * 算法第四版中实现优先队列时，由于某个节点变得比它父节点大而打破平衡
     * 的该节点上浮方法
     * @param a 简化的int数组
     * @param k 要上浮的元素的index
     */
    public static void swim(int[] a, int k) {
        while (k > 1 && isLess(a, k / 2, k)) {
            // k > 1保证k / 2有意义, k / 2是当前k的父节点
            // 父节点的值小于当前节点就上浮
            exch(a, k / 2, k);
            // 子节点变为父节点继续上移
            k /= 2;
        }
    }

/**
     * 算法第四版中实现优先队列时，由于某个节点变得比它子节点小而打破平衡
     * 的该节点下沉方法
     * @param a 简化的int数组
     * @param k 要下沉的元素的index
     */
    public static void sink(int[] a, int k) {
        while (2 * k <= a.length) {
            // 获得子节点index
            int j = 2 * k;
            if (j < a.length && isLess(a, j, j+1)) {
                // 找到当前子节点中值更大的index
                j++;
            }
            if (!isLess(a, k, j)) {
                // 如果k比子节点大，不交换
                break;
            }
            exch(a, k, j);
            // 顶端index变为子节点的index，继续向下判断时候还有更小的子节点
            k = j;
        }
    }
}

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
47
48
49
50
51
52
public class Helper {
    public static boolean isLess(int[] a, int i, int j) {
        return a[i] < a[j];
    }

    public static void exch(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 算法第四版中实现优先队列时，由于某个节点变得比它父节点大而打破平衡
     * 的该节点上浮方法
     * @param a 简化的int数组
     * @param k 要上浮的元素的index
     */
    public static void swim(int[] a, int k) {
        while (k > 1 && isLess(a, k / 2, k)) {
            // k > 1保证k / 2有意义, k / 2是当前k的父节点
            // 父节点的值小于当前节点就上浮
            exch(a, k / 2, k);
            // 子节点变为父节点继续上移
            k /= 2;
        }
    }

    /**
     * 算法第四版中实现优先队列时，由于某个节点变得比它子节点小而打破平衡
     * 的该节点下沉方法
     * @param a 简化的int数组
     * @param k 要下沉的元素的index
     */
    public static void sink(int[] a, int k) {
        while (2 * k <= a.length) {
            // 获得子节点index
            int j = 2 * k;
            if (j < a.length && isLess(a, j, j+1)) {
                // 找到当前子节点中值更大的index
                j++;
            }
            if (!isLess(a, k, j)) {
                // 如果k比子节点大，不交换
                break;
            }
            exch(a, k, j);
            // 顶端index变为子节点的index，继续向下判断时候还有更小的子节点
            k = j;
        }
    }
}