[A]堆排序、归并排序算法；[U] 更新堆排序算法文章以及readme

coderbruis · coderbruis · commit 3b419617a649 · 2020-08-14T13:11:37.000+08:00
diff --git a/README.md b/README.md
@@ -4,29 +4,38 @@
 
 # 经典排序算法
 
-- [冒泡排序]() 
-- [选择排序]() 
-- [插入排序]() 
-- [归并排序]() 
-- [快速排序]() 
-- [希尔排序]() 
-- [桶排序]() 
-- [基数排序]() 
-
-# 经典数据结构
-
-- [数组]()
-- [栈和队列]()
-- [链表]()
-- [二分搜索树]()
-- [集合和映射]()
+- [冒泡排序]() （待续） 
+- [选择排序]()（待续）
+- [插入排序]()（待续）
+- [归并排序]()（待续）
+- [快速排序]()（待续）
+- [希尔排序]()（待续）
+- [桶排序]() （待续）
+- [基数排序]()（待续）
+
+# 经典算法
+
+- [KMP算法]()（待续） 
+- [马拉车算法]()（待续）
+- [Prim算法]()（待续）      
+- [Krusk]() （待续）
+- [Dijkstra算法]() （待续）
+- [Bellman-Ford算法]() （待续）
+            
+# 经典数据结构    
+            
+- [数组]()   （待续） 
+- [栈和队列]()（待续）
+- [链表]()（待续）
+- [二分搜索树]()（待续）
+- [集合和映射]()（待续）
 - [堆和优先队列](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/datastructures/%E5%A0%86%E5%92%8C%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97.md)
-- [线段树]()
-- [Trie树]()
-- [并查集]()
+- [线段树]() （待续）
+- [Trie树]() （待续）
+- [并查集]()（待续）
 - [AVL树](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/datastructures/AVL%E6%A0%91.md)
-- [红黑树]()
-- [哈希表]()
+- [红黑树]() （待续）
+- [哈希表]()（待续）
 
 # leetcode专区
 
