《Java实现遍历、排序、查找算法及简要说明》由会员分享，可在线阅读，更多相关《Java实现遍历、排序、查找算法及简要说明（10页珍藏版）》请在金锄头文库上搜索。
1、1. 遍历算法(遍历二叉树 6种方法)1.1. 概述遍历算法针对二叉树而言的，主要有先序、中序、后序三种遍历顺序，三种顺序又分别有递归和常规算法， 二叉树遍历的主要思想是：遍历左子树，遍历右子树，访问根节点，由这三者的遍历顺序来确定是先序、中 序还是后序。下面只要求掌握递归遍历算法，常规遍历算法见附录一。1.2. 先序遍历算法遍历顺序：访问根节点，遍历左子树，遍历右子树。代码如下：void preOrder(BinaryTreeNode bt) if (bt = null)/ 如果当前树为空，则终止递归return;System.out.print(bt.getData();/ 先访问根节点p
2、reOrder(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. 后序遍历算法遍历
3、顺序：遍历左子树，遍历右子树，访问根节点。代码如下：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
4、.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
5、. 插入类排序基本思想是：逐个考察每个待排序元素，将每一个新元素插入到前面已经排好序的序列中适当的位置上，使得新序列仍然是一个有序序列。主要介绍三种：直接插入排序、折半插入排序和希尔排序。2.2.1. 直接插入排序思路：仅有一个元素的序列总是有序的，因此，对 n 个记录的序列，可从第二个元素开始直到第 n 个元素，逐个向有序序列中执行插入操作，从而得到 n 个元素按关键字有序的序列。代码如下：void insert(int a) for (int i = 1; i a.length; i+) / 从第二个开始比较插入/ 待插入的元素比之前排好序的元素最大值小才需要插入if (ai = 0 &
6、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
7、;while (low high) mid = (low + high) / 2;if (tmp high; j-)aj + 1 = aj;ahigh + 1 = tmp;/ high + 1即为待插入位置2.2.3. 希尔排序思路：首先将待排序的元素分为多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分 别进行直接插入排序，待整个待排序序列“基本有序”后，再对所有元素进行一次直接插入排序。 static void shell(int a) int d = 1;/ 定义步长值while (d 0; d = (d - 1) / 3) / 还原步长值for (int i = d; i a
8、.length; i+) / 从第1个步长开始比较插入/ 待插入的元素比之前排好序的元素最大值小才需要插入if (ai = 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 aj) / 前后比较int tmp = aj - 1;aj -
9、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)
10、 / 循环该段数据while (low high & tar ahigh)/ 先从高端开始查找high-;alow = ahigh;/ 交换数据while (low alow)/ 再从低端开始查找low+;ahigh = alow;/ 交换数据alow = tar;/ 重新设置枢轴return low;/ 返回枢轴位置2.4. 选择类排序2.4.1. 概述每一趟从n-i+1 （i=l,2,个元素中选取一个关键字最小的元素作为有序序列中第i个元素。2.4.2. 简单选择排序void recursionSort(int arr, int index) / 递归选择排序 if (index arr.
11、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 arrj) int tmp = arrj; arrj = arri;arri = tmp;2.4.3. 树形选择排序和堆排序（附录二
12、）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+;else
