~~~ package stackAndQueue; import java.util.Stack; /** * 用栈来求解汉诺塔问题：HanoiStack【3】 * * 【问题描述】：将汉诺塔游戏（小压大）规则修改，不能从左（右）侧的塔直接移到右（左）侧，而是必须经过中间塔。 * * 求当塔有N层时，打印最优移动过程和最优移动步数。如N=2，记上层塔为1，下层为2.则打印：1：left->mid;1 * * 由于必须经过中间，实际动作只有4个：左L->中M，中->左，中->右R，右->中。 * * 原则：①小压大；②相邻不可逆（上一步是L->M,下一步绝不能是M->L） * * 非递归方法核心结论：1.第一步一定是L-M；2.为了走出最少步数，四个动作只可能有一个不违反上述两项原则。 * * 核心结论2证明：假设前一步是L->M（其他3种情况略） * * a.根据原则①，L->M不可能发生；b.根据原则②，M->L不可能；c.根据原则①，M->R或R->M仅一个达标。 * * So，每走一步只需考察四个步骤中哪个步骤达标，依次执行即可。 * * @author xiaofan */ public class HanoiStack { private enum Action { None, LToM, MToL, MToR, RToM }; static Action preAct = Action.None; // 上一步操作，最初什么移动操作都没有 final static int num = 4; // 汉诺塔层数 public static void main(String[] args) { int steps = transfer(num); System.out.println("It will move " + steps + " steps."); } private static int transfer(int n) { Stack<Integer> lS = new Stack<>(); // java7菱形用法，允许构造器后面省略范型。 Stack<Integer> mS = new Stack<>(); Stack<Integer> rS = new Stack<>(); lS.push(Integer.MAX_VALUE);// 栈底有个最大值，方便后续可以直接peek比较 mS.push(Integer.MAX_VALUE); rS.push(Integer.MAX_VALUE); for (int i = n; i > 0; i--) { lS.push(i);// 初始化待移动栈 } int step = 0; while (rS.size() < n + 1) {// n+1,因为rS.push(Integer.MAX_VALUE);等于n+1说明全部移动完成 step += move(Action.MToL, Action.LToM, lS, mS);// 第一步一定是LToM step += move(Action.LToM, Action.MToL, mS, lS);// 只可能有这4种操作 step += move(Action.MToR, Action.RToM, rS, mS); step += move(Action.RToM, Action.MToR, mS, rS); } return step; } /** * 实施移动操作. * * @param cantAct * 不能这样移动 * @param nowAct * 即将执行的操作 * @param fromStack * 起始栈 * @param toStack * 目标栈 * @return step(成功与否) */ private static int move(Action cantAct, Action nowAct, Stack<Integer> fromStack, Stack<Integer> toStack) { if (preAct != cantAct && toStack.peek() > fromStack.peek()) { toStack.push(fromStack.pop()); // 执行移动操作 System.out.println(toStack.peek() + ":" + nowAct); preAct = nowAct; // 更新“上一步动作” return 1; } return 0; } } ~~~ 代码地址：[https://github.com/zxiaofan/Algorithm/tree/master/src/stackAndQueue](https://github.com/zxiaofan/Algorithm/tree/master/src/stackAndQueue)

~~~ package stackAndQueue; import java.util.Stack; import org.junit.Test; /** * 由两个栈组成的队列：TwoStackQueue【2】 * * 【编写一个类，用两个栈实现队列，支持队列的基本操作(add、poll、peek)】 * * 设计思路：栈-先进后出，队列-先进先出。用两个栈把顺序反过来。 * * stackPush只管进栈，stackPop只管出栈且【仅当】其为空时，将stackPush的元素【全部】转移到stackPop。 * * @author xiaofan */ public class TwoStackQueue { private Stack<Integer> stackPush; private Stack<Integer> stackPop; public TwoStackQueue() { this.stackPush = new Stack<Integer>(); this.stackPop = new Stack<Integer>(); } public void add(int e) { this.stackPush.push(e); } public int poll() { tranfer(); return this.stackPop.pop(); } public int peek() { tranfer(); return this.stackPop.peek(); } private void tranfer() { if (this.stackPop.empty()) { if (this.stackPush.isEmpty()) { // isEmpty是Stack继承的Vector的方法 throw new RuntimeException("Your queue is empty."); } while (!this.stackPush.empty()) { // empty是Stack自带的方法 this.stackPop.push(this.stackPush.pop()); } } } /////// 测试方法////// @Test public void test() { TwoStackQueue queue = new TwoStackQueue(); queue.add(1); queue.add(2); queue.add(3); queue.add(3); queue.add(4); System.out.println("peek:" + queue.peek()); while (true) { // 未重写empty方法，只能这样遍历 try { System.out.println(queue.poll()); } catch (Exception e) { break; } } TwoStackQueue queue1 = new TwoStackQueue(); queue1.peek(); // java.lang.RuntimeException: Your queue is empty. } } ~~~ 代码地址：[https://github.com/zxiaofan/Algorithm/tree/master/src/stackAndQueue](https://github.com/zxiaofan/Algorithm/tree/master/src/stackAndQueue)

~~~ package stackAndQueue; import java.util.Stack; import org.junit.Test; /** * * 设计一个有getMin功能的栈：StackGetMin【1】. * * 【实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作】 * * 要求：1、pop、push、getMin操作的时间复杂度都是O(1);2、设计的栈类型可以使用现成的栈结构。 * * 设计思路：两个栈-普通栈+getMin栈 * * @author xiaofan. */ public class StackGetMin { private Stack<Integer> stackData; private Stack<Integer> stackGetMin; /** * 构造函数. */ public StackGetMin() { this.stackData = new Stack<Integer>(); this.stackGetMin = new Stack<Integer>(); } public void push(int item) { // 压入稍省空间 this.stackData.push(item); if (this.stackGetMin.isEmpty()) { this.stackGetMin.push(item); } else if (item <= this.getMin()) { // 小于等于:避免插入多个最小值再弹出后，栈中无最小值 this.stackGetMin.push(item); } } public int pop() { // 弹出稍费时间 if (this.stackData.isEmpty()) { // 判空 throw new RuntimeException("Your Stack is empty."); } int value = this.stackData.pop(); if (value == this.getMin()) { // 两个栈同步弹出 this.stackGetMin.pop(); } return value; } public int getMin() { if (this.stackGetMin.isEmpty()) { throw new RuntimeException("Your Stack is empty."); } return this.stackGetMin.peek(); } //////////// 测试类///////////////// @Test public void test() { StackGetMin myStack = new StackGetMin(); myStack.push(2); myStack.push(5); myStack.push(4); myStack.push(1); myStack.push(1); System.out.println(myStack.pop()); System.out.println(myStack.getMin()); StackGetMin myStack1 = new StackGetMin(); myStack1.pop(); // RuntimeException("Your Stack is empty.") } ///////// 方案2////// // 如果StackGetMin栈顶元素比比newNum小，则将栈顶元素重复压入 // 压入稍费空间，弹出稍省时间 } ~~~ 代码地址：[https://github.com/zxiaofan/Algorithm/tree/master/src/stackAndQueue](https://github.com/zxiaofan/Algorithm/tree/master/src/stackAndQueue)

~~~ package stackAndQueue; import java.util.Stack; import org.junit.Test; /** * 仅用递归函数和栈逆序一个栈：ReverseStack【2】 * * 【一个栈依次压入1、2、3，将栈转置，使栈顶到栈底依次是1、2、3，只能用递归函数，不能借用额外的数据结构包括栈】 * * 算法思想：两个递归函数（getAndRemoveBottom、reverse） * * @author xiaofan */ public class ReverseStack { /** * 返回并移除当前栈底元素（栈内元素<栈底>1、2、3<栈顶>变为2、3<栈顶>）. */ private int getAndRemoveBottom(Stack<Integer> stack) { int result = stack.pop(); if (stack.empty()) { return result; } else { int bottom = getAndRemoveBottom(stack); stack.push(result); return bottom; // 第一轮时，返回栈底元素1 } } /** * 每层递归取出栈底的元素并缓存到变量中，直到栈空； * * 然后逆向将每层变量压入栈，最后实现原栈数据的逆序。 * * @param stack */ public void reverse(Stack<Integer> stack) { if (stack.empty()) { return; } int i = getAndRemoveBottom(stack); // 依次返回1、2、3 reverse(stack); stack.push(i); // 依次压入3、2、1 } ///////// 测试方法//////// @Test public void test() { Stack stack = new Stack(); // Stack继承Vector，默认容量是10 stack.push(1); stack.push(2); stack.push(3); ReverseStack rStack = new ReverseStack(); rStack.reverse(stack); while (!stack.empty()) { System.out.println(stack.pop()); } } } ~~~ 代码地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/stackAndQueue/ReverseStack.java](https://github.com/zxiaofan/Algorithm/blob/master/src/stackAndQueue/ReverseStack.java)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。速度仅次于快速排序，为稳定排序算法，一般用于总体无序，但是各子项相对有序的数列。若将两个有序表合并成一个有序表，称为二路[归并](http://baike.baidu.com/view/711818.htm)。 **1、算法思想** 比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。 归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。 基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。 （1）分治法的三个步骤 设归并排序的当前区间是R[low..high]，分治法的三个步骤是： ①分解：将当前区间一分为二，即求分裂点          ②求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序； ③组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。 递归的终结条件：子区间长度为1（一个记录自然有序）。 **2、代码实现：** ~~~ package sort; public class MergingSort { public static void main(String[] args) { int[] a = {3, 2, 5, 4, 1}; sort(a, 0, a.length - 1); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } public static void sort(int[] data, int left, int right) { if (left < right) { // 首先找出中间的索引 int center = (left + right) / 2; // 对左边的数组进行递归,使左边有序 sort(data, left, center); // 对中间索引右边的数组进行递归，使右边有序 sort(data, center + 1, right); // 再将二个有序数列合并 merge(data, left, center, right); } } public static void merge(int[] data, int left, int center, int right) { int[] tmpArr = new int[data.length]; int mid = center + 1; // third记录中间数组的索引 int third = left; int tmp = left; while (left <= center && mid <= right) { // 将两个数组中取出最小的数放入中间数组 if (data[left] <= data[mid]) { tmpArr[third++] = data[left++]; } else { tmpArr[third++] = data[mid++]; } } // 剩余部分依次放入中间数组 while (mid <= right) { tmpArr[third++] = data[mid++]; } while (left <= center) { tmpArr[third++] = data[left++]; } while (tmp <= right) { data[tmp] = tmpArr[tmp++]; } } } ~~~ **3、算法分析** 1、稳定性 归并排序是一种稳定的排序。 2、存储结构要求 可用顺序存储结构。也易于在链表上实现。 3、时间复杂度 对长度为n的文件，需进行 **lgn** **趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。** 4、空间复杂度 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。 注意： 若用单链表做存储结构，很容易给出就地的归并排序。 5、比较操作的次数介于(nlogn) / 2和nlogn - n + 1。 6、赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n) 7、归并排序比较占用内存，但却是一种效率高且稳定的算法。 代码地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/MergingSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/MergingSort.java)

**1、算法思想：** 一趟快速排序的算法是： 1）、设置两个变量I、J，排序开始的时候I：=1，J：=N； 2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]； 3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换； 4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换； 5）、重复第3、4步，直到I=J； **2、代码实现：** 注意： ~~~ if (a.length > 0) { // 查看数组是否为空             quickSort(a, 0, a.length - 1);         } ~~~ ~~~ private static void quickSort(int[] list, int low, int high) { if (low < high) {// 不是while，否则死循环 int middle = partition(list, low, high); // 将list数组进行一分为二 quickSort(list, low, middle - 1); // 对低字表进行递归排序 quickSort(list, middle + 1, high); // 对高字表进行递归排序 } } private static int partition(int[] arr, int low, int high) { int tmp = arr[low]; // 数组的第一个元素作为基准,用temp临时存储 while (low < high) {// 从区间两端交替向中间扫描，直至low=high为止 while (low < high && arr[high] >= tmp) {// high向前搜索,直到找到第一个比temp小的元素 high--; } arr[low] = arr[high]; // 比temp小的(high)移到低端 while (low < high && arr[low] <= tmp) {// low下标增至第一个比temp大的元素 low++; }// while终止说明arr[low]>temp arr[high] = arr[low]; // 比temp大的(low)移到高端 } // 当low == high，完成一趟快速排序，此时low位相当于空，等待基准temp补上 arr[low] = tmp; // 基准记录已被最后定位 return low; // 返回基准的位置【下标】<基准最终位置> } ~~~ **3、算法分析** 快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。 **（1）最坏时间复杂度** 最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。 因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值： Cmax = 1+2+3+……(n-1)=n(n-1)/2=O(n2) 如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序(或递减序)排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，则快速排序所需的比较次数反而最多。 **（2）最好时间复杂度** 在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数： 0(nlgn) 注意： 用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为O(lgn)，而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个排序过程所需要的关键字比较总次数C(n)=O(nlgn)。 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlgn)。 （3）基准关键字的选取 在当前无序区中选取划分的基准关键字是决定算法性能的关键。 **①"三者取中"的规则** "三者取中"规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区伺的第1个记录进行交换，此后的划分过程与上面所给的Partition算法完全相同。 **②取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准** 选取基准最好的方法是用一个随机函数产生一个取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准，这相当于强迫R[low..high]中的记录是随机分布的。用此方法所得到的快速排序一般称为随机的快速排序。 注意： 随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大地提高了，尤其是对初始有序的文件，一般不可能导致最坏情况的发生。算法的随机化不仅仅适用于快速排序，也适用于其它需要数据随机分布的算法。 （4）平均时间复杂度 尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。 （5）空间复杂度 快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。 （6）稳定性 快速排序是非稳定的，例如[2，2，1]。 **4、算法改进** 在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低，且当k取值为 8 左右时,改进算法的性能最佳。 源码地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/QuickSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/QuickSort.java)

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 **1、算法思想** 1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 3、 针对所有的元素重复以上的步骤，除了最后一个。 4、 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。 **2、代码实现** ~~~ public static void bubbleSort(int[] source) { int length = source.length; for (int i = 0; i < length - 1; i++) { // N个数需N-1趟,每趟完成之后,较大元素将冒到数组最末端 for (int j = 0; j < length - 1 - i; j++) { // 每趟需要比较N-i次比较 if (source[j] > source[j + 1]) { swap(source, j, j + 1); } // System.out.print("\n外循环第" + (i + 1) + "次,内循环第" + (j + 1) + "次,排序结果："); // printArray(source); } System.out.println(""); } } ~~~ **3、算法分析**  ### 算法稳定性 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。 **4、算法改进** 对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。 本文再提供以下两种改进算法： 1）．设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。 改进后算法如下: ~~~ /** * 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。 * * 由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。 */ public static void bubbleSort2(int[] source) { int high = source.length - 1; while (high > 0) { // high=0时证明最后一次进行交换的位置为0 int pos = 0;// 每趟开始，无记录交换 for (int i = 0; i < high; i++) { if (source[i] > source[i + 1]) { swap(source, i, i + 1); pos = i; // 有交换则令pos=i } } high = pos; // 每趟for循环结束，pos、length变更一次 // System.out.println(high); } } ~~~ 2）．传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。 改进后的算法实现为: ~~~ /** * 每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大值和最小值), * * 从而使排序趟数几乎减少了一半。 */ public static void bubbleSort3(int[] source) { int low = 0; int high = source.length - 1; while (low < high) { for (int i = low; i < high; i++) { // 正向找最大 if (source[i] > source[i + 1]) { swap(source, i, i + 1); } } high--; // 一次for循环结束，最大数冒出 for (int i = high; i > low; i--) { // 逆向找最小 if (source[i] < source[i - 1]) { swap(source, i, i - 1); } } low++; } } ~~~ swap ~~~ private static void swap(int[] source, int x, int y) { int temp = source[x]; source[x] = source[y]; source[y] = temp; } ~~~ 源码地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/BubbleSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/BubbleSort.java)

堆排序是一种树形选择排序，是对直接选择排序的有效改进。 堆的构建--》堆排： 初始状态-<从最后一个结点开始，使该子树成堆（最小/大的数移到根节点）,不断循环>-初始堆（小/大顶）--输出堆顶元素（堆顶与堆的最后一个元素交换位置）--最后一个数移至堆顶--重新建--输出堆顶元素 以下为《数据结构（C++版）习题解答与实验指导》实例    1、算法思想 堆：具有n个元素的序列（k1,k2,...,kn),当且仅当满足  时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（最大项）。 若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如： (a)大顶堆序列：（96, 83,27,38,11,09) (b)小顶堆序列：（12，36，24，85，47，30，53，91）  初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。 因此，实现堆排序需解决两个问题： 1. 如何将n 个待排序的数建成堆； 2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。 首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。 调整大顶堆的方法： 1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。 2）将根结点与左、右子树中较大元素的进行交换。 3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）. 4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）. 5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。 称这个自 根结点 到 叶子结点 的调整过程为筛选。如图：  再讨论对n 个元素初始建堆的过程。 建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。 1）n 个结点的完全二叉树，则最后一个结点是第 个结点的子树。【向下取整】 2）筛选从第 个结点为根的子树开始，该子树成为堆。 3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。 如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）  2、代码实现 ~~~ package sort; public class HeapSort { public static void main(String[] args) { int[] src = { 66, 89, 8, 123, 9, 44, 55, 37, 200, 127, 98 }; System.out.println("初始值："); print(src); HeapSort(src, src.length); System.out.println("堆排后："); print(src); } /** * 大顶堆排序算法 */ private static void HeapSort(int src[], int length) {// 大顶堆排序算法 // 初始化堆,从最后一个节点 i= (length-1) / 2 for (int i = (length - 1) >> 1; i >= 0; --i) HeapAdjust(src, i, length); for (int i = length - 1; i > 0; --i) {// 从堆尾往前调整 src[i] = src[0] + (src[0] = src[i]) * 0;// 弹出堆顶最大值，堆尾值填补 HeapAdjust(src, 0, i);// 重新调整堆 } } /** * src[i+1,…. ,j]已经成堆，调整 i 的子树为堆. * * @param src是待调整的堆数组 * @param i是待调整的数组元素的位置 * @param j是待调整数组的长度 */ private static void HeapAdjust(int src[], int i, int j) {// 对下标为i的节点，调整其子树为堆 int temp = src[i]; int child = 2 * i + 1; // 左孩子的位置。(child+1 为当前调整结点的右孩子的位置) while (child < j) {// 防止第一次length为偶数12时，i=5与child=11非父子关系 if (child + 1 < j && src[child] < src[child + 1]) { // 定位较大的的孩子结点 ++child; } if (src[i] < src[child]) { // 如果较大的子结点大于父结点 src[i] = src[child]; // 那么把较大的子结点往上移动，替换它的父结点 i = child; // 更新i，以便使新子树为堆（子树结构可能改变） src[i] = temp; // 父结点放到比它大的孩子结点上（temp值未变） child = 2 * i + 1;// 若child<length，则继续循环建堆 } else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出 break;// 防止死循环 } } print(src); } private static void print(int a[]) { for (int i : a) { System.out.print(i + " "); } System.out.println(); } } ~~~ 3、算法分析 堆排序也是一种不稳定的排序算法。  堆排序优于简单选择排序的原因： 直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。 堆排序的**最坏时间复杂度为O(nlogn)**。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。 堆排序在最坏的情况下，其时间复杂度也为O(nlogn)。相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小的供交换用的辅助存储空间。 建堆时对于每个非终端结点来说，其实最多进行两次比较和互换操作，比较次数不超过4n 次，因此整个构建堆的时间复杂度为O(n)。 设树深度为k ，从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式：  因此堆排序最坏情况下，**时间复杂度也为：O(nlogn )**。 4、算法改进 堆排序可通过树形结构保存部分比较结果，可减少比较次数。 源码地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/HeapSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/HeapSort.java)

冒泡排序：在每一次比较的时候，如果发现相邻两数的次序不对，都会马上就把两数进行对调。 选择排序：则在比较过程中（内循环里面）并不进行对调，而是先记录下最小（大）数的下标，在一次扫描完成后再进行对调。  1、算法思想 在要排序的一组数中，选出最小（或者最大）的一个数与第 i（i=0）个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第i+1个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。 2、代码实现 ~~~ /** * 在要排序的一组数中，选出最小（或者最大）的一个数与第 i（i=0）个位置的数交换； 然后在剩下的数当中再找最小（或者最大）的与第i+1个位置的数交换， 依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。 */ private static void SimpleSelectSort(int[] source) { if (source.length <= 1 || source == null) {// 习惯，参数判断 return; } for (int i = 0; i < source.length - 1; i++) { // i < source.length尚可 int j = i + 1; int min = source[i]; // 最小值 int minIndex = i; // 最小值下标 while (j < source.length) { if (source[j] < min) { min = source[j]; minIndex = j; } j++; } if (minIndex != i) { // 3次赋值 source[i] = source[minIndex] + (source[minIndex] = source[i]) * 0; } printArr(source); } } ~~~ 3、算法分析 1.时间复杂度 选择排序的交换操作介于 0 和 (n - 1）次之间。 选择排序的比较操作为 n (n - 1）/ 2次。 选择排序的赋值操作介于 0 和 3 (n - 1）次之间(n-1次交换，每次交换需要赋值3次) t = a, a = b, b = t。 比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。 交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。 交换次数比[冒泡排序](http://baike.baidu.com/view/254413.htm)少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。 2.稳定性 选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。 4、算法改进 **二元选择排序** 简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：（类冒泡） ~~~ /** * 简单选择排序，每趟循环只能确定一个元素排序后的定位。 我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置。 从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。 */ private static void TwoSelectSort(int[] source) { int n = source.length; if (n <= 1 || source == null) {// 习惯，参数判断 return; } int minIndex, maxIndex, tempI; for (int i = 0; i < n / 2; i++) { minIndex = maxIndex = i; for (int j = i + 1; j < n - i; j++) { if (source[j] < source[minIndex]) { minIndex = j; continue; } if (source[j] > source[maxIndex]) { maxIndex = j; } } if (minIndex != i) { // 3次赋值 source[i] = source[minIndex] + (source[minIndex] = source[i]) * 0; } if (maxIndex == i) { // 此时最大值已被替换到minIndex处 maxIndex = minIndex; } if (maxIndex != n - i - 1) { source[n - i - 1] = source[maxIndex] + (source[maxIndex] = source[n - i - 1]) * 0; } printArr(source); } } ~~~ 冒泡排序改进算法之每趟循环确定两个元素时，不用考虑 if（maxIndex==i），因为其每趟比较只要不符合排序就要交换位置，而不是仅仅记录其索引的改变。 源码地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/SelectSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/SelectSort.java)

希尔排序（Shell Sort）是一种插入排序算法，因D.L.Shell于1959年提出而得名。 Shell排序又称作缩小增量排序。 1、算法思想 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d21重复上述的分组和排序，直至所取的增量d t=1(d tt-l<… 21)，即所有记录放在同一组中进行直接插入排序为止。 该方法实质上是一种分组插入方法。  2、代码实现 ~~~ package sort; /** * 希尔排序ShellSoet * * 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。 * * 所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序； * * 然后，取第二个增量d21重复上述的分组和排序，直至所取的增量d t=1(d tt-l<… 21)，即所有记录放在同一组中进行直接插入排序为止。 * * 该方法实质上是一种分组插入方法。 * * @author yunhai */ public class ShellSort { public static void main(String[] args) { int source[] = new int[]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4, 6}; System.out.print("排序前：\t"); printArray(source); shellSort(source); System.out.print("排序后：\t"); printArray(source); } private static void shellSort(int[] source) { int j; for (int gap = source.length / 2; gap > 0; gap /= 2) { // gap 为增长序列，递减至1【亦可自定义增长序列】 for (int i = gap; i < source.length; i++) { // 【直接插入排序】，从第一个gap处向后移,直至移到最后一个数 int temp = source[i];// 当前gap处的值 for (j = i; j >= gap && temp < source[j - gap];) {// 最后一个数如果是第一个gap的倍数，按理应第一次循环，但却最后循环 source[j] = source[j - gap]; // 较大数往后移 j -= gap; // 亦可放在循环体内 } source[j] = temp; // 跳出循环意味着temp的位置已确定 } System.out.print("增长序列" + gap + ": "); printArray(source); } } private static void printArray(int[] source) { for (int i = 0; i < source.length; i++) { System.out.print(source[i] + ","); } System.out.println(); } } ~~~ 3、算法分析 1）、增量序列的选择。 Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征如下： a.最后一个增量必须为1。 b.应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。 有人通过大量实验给出了目前最好的结果：当n较大时，比较和移动的次数大概在n^1.25到n^1.26之间。 2）、Shell排序的时间性能优于直接插入排序。 希尔排序的时间性能优于直接排序的原因如下： a.当文件初态基本有序时，直接插入排序所需的比较和移动次数均较少。 b.当n值较小时，n和n^2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n^2)差别不大。 c.在希尔排序开始时增量较大，分组较多，每组记录数目少，故每组内直接插入排序较快，后来增量d(i)逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按d(i-1)做为距离拍过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。 3）、稳定性 希尔排序是不稳定的。 4、算法改进 增量序列的选择：Shell排序的执行时间依赖于增量序列。  好的增量序列的共同特征：  ① 最后一个增量必须为1；  ② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。 源码地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/ShellSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/ShellSort.java)

1、算法思想 将一个记录插入到已排序好的有序表中，从而得到一个新的记录数增1的有序表。 即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 要点：设立哨兵，作为临时存储和判断数组边界之用。 2、代码实现 ~~~ package sort; public class StraightInsertSort { public static void main(String[] args) { int[] source = {99, 53, 27, 36, 15, 69, 42, 66}; printArr(source); StraightInsertSort(source); printArr(source); } /** * 将一个记录插入到已排序好的有序表中，从而得到一个新的记录数增1的有序表。 即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 要点：设立哨兵，作为临时存储和判断数组边界之用。 */ private static void StraightInsertSort(int[] source) { if (source.length <= 1 || source == null) { return; } int j; for (int i = 1; i < source.length; i++) { // 从第二个数开始，依次直接插入 j = i;// 亦可只用一个变量i，但会增加比较次数 while (j > 0 && source[j] < source[j - 1]) {// 位置不合适则交换 source[j] = source[j - 1] + (source[j - 1] = source[j]) * 0; j--; } printArr(source); } } private static void printArr(int[] source) { for (int i : source) { System.out.print(i + " "); } System.out.println(); } } ~~~ 3、算法分析 ### 算法稳定性 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况如下。 **最好情况**：序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。 **最坏情况**：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次（计算式为1+2+……+ n-1）。 直接插入排序属于稳定的排序，**最坏时间复杂度**为**O(n^2)**，**最好时间复杂度**为**O(n)**，**空间复杂度**为**O(1)**。 插入排序的赋值操作是比较操作的次数加上(n-1)次。 因此，插入排序**不适合对于数据量比较大**的排序应用。 源码地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/StraightInsertSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/StraightInsertSort.java)

排序算法相关内容（Java实现）是个人理解并代码实现的常用的内部排序算法，目前包括如下七大算法（暂不包括基数排序）： **直接插入排序、希尔排序、简单选择、堆排、冒泡、快排、归并排序**。 相关内容最初写在自己的云笔记上，现发表于博客，希望和大家多多交流。由于多数内容是直接从云笔记上copy过来的，编辑器不同使得个别文字格式或许有些不美观，但这不影响阅读。如有需要，将尽可能优化使其更美观。 在写这些内容之时，也借鉴了一些前辈的文章，每个算法都用Java自我实现了。本人也算不上大神，如有纰漏，望交流指正，共同进步。 相关代码都可以直接从本人github上阅读下载，地址：[https://github.com/zxiaofan/Algorithm/tree/master/src/sort](https://github.com/zxiaofan/Algorithm/tree/master/src/sort) 。

今天做这道题最初以为会用到什么数学公式，在思考后发现自己想多了。 思路主要两个： 1.生成一个质数表，再按要求求值（本文就按此方法）； 2.从小取到大，判断是否是质数，如果是就相乘，并构建计数器判断是否达到n个。 **算法训练 Torry的困惑(基本型)** 时间限制：1.0s   内存限制：512.0MB 问题描述 　　Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7……这样的数叫做质数。Torry突然想到一个问题，前10、100、1000、10000……个质数的乘积是多少呢？他把这个问题告诉老师。老师愣住了，一时回答不出来。于是Torry求助于会编程的你，请你算出前n个质数的乘积。不过，考虑到你才接触编程不久，Torry只要你算出这个数模上50000的值。 输入格式 　　仅包含一个正整数n，其中n<=100000。 输出格式 　　输出一行，即前n个质数的乘积模50000的值。 样例输入 1 样例输出 2 代码奉上 ~~~ import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { ArrayList<Integer> a = new ArrayList<Integer>(); a.add(2); for (int i = 3; i <= 100000; i += 2) { int j; for (j = 3; j <= Math.sqrt(i); j++) { if (i % j == 0) break; } if (j > Math.sqrt(i)) { a.add(i); } } Scanner in = new Scanner(System.in); int n = in.nextInt(); int s = 1; for (int i = 0; i < n; i++) { s = (s * a.get(i)) % 50000; } System.out.println(s); } } ~~~

基础练习 **十六进制转八进制** 问题描述 给定n个十六进制正整数，输出它们对应的八进制数。 输入格式 输入的第一行为一个正整数n （1<=n<=10）。 接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。 输出格式 输出n行，每行为输入对应的八进制正整数。 注意 输入的十六进制数不会有前导0，比如012A。 输出的八进制数也不能有前导0。 样例输入 2 39 123ABC 样例输出 71 4435274 提示 先将十六进制数转换成某进制数，再由某进制数转换成八进制。 自己做这道题的时候也算曲折，花了好几天20多次0分后终于修成正果。现将一些编程过程中的小经验分享，本人非大牛，如有什么错误，敬请指正，有更好的方法也请赐教。 **1.**思路：16进制转2进制，再转8进制，我先转的10进制，数据小还 行，数据大了就game over了。（本题数据最大为10万位） **2.**判断2进制的位数对3取模是多少，因为2到8是3位3位的看的。 **3.**删除最后数据前面的0（题目要求哈）。 **4.**我就死在这点上，测试数据不是一条条输入的，而是所有数据从文本读入，所以不能用Scanner，得用BufferedReader。 **5.**最后将StringBuffer转换为String输出，不然就是一直等待测评，我也不知道为什么，或许是我自己的问题吧。 **6.**本题注意以下函数用法： ~~~ ①BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); ②int n = Integer.parseInt(in.readLine()); ③a[i] = in.readLine(); ④char[] temp = a[i].toCharArray(); ⑤StringBuffer s2 = new StringBuffer(); ⑥s2.append(“0000”); ⑦s3.append(s2.substring(0, 1)); ~~~ 原码奉上 ~~~ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader( new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine()); String a[] = new String[n]; for (int i = 0; i < n; i++) { a[i] = in.readLine(); } for (int i = 0; i < n; i++) { char[] temp = a[i].toCharArray(); StringBuffer s2 = new StringBuffer(); // 16 to 2 int k = temp.length; for (int j = 0; j < k; j++) { switch (temp[j]) { case '0': s2.append("0000"); break; case '1': s2.append("0001"); break; case '2': s2.append("0010"); break; case '3': s2.append("0011"); break; case '4': s2.append("0100"); break; case '5': s2.append("0101"); break; case '6': s2.append("0110"); break; case '7': s2.append("0111"); break; case '8': s2.append("1000"); break; case '9': s2.append("1001"); break; case 'A': s2.append("1010"); break; case 'B': s2.append("1011"); break; case 'C': s2.append("1100"); break; case 'D': s2.append("1101"); break; case 'E': s2.append("1110"); break; case 'F': s2.append("1111"); break; } } // 2 to 8 StringBuffer s3 = new StringBuffer(); int m = 0; if (4 * k % 3 == 1) { s3.append(s2.substring(0, 1)); m += 1; } else if (4 * k % 3 == 2) { switch (s2.substring(0, 2)) { case "01": s3.append("1"); break; case "10": s3.append("2"); break; case "11": s3.append("3"); break; default: break; } m += 2; } for (int j = m; j < 4 * k;) { switch (s2.substring(j, j + 3)) { case "000": s3.append("0"); break; case "001": s3.append("1"); break; case "010": s3.append("2"); break; case "011": s3.append("3"); break; case "100": s3.append("4"); break; case "101": s3.append("5"); break; case "110": s3.append("6"); break; case "111": s3.append("7"); break; } j += 3; } // delete 0 // use delete(old is 0) or charAt if (s3.length() == 2 && s3.charAt(0) == '0') {// 0-->00-->delete 00-->notany System.out.println(s3.substring(1)); } else { int q = 0; while (s3.charAt(q) == '0') { q++; } String s = s3.toString(); System.out.println(s3.substring(q)); } } } } ~~~  当然本题也可以将2进制每12位转换为8进制，这里就不赘述了。 如有什么问题，欢迎留言。 祝君好运！

刚做了，蓝桥杯算法训练的最大最小公倍数一题，感觉考查的是数学了，哈哈。 时间限制：1.0s   内存限制：256.0MB 问题描述 已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。 输入格式 输入一个正整数N。 输出格式 输出一个整数，表示你找到的最小公倍数。 样例输入 9 样例输出 504 数据规模与约定 1 <= N <= 10^6。 **思路如下：** 1. n是奇数，那就最大的三个数相乘 2. n是偶数，得分两种情况了， ①如果n不是3的倍数，那就s=n*(n-1)*(n-3)---n与n-2同为偶数，故排除一个n-2； ②n是3的倍数，s=(n-1)*(n-2)*(n-3)，n与n-2同为偶数，排除n-2，但n与n-3均有3这个公约数，得排除n-3，那就用n-4么？多往后写几个数你就会发现这样下去根本不行。 所以只能用(n-1)*(n-2)*(n-3)。 代码如下 ~~~ import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in=new Scanner(System.in); long n=in.nextLong(); long s; if(n%2==1){ s=n*(n-1)*(n-2); } else{ if(n%3==0) s=(n-1)*(n-2)*(n-3); else s=n*(n-1)*(n-3); } System.out.println(s); } } ~~~ 但是上传测试出了小问题，分数只有60分，百思不得其解，网上查阅了很多，发现貌似这道题后台测试数据是错误的，(⊙o⊙)… 见 http://blog.csdn.net/u011669700/article/details/18702757 如有任何问题，欢迎留言。 祝君好运！

> 原文出处：[算法积累](http://blog.csdn.net/column/details/zxiaofan-algorithm.html) 作者：[u010887744](http://blog.csdn.net/u010887744) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # 算法积累 > 个人算法积累，部分算法学习于《程序员代码面试指南》，预计包括排序算法、栈和队列、链表问题、二叉树、递归和动态规划、字符串问题、大数据和空间限制、数组和矩阵问题等。所有代码都经测试通过，全部代码可通过个人github.zxiaofan.cn下载。