2020软件工程作业04

2020软件工程作业04

这个作业属于哪个课程	https://edu.cnblogs.com/campus/zswxy/2018SE/
这个作业要求在哪里	https://edu.cnblogs.com/campus/zswxy/2018SE/homework/11406
这个作业的目标	实现算法
其他参考文献	...

快速排序

思路：

1. 从数列中挑出一个元素，称为"基准"（pivot）
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。
3. 递归把小于基准值元素的子数列和大于基准值元素的子数列排序。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * Created by HeHao on 2020/10/28 10:51
 */
public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        int i, j, temp, t;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        //temp就是基准位
        temp = arr[low];

        while (i < j) {
            //先看右边，依次往左递减
            while (temp <= arr[j] && i < j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp >= arr[i] && i < j) {
                i++;
            }
            //如果满足条件则交换
            if (i < j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j - 1);
        //递归调用右半数组
        quickSort(arr, j + 1, high);
    }


    public static void main(String[] args) throws IOException {
//        int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
//        quickSort(arr, 0, arr.length - 1);
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String len = reader.readLine();
        String[] strArray = reader.readLine().split(" ");
        int[] array = Arrays.stream(strArray).mapToInt(Integer::parseInt).toArray();
        int times = Integer.parseInt(reader.readLine());
        int l, r, k;
        for (int i = 0; i < times; i++) {
            int[] lrk = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            l = lrk[0];
            r = lrk[1];
            k = lrk[2];
            quickSort(array, 0, array.length - 1);
            System.out.println("从左往右第" + l + "到第" + r + "中第" + k + "个数是" + array[r - k]);
        }
    }
}

二叉树遍历

四种主要的遍历思想为：

1. 先序遍历：根结点 —> 左子树 —> 右子树

2. 中序遍历：左子树—> 根结点 —> 右子树

3. 后序遍历：左子树 —> 右子树 —> 根结点

4. 层次遍历：只需按层次遍历即可

import java.util.LinkedList;

/**
 * Created by HeHao on 2020/10/28 10:51
 */
public class Main {
    public static void main(String[] args) {
        Node root = into();
        // 先序遍历
        System.out.print(" 先序遍历：");
        A(root);
        // 中序遍历
        System.out.print(" 中序遍历：");
        B(root);
        // 后续遍历
        System.out.print(" 后续遍历：");
        C(root);
        // 层级遍历
        System.out.print(" 层次遍历：");
        D(root);

    }

    private static void A(Node root) {
        // TODO 先序遍历
        if (root == null) return;
        System.out.print(root.data);
        A(root.l);
        A(root.r);
    }

    private static void B(Node root) {
        // TODO 中序遍历
        if (root == null) return;
        B(root.l);
        System.out.print(root.data);
        B(root.r);
    }

    private static void C(Node root) {
        // TODO 后续遍历
        if (root == null) return;
        C(root.l);
        C(root.r);
        System.out.print(root.data);
    }

    private static void D(Node root) {
        // TODO 层级遍历
        if (root == null) return;
        LinkedList<Node> linkedList = new LinkedList<>();
        Node current = null;
        //将根节点入队
        linkedList.offer(root);
        while (!linkedList.isEmpty()) {
            //出队队头元素并访问
            current = linkedList.poll();
            System.out.print(current.data);
            //如果当前节点的左节点不为空入队
            if (current.l != null) {
                linkedList.offer(current.l);
            }
            //如果当前节点的右节点不为空，把右节点入队
            if (current.r != null) {
                linkedList.offer(current.r);
            }
        }
    }

    // 构建一颗树，返回根节点
    private static Node into() {
        Node root = new Node("A");
        Node node1 = new Node("T");
        Node node2 = new Node("D");
        Node node3 = new Node("N");
        Node node4 = new Node("B");
        Node node5 = new Node("6");
        Node node6 = new Node("5");
        Node node7 = new Node("4");
        Node node8 = new Node("9");
        Node node9 = new Node("1");
        root.l = node1;
        node1.l = node2;
        node2.l = node3;
        node2.r = node6;
        node3.r = node7;
        node7.r = node8;
        node6.l = node9;
        node3.l = node4;
        root.r = node5;
        return root;
    }

    // 节点
    static class Node {
        // 数据
        Object data;
        // 左孩子
        Node l;
        // 右孩子
        Node r;

        public Node() {
        }

        public Node(Object data) {
            this.data = data;
            this.l = null;
            this.r = null;
        }

        public Node(Object data, Node l, Node r) {
            this.data = data;
            this.l = l;
            this.r = r;
        }
    }
}