Java实现遍历、排序、查找算法及简要说明(共11页).docx

精选优质文档-倾情为你奉上1. 遍历算法（遍历二叉树6种方法）1.1. 概述遍历算法针对二叉树而言的，主要有先序、中序、后序三种遍历顺序，三种顺序又分别有递归和常规算法，二叉树遍历的主要思想是：遍历左子树，遍历右子树，访问根节点，由这三者的遍历顺序来确定是先序、中序还是后序。下面只要求掌握递归遍历算法，常规遍历算法见附录一。1.2. 先序遍历算法遍历顺序：访问根节点，遍历左子树，遍历右子树。代码如下：void preOrder(BinaryTreeNode bt) if (bt = null)/ 如果当前树为空，则终止递归return;System.out.print(bt.getData();/ 先访问根节点preOrder(bt.getLeftChild();/ 再遍历左子树preOrder(bt.getRightChild();/ 再遍历右子树1.3. 中序遍历算法遍历顺序：遍历左子树，访问根节点，遍历右子树。代码如下：void midOrder(BinaryTreeNode bt) if (bt = null)/ 如果当前树为空，则终止递归return;preOrder(bt.getLeftChild();/ 先遍历左子树System.out.print(bt.getData();/ 再访问根节点preOrder(bt.getRightChild();/ 再遍历右子树1.4. 后序遍历算法遍历顺序：遍历左子树，遍历右子树，访问根节点。代码如下：void postOrder(BinaryTreeNode bt) if (bt = null)/ 如果当前树为空，则终止递归return;preOrder(bt.getLeftChild();/ 先遍历左子树preOrder(bt.getRightChild();/ 再遍历右子树System.out.print(bt.getData();/ 再访问根节点1.5. 层次遍历算法void levelOrder(BinaryTreeNode bt) if (bt = null)return;Queue q = new ArrayQueue();q.enqueue(bt);while (!q.isEmpty() bt = (BinaryTreeNode) q.dequeue();/ 取出队首元素，访问之System.out.println(bt.getData();if (bt.hasLeftChild() q.enqueue(bt.getLeftChild();/ 如果左节点存在，放入队列中if (bt.hasRightChild() q.enqueue(bt.getRightChild();/ 如果右节点存在，放入队列中2. 排序算法（9种排序算法）2.1. 概述将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。2.2. 插入类排序基本思想是：逐个考察每个待排序元素，将每一个新元素插入到前面已经排好序的序列中适当的位置上，使得新序列仍然是一个有序序列。主要介绍三种：直接插入排序、折半插入排序和希尔排序。2.2.1. 直接插入排序思路：仅有一个元素的序列总是有序的，因此，对 n 个记录的序列，可从第二个元素开始直到第 n 个元素，逐个向有序序列中执行插入操作，从而得到 n 个元素按关键字有序的序列。代码如下：void insert(int a) for (int i = 1; i < a.length; i+) / 从第二个开始比较插入/ 待插入的元素比之前排好序的元素最大值小才需要插入if (ai < ai - 1) int tmp = ai;/ 把当前位置腾出来ai = ai - 1;/ 和已排好序的最大值交换顺序int j = i - 2;/ 遍历之前i-2个元素找出要插入的位置/ 如果待插入元素小于已排好序中的第j位并j不小于0则继续遍历for (; j >= 0 && tmp < aj; j-)aj + 1 = aj;aj + 1 = tmp;/ j + 1即为待插入位置2.2.2. 折半插入排序思路：可以不断二分有序序列来确定插入位置，即搜索插入位置的方法可以使用折半查找实现。代码如下：void binaryInsert(int a) for (int i = 1; i < a.length; i+) / 从第二个开始比较插入/ 待插入的元素比之前排好序的元素最大值小才需要插入if (ai < ai - 1) int tmp = ai;/ 把当前位置腾出来ai = ai - 1;/ 和已排好序的最大值交换顺序int low = 0, high = i - 1, mid;/high=已排好序列的长度while (low < high) mid = (low + high) / 2;if (tmp < amid)high = mid - 1;elselow = mid + 1;int j = i - 2;/ 遍历之前i-2个元素找出要插入的位置/ 取high是因为经过while循环后high一定是不大于low的for (; j > high; j-)aj + 1 = aj;ahigh + 1 = tmp;/ high + 1即为待插入位置2.2.3. 希尔排序思路：首先将待排序的元素分为多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序”后，再对所有元素进行一次直接插入排序。static void shell(int a) int d = 1;/ 定义步长值while (d <= a.length / 3)d = d * 3 + 1;/ 根据数组长度生成步长终值for (; d > 0; d = (d - 1) / 3) / 还原步长值for (int i = d; i < a.length; i+) / 从第1个步长开始比较插入/ 待插入的元素比之前排好序的元素最大值小才需要插入if (ai < ai - d) int tmp = ai;/ 把当前位置腾出来ai = ai - d;/ 和已排好序的最大值交换顺序int j = i - d - 1;/ 遍历之前i-d-1个元素找出要插入的位置/ 如果待插入元素小于已排好序中的第j位并j不小于0则继续遍历for (; j >= 0 && tmp < aj; j -= d)aj + d = aj;aj + d = tmp;/ j + d即为待插入位置2.3. 交换类排序2.3.1. 基本思想交换类排序主要是通过两两比较待排元素的关键字，若发现与排序要求相逆，则“交换”之。2.3.2. 冒泡排序void bubble(int a) for (int i = 0; i < a.length; i+) / 先遍历数组for (int j = 1; j < a.length - i; j+) / 遍历未排好序的len-i个元素if (aj - 1 > aj) / 前后比较int tmp = aj - 1;aj - 1 = aj;aj = tmp;2.3.3. 快速排序思路：划分步骤：通过枢轴元素 x 将序列一分为二， 且左子序列的元素均小于 x，右子序列的元素均大于 x；治理步骤：递归的对左、右子序列排序；void quick(int a, int low, int high) if (low < high) int part = partition(a, low, high);quick(a, low, part - 1);quick(a, part + 1, high);int partition(int a, int low, int high) int tar = alow;while (low < high) / 循环该段数据while (low < high && tar < ahigh)/ 先从高端开始查找high-;alow = ahigh;/ 交换数据while (low < high && tar > alow)/ 再从低端开始查找low+;ahigh = alow;/ 交换数据alow = tar;/ 重新设置枢轴return low;/ 返回枢轴位置2.4. 选择类排序2.4.1. 概述每一趟从 n-i+1 (i=1,2,n)个元素中选取一个关键字最小的元素作为有序序列中第 i 个元素。2.4.2. 简单选择排序void recursionSort(int arr, int index) / 递归选择排序if (index < arr.length) for (int i = 0; i < arr.length; i+) if (arrindex < arri) int tmp = arrindex;arrindex = arri;arri = tmp;index+;recursionSort(arr, index);void commonSort(int arr) / 简单选择排序for (int i = 0; i < arr.length; i+) for (int j = i + 1; j < arr.length; j+) if (arri > arrj) int tmp = arrj;arrj = arri;arri = tmp;2.4.3. 树形选择排序和堆排序（附录二）2.5. 并归排序排序思想：1. 划分：将待排序的序列划分为大小相等（或大致相等）的两个子序列；2. 治理：当子序列的规模大于 1 时，递归排序子序列，如果子序列规模为 1 则成为有序序列；3. 组合：将两个有序的子序列合并为一个有序序列。void msort(int a, int low, int high) if (low < high) msort(a, low, (high + low) / 2);msort(a, (high + low) / 2 + 1, high);/并归后半段merge(a, low, (high + low) / 2, high);/并归前半段void merge(int a, int p, int q, int r) int b = new intr - p + 1;int s = p;/并归a中p到q，q+1到r两个数组int t = q + 1;int k = 0;while (s <= q && t <= r)/并归交叉段if (as < at)bk+ = as+;elsebk+ = at+;while (s <= q)/并归剩下的段bk+ = as+;while (t <= r)bk+ = at+;for (int i = 0; i < b.length; i+)ap + i = bi;2.6. 各种排序之间的比较3. 查找算法（3种查找算法）3.1. 顺序查找int order(int array, int tar) for (int i = 0; i < array.length; i+) if (tar = arrayi)return i + 1;return -1;3.2. 折半查找int binRecursion(int array, int tar, int low, int high) / 二分法查找递归int mid;if (low > high)return -1;mid = (high + low) / 2;if (tar = arraymid)return mid + 1;else if (tar > arraymid)binRecursion(array, tar, mid+, high);elsebinRecursion(array, tar, low, mid-);return -1;int bin(int array, int tar) / 二分法查找非递归int low = 0, high = array.length - 1, mid;while (low <= high) mid = (low + high) / 2;if (arraymid = tar)return mid + 1;else if (arraymid < tar)low = mid + 1;elsehigh = mid - 1;return -1;3.3. 二叉树查找BinaryTreeNode binaryTreeRecusion(BinaryTreeNode bt, Object tar) / 二叉树递归查找算法if (bt = null)return new BinaryTreeNode("null");switch (pare(tar, bt.getData() case -1:/ tar比data小就查找左子树return binaryTreeRecusion(bt.getLeftChild(), tar);case 1:/ tar比data大就查找右子树return binaryTreeRecusion(bt.getRightChild(), tar);default:/ 比较结果是0，tar和data相等就返回return bt;BinaryTreeNode binaryTree(BinaryTreeNode bt, Object tar) / 二叉树非递归查找算法while (bt != null) switch (pare(tar, bt.getData() case -1:/ tar比data小就查找左子树return bt = bt.getLeftChild();case 1:/ tar比data大就查找右子树return bt = bt.getRightChild();default:/ 比较结果是0，tar和data相等就返回return bt;return new BinaryTreeNode("null");4. 附录一void preOrder(BinaryTreeNode p) / 二叉树先序遍历非递归算法Stack s = new SingleLinkedStack();while (p != null) while (p != null) System.out.println(p.getData();/ 访问根节点if (p.hasRightChild() / 右子树压栈s.push(p.getRightChild();p = p.getLeftChild();/ 继续访问左子树直到为空if (!s.isEmpty() p = (BinaryTreeNode) s.pop();/ 当当前左子树遍历完成，存右子树的栈退栈BinaryTreeNode goFarLeft(BinaryTreeNode bt, Stack s) / 找到最左节点if (bt = null)return null;while (bt.hasLeftChild() s.push(bt);bt = bt.getLeftChild();return bt;void midOrder(BinaryTreeNode bt) / 二叉树中序遍历的非递归算法Stack s = new SingleLinkedStack();BinaryTreeNode p = goFarLeft(bt, s);/ 找到最左节点/ 如果最左节点不为空则继续查找while (p != null) System.out.println(p.getData();/ 访问根节点if (p.hasRightChild() / 如果有右孩子节点，则访问有孩子节点的最左孩子节点p = goFarLeft(p.getRightChild(), s); else if (!s.isEmpty() / 如果没有右孩子节点且栈不为空，则弹栈往回找上一级p = (BinaryTreeNode) s.pop(); elsep = null;/ 栈为空则查找完成void lastOrder(BinaryTreeNode p) / 二叉树后序遍历非递归算法Stack s = new SingleLinkedStack();BinaryTreeNode pre = null;/ 缓存上次访问节点/ 如果最左节点不为空则继续查找while (p != null | !s.isEmpty() while (p != null) / 查找最左节点s.push(p);p = p.getLeftChild();if (!s.isEmpty() / 取出栈顶节点p = (BinaryTreeNode) s.peek();/ 判断当前节点是否是父亲节点的右子节点，如果是/ 只需访问其父节点即可完成以p的父节点为根节点的子树的访问if (!p.hasRightChild() | p.getRightChild() = pre) list.insertLast(p);s.pop();pre = p;p = null; elsep = p.getRightChild();5. 附录二堆排序：/ 已知 rlow.high中除 rlow之外，其余元素均满足堆的定义private void heapAdjust(int r, int low, int high) int tmp = rlow;for (int j = 2 * low; j <= high; j = j * 2) / 沿关键之较大的元素向下进行筛选if (j < high && rj > rj + 1)/ j 指向关键之较大的元素j+;if (tmp >= rj)/ 若 temp 比其孩子都大，则插入到 low 所指位置break;rlow = rj;low = j; / 向下筛选rlow = tmp;public void heapSort(int r) int n = r.length - 1;for (int i = n / 2; i >= 1; i-)/ 初始化建堆heapAdjust(r, i, n);for (int i = n; i > 1; i-) / 不断输出堆顶元素并调整 r1.i-1为新堆int tmp = r1; / 交换堆顶与堆底元素r1 = ri;ri = tmp;heapAdjust(r, 1, i - 1); / 调整专心-专注-专业