diff --git a/notes/algorithms/基础排序算法.md b/notes/algorithms/基础排序算法.md
@@ -362,6 +362,13 @@ public void sort(int[] nums) {
 | 希尔排序 | O(nlogn) |     O(1)     |      |      |                           | 不稳定  |
 | 堆排序  | O(nlogn) |     O(1)     |      |      |                           | 不稳定  |
 
+注意这里总结的都是平均时间复杂度，例如插入排序，如果是有序的数组，则时间复杂度会退化成O(n)。而快速排序，对于每次选择的p位置都是末尾位置，则会退化成时间复杂度为O(n^2)（通过让p的位置随机来解决这个问题）。
+对于归并排序、快速排序、堆排序这三个O(nlogn)的排序来说，时间复杂度是有常数级别的区别的，但是快速排序是相对更快的一种排序。
+
+这里还需要注意的是，对于插入排序、快速排序、堆排序来说，都是原地排序的，即不需要额外的空间；而归并排序则是非原地排序，需要借助额外空间。
+
+> 排序算法的稳定性：对于相等的元素，在排序后，原来靠前的元素依然靠前，相等元素的相对位置没有发生改变。
+
 > 除非面试题特别说明，否则认为要排序的数据范围是均匀分布的。
 
 > 快速排序之所以叫快速排序，并不代表它比堆排序和归并排序优良。在最好情况下，它的渐进复杂度与 堆排序和归并排序是相同的。知识快速排序的常量系数比较小而已。
diff --git a/notes/algorithms/堆排序算法.md b/notes/algorithms/堆排序算法.md
@@ -0,0 +1,15 @@
+## 前言
+
+对于堆这种数据结构，详细讲解在这：
+
+[堆排序讲解](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/datastructures/%E5%A0%86%E5%92%8C%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97.md)
+
+学完堆这种数据结构后，再来学堆排序，会简单的多。
+
+## 正文
+
+### 1. 借助辅助空间
+
+
+
+### 2. 原地堆排序
diff --git a/notes/algorithms/归并排序算法.md b/notes/algorithms/归并排序算法.md
@@ -0,0 +1,31 @@
+## 前言
+
+归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
+
+作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
+
+- 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
+- 自下而上的迭代；
+
+
+归并排序算法是一个平均时间复杂度为O(NlogN)级别的算法，并且空间复杂度为O(N)级别。
+
+![归并过程动态图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/mergeSort.gif)
+![分治思想](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/1557906108-5066-20161218163120151-452283750.png)
+
+## 正文
+
+### 1.（自顶向下）归并排序算法
+
+自顶向下的特点就是——递归。
+
+### 2.（自顶向下）归并排序算法——优化
+
+### 3.（自低向上）归并排序算法
+
+自底向上的特点就是——迭代。
+
+除此之外，自底向上排序的算法不需要额外的空间，空间复杂度为O(1)。自底向上有一个非常重要的作用，它可以通过O(NlogN)的
+时间复杂度去对链表这种数据结构进行排序。
+
+**对链表进行O(NlogN)级别的排序**
diff --git a/notes/datastructures/堆和优先队列.md b/notes/datastructures/堆和优先队列.md
@@ -258,6 +258,128 @@ public class MaxHeap {
 heapify二叉堆化，即从最后一个非叶子节点开始siftDown，即图中蓝色图表示的节点元素。
 ![二叉堆图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/heap06.png)
 
+### 1.2 原地堆排序
+
+原地堆排序，就是指不需要借助额外的空间进行的排序。
+
+对于最大堆，数组中最大元素都存放在堆顶。每次排序将堆顶和数组最后一位元素进行swap操作，所以最后一位元素就是最大值，此时0~(n-2)就不是堆结构，即需要对
+0~(n-2)进行堆化，即将0位置的元素进行下沉操作，之后继续再对0~(n-2)作同样的操作。
+
+![二叉堆图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/heap07.png)
+
+```
+public class HeapSort {
+
+    public static void sort(int[] arr) {
+        int n = arr.length;
+
+        // 注意，此时我们的堆是从0开始索引的
+        // 从(最后一个元素的索引-1)/2开始
+        // 最后一个元素的索引 = n-1
+        // 其实这里 i = (n-1) 也行
+        for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
+            siftDown2(arr, n, i);
+        }
+
+        // [a.....v,k]
+        // [.......]k
+        // [.....] ba
+        for (int i = n-1; i > 0; i--) {
+            // 由于上面执行过下沉操作，所以已经是最大堆（但没有排序完）。所以此时swap就将最大值替换到数组末尾。
+            swap(arr, 0, i);
+            // 由于siftDown中是判断 2*k+1 < n ，所以就是对n-1进行下沉操作；
+            siftDown2(arr, i, 0);
+        }
+    }
+
+    // 下浮
+    public static void siftDown(int[] arr, int n, int k) {
+
+        while (2 * k + 1 < n) {
+            int j = 2 * k + 1;
+            if (j + 1 < n && arr[j+1] > arr[j]) {
+                j += 1;
+            }
+            if (arr[k] >= arr[j]) {
+                break;
+            }
+            swap(arr, k, j);
+            k = j;
+        }
+    }
+
+    /**
+     * 优化下沉过程, 不适用swap交换，通过赋值来代替。
+     *
+     * @param arr
+     * @param n
+     * @param k
+     */
+    private static void siftDown2(int[] arr, int n, int k) {
+
+        int e = arr[k];
+
+        while (2 * k + 1 < n) {
+            int j = 2 * k + 1;
+            if (j + 1 < n && arr[j + 1] > arr[j]) {
+                j++;
+            }
+
+            if (e >= arr[j]) {
+                break;
+            }
+            // 此时说明arr[j] > arr[k]; 所以让大值上浮;
+            arr[k] = arr[j];
+            k = j;
+        }
+        // 将最小元素替换到k的位置
+        arr[k] = e;
+    }
+
+    public static void swap(int[] arr, int i, int j) {
+        int tmp = arr[i];
+        arr[i] = arr[j];
+        arr[j] = tmp;
+    }
+
+    public static void main(String[] args) {
+/*
+        int n = 100;
+        int[] test = new int[n];
+        Random random = new Random();
+        for (int i = 0; i < n; i++) {
+            test[i] = random.nextInt(1000);
+        }
+*/
+        int n = 10;
+        int[] test = {10, 41, 30, 28, 16, 22, 13, 19, 17, 15};
+
+        sort(test);
+
+        for (int i = 1; i < n; i++) {
+            if (test[i-1] > test[i]) {
+                throw new IllegalArgumentException("Error!");
+            }
+        }
+    }
+}
+```
+
+### 1.3 索引堆
+
+对于我们所关心的这个通过数组实现的堆而言，数组中的元素位置发生了改变。正是因为这些元素的位置发生了改变，我们才能将其构建为最大堆。
+
+可是由于数组中元素位置的改变，我们将面临着几个局限性。
+
+ 1.如果我们的元素是十分复杂的话，比如像每个位置上存的是一篇10万字的文章。那么交换它们之间的位置将产生大量的时间消耗。（不过这可以通过技术手段解决）
+
+ 2.由于我们的数组元素的位置在构建成堆之后发生了改变，那么我们之后就很难索引到它，很难去改变它。例如我们在构建成堆后，想去改变一个原来元素的优先级（值），将会变得非常困难。
+
+可能我们在每一个元素上再加上一个属性来表示原来位置可以解决，但是这样的话，我们必须将这个数组遍历一下才能解决。（性能低效）
+
+针对以上问题，我们就需要引入索引堆（Index Heap）的概念。
+
+对于索引堆来说，我们将数据和索引这两部分分开存储。真正表征堆的这个数组是由索引这个数组构建成的。
 
 ## 2. 优先队列
 
diff --git a/notes/pictures/heap07.png b/notes/pictures/heap07.png
diff --git a/src/main/java/com/bruis/algorithminjava/algorithm/sort/MergeSortBU.java b/src/main/java/com/bruis/algorithminjava/algorithm/sort/MergeSortBU.java
@@ -0,0 +1,44 @@
+package com.bruis.algorithminjava.algorithm.sort;
+
+import java.util.Arrays;
+
+/**
+ *
+ * 归并排序（自底向上）
+ *
+ * @author LuoHaiYang
+ */
+public class MergeSortBU {
+    private static void merge(int[] arr, int left, int mid, int right) {
+        int[] aux = Arrays.copyOfRange(arr, left, right + 1);
+
+        int i = left, j = right + 1;
+        for (int k = 0; k <= right; k++) {
+            if (i > mid) {
+                arr[k] = aux[j - left];
+                j++;
+            } else if (j > right) {
+                arr[k] = aux[i - left];
+                i++;
+            } else if (aux[i - left] > aux[j - left]) {
+                arr[k] = aux[j - left];
+                j++;
+            } else {
+                arr[k] = aux[i - left];
+                i++;
+            }
+        }
+    }
+
+    // [a, b, c, d, e, f, g, h, i]
+    // [a,b]  [c,d] [e,f] [g,h]
+    public static void sort(int[] arr) {
+        int n = arr.length;
+
+        for (int sz = 1; sz < n; sz *= 2) {
+            for (int i = 0; i < n - sz; i += sz + sz) {
+                merge(arr, i, i+sz-1, Math.min(i+sz+sz-1, n-1));
+            }
+        }
+    }
+}
diff --git a/src/main/java/com/bruis/algorithminjava/datastructures/heap/IndexMapHeap.java b/src/main/java/com/bruis/algorithminjava/datastructures/heap/IndexMapHeap.java
diff --git a/src/main/java/com/bruis/algorithminjava/utils/SortTestHelper.java b/src/main/java/com/bruis/algorithminjava/utils/SortTestHelper.java
