[A] 添加冒泡、选择、插入、快速排序文章

coderbruis · coderbruis · commit 109a9e0c5912 · 2020-08-14T15:05:40.000+08:00
diff --git a/README.md b/README.md
@@ -14,6 +14,34 @@
 - [基数排序]()（待续）
 - [堆排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%A0%86%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md) 【更新中】
 
+## 排序算法总结
+
+| 排序名  |  平均时间复杂度   |    空间复杂度     |  优势  |  劣势  |           适用场景            | 稳定性  |
+| :--: | :------: | :----------: | :--: | :--: | :-----------------------: | :--: |
+| 冒泡排序 |  O(n^2)  |     O(1)     |      |      |                           |  稳定  |
+| 插入排序 |  O(n^2)  |     O(1)     |      |      |                           |  稳定  |
+| 计数排序 |          |     O(M)     |      |      | 对于用例少的数据，比如对人的年龄排序或者身高排序。 |  稳定  |
+| 基数排序 | O(d(n+r)) |     O(M)     |      |      |                           |  稳定  |
+| 桶排序  |          |              |      |      |                           |  稳定  |
+| 选择排序 |  O(n^2)  |     O(1)     |      |      |                           | 不稳定  |
+| 归并排序 | O(nlogn) |     O(N)     |      |      |                           |  稳定  |
+| 快速排序 | O(nlogn) | O(logn)~O(n) |      |      |                           | 不稳定  |
+| 希尔排序 | O(nlogn) |     O(1)     |      |      |                           | 不稳定  |
+| 堆排序  | O(nlogn) |     O(1)     |      |      |                           | 不稳定  |
+
+注意这里总结的都是平均时间复杂度，例如插入排序，如果是有序的数组，则时间复杂度会退化成O(n)。而快速排序，对于每次选择的p位置都是末尾位置，则会退化成时间复杂度为O(n^2)（通过让p的位置随机来解决这个问题）。
+对于归并排序、快速排序、堆排序这三个O(nlogn)的排序来说，时间复杂度是有常数级别的区别的，但是快速排序是相对更快的一种排序。
+
+这里还需要注意的是，对于插入排序、快速排序、堆排序来说，都是原地排序的，即不需要额外的空间；而归并排序则是非原地排序，需要借助额外空间。
+
+> 排序算法的稳定性：对于相等的元素，在排序后，原来靠前的元素依然靠前，相等元素的相对位置没有发生改变。
+
+> 除非面试题特别说明，否则认为要排序的数据范围是均匀分布的。
+
+> 快速排序之所以叫快速排序，并不代表它比堆排序和归并排序优良。在最好情况下，它的渐进复杂度与 堆排序和归并排序是相同的。知识快速排序的常量系数比较小而已。
+
+> 类库上提供的排序，并不是某一种算法的实现，而是综合了多种排序的综合排序。当数组比较小时，使用插入排序；当数组较大时，选择快速排序或其他的O(nlogn)的排序。
+
 # 经典算法
 
 - [KMP算法]()（待续） 
diff --git a/notes/algorithms/冒泡排序算法.md b/notes/algorithms/冒泡排序算法.md
@@ -0,0 +1,97 @@
+## 前言
+
+思路：每一趟遍历将最大元素冒泡到数组最后的位置；
+
+动态图
+
+![冒泡排序动态图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/bubbleSort.gif)
+
+- 时间复杂度：O(N^2)
+- 空间复杂度：O(1)
+- 稳定性：稳定
+
+## 正文
+
+### 1. 实现代码
+
+```
+public class BubbleSort {
+
+    // 方式;
+    public static void sort(int[] arr) {
+        int n = arr.length;
+        boolean swapped = false;
+
+        do {
+            swapped = false;
+            for (int i = 1; i < n; i++) {
+                if (arr[i - 1] > arr[i]) {
+                    swap(arr, i - 1, i);
+                    swapped = true;
+                }
+            }
+        } while(swapped);
+    }
+    
+    // 方式2
+    public static void sort2(int[] arr) {
+        int n = arr.length;
+
+        if (n <= 1) {
+            return;
+        }
+
+        // 使用newn来进行优化
+        int newn;
+
+        do {
+            newn = 0;
+            for (int i = 1; i < n; i++) {
+                if (arr[i - 1] > arr[i]) {
+                    swap(arr, i - 1, i);
+                    // 记录当前排序最后一次交换的位置，在此之后的元素在下一轮扫描中均不考虑
+                    newn = i;
+                }
+            }
+            n = newn;
+        } while (newn > 0);
+
+    }
+
+    // 方式3
+    public static void sort3(int[] arr) {
+        int n = arr.length;
+        if (n <= 1) {
+            return;
+        }
+
+        for (int i = 0; i < n; i++) {
+            boolean flag = false;
+
+            // n - i - 1 表示每轮排序都会有一个最大元素冒泡到最大位置，因而每轮排序都会少一个遍历的元素
+            for (int j = 0; j < n - i - 1; j++) {
+                if (arr[j] < arr[j + 1]) {
+                    swap(arr, j, j + 1);
+                    flag = true;
+                }
+            }
+            // 此轮排序没有数据交换，则退出排序
+            if (!flag) {
+                break;
+            }
+        }
+    }
+
+    public static void swap(int[] arr, int i, int j) {
+        int tmp = arr[i];
+        arr[i] = arr[j];
+        arr[j] = tmp;
+    }
+}
+```
+
+> 分析：对于方式一，由于每一趟排序都会将最大元素冒泡到最后一位，所以下一次排序就不用考虑最后一个位置的元素了，从而加速下一次排序的速度。代码中的方式2和方式3都是同样的优化思路。
+
+## 参考
+
+- [动态图参考](https://www.runoob.com/w3cnote/bubble-sort.html)
diff --git a/notes/algorithms/堆排序算法.md b/notes/algorithms/堆排序算法.md
@@ -6,10 +6,20 @@
 
 学完堆这种数据结构后，再来学堆排序，会简单的多。
 
+- 时间复杂度：O(NlogN)
+- 空间复杂度：O(1)
+- 稳定性：不稳定
+
 ## 正文
 
 ### 1. 借助辅助空间
 
 
 
-### 2. 原地堆排序
+### 2. 原地堆排序
+
+
+
+## 参考
+
+- [动态图参考](https://www.runoob.com/w3cnote/bubble-sort.html)
diff --git a/notes/algorithms/归并排序算法.md b/notes/algorithms/归并排序算法.md
@@ -13,6 +13,10 @@
 ![归并过程动态图](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)
 
+- 时间复杂度：O(NlogN)
+- 空间复杂度：O(N)
+- 稳定性：不稳定
+
 ## 正文
 
 ### 1.（自顶向下）归并排序算法
@@ -28,4 +32,10 @@
 除此之外，自底向上排序的算法不需要额外的空间，空间复杂度为O(1)。自底向上有一个非常重要的作用，它可以通过O(NlogN)的
 时间复杂度去对链表这种数据结构进行排序。
 
-**对链表进行O(NlogN)级别的排序**
+**对链表进行O(NlogN)级别的排序**
+
+
+
+## 参考
+
+- [动态图参考](https://www.runoob.com/w3cnote/bubble-sort.html)
diff --git a/notes/algorithms/快速排序算法.md b/notes/algorithms/快速排序算法.md
@@ -0,0 +1,61 @@
+## 前言
+
+
+- 时间复杂度：O(NlogN)
+- 空间复杂度：O(N)
+- 稳定性：稳定
+
+## 正文
+
+### 1. 代码实现
+
+```
+private int partition2(int[] nums, int lt, int gt) {
+	int p = nums[n];
+	int j = lt;
+	for(int i = lt; i <= gt; i++) {
+		if(nums[i] < p) {
+			swap(nums, ++j, i);
+		}
+	}
+	swap(nums, lt, j);
+	return j;
+}
+
+private int partition(int[] nums, int n, int m) {
+	int p = nums[n];
+	int j = n;
+	int k = m + 1;
+	int i = n + 1;
+	while(i < k) {
+		if(nums[i] < p) {
+			swap(nums, ++j, i++);
+		} else if(nums[i] > p) {
+			swap(nums, --k, i);
+		} else {// nums[i] == p
+			i++;
+		}
+	}
+	swap(nums, n, j);
+	return j;
+}
+private void swap(int[] nums, int n, int m) {
+	int tmp = nums[n];
+	nums[n] = nums[m];
+	nums[m] = tmp;
+}
+private void sort(int[] nums, int n, int m) {
+	if(n > m) {
+		return;
+	}
+	int p = partition(nums, n, m);
+	sort(nums, n, p - 1);
+	sort(nums, p + 1, m);
+} 
+public void sort(int[] nums) {
+	sort(nums, 0, nums.length);
+} 
+
+```
+
+## 参考
diff --git a/notes/algorithms/插入排序算法.md b/notes/algorithms/插入排序算法.md
@@ -0,0 +1,79 @@
+## 前言
+
+思路：插入排序就跟玩扑克牌一样，先把一部分牌给排好顺序，然后依次往后排剩下的牌，最终达到将所有牌都排序的效果。
+
+动态图
+
+![插入排序动态图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/insertionSort.gif)
+
+- 时间复杂度：O(N^2)
+- 空间复杂度：O(1)
+- 稳定性：稳定
+
+## 正文
+
+### 1. 代码实现
+
+```
+public class InsertionSort {
+    // 方式1
+    public static void sort(int[] arr) {
+        int n = arr.length;
+        for (int i = 0; i < n; i++) {
+            for (int j = i; j > 0; j--) {
+                // 注意这里j-1没有越界，因为j > 0进行了判断
+                if (arr[j] < arr[j-1]) {
+                    swap(arr, j, j-1);
+                } else {
+                    break;
+                }
+            }
+        }
+    }
+
+    // 方式2
+    public static void sort2(int[] arr) {
+        int n = arr.length;
+        for (int i = 0; i < n; i++) {
+            for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
+                // 注意这里j-1没有越界，因为j > 0进行了判断
+                swap(arr, j, j-1);
+            }
+        }
+    }
+
+    // 方式3，优化版
+    public static void sort3(int[] arr) {
+        int n = arr.length;
+        for (int i = 0; i < n; i++) {
+            // 获取需要比较的元素
+            int e = arr[i];
+            int j = i;
+            for (; j > 0 && e < arr[j-1] ; j--) {
+                // 如果满足条件，则前一位元素复制给后一位元素
+                arr[j] = arr[j-1];
+            }
+            // 跳出循环，则将需要比较的e元素替换到j位置，j位置即最终停留的位置
+            arr[j] = 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 [] arr = {6,2,1,5,4,3};
+        sort2(arr);
+        for (int n : arr) {
+            System.out.println(n);
+        }
+    }
+}
+```
+
+## 参考
+
+- [动态图参考](https://www.runoob.com/w3cnote/bubble-sort.html)
diff --git a/notes/algorithms/选择排序算法.md b/notes/algorithms/选择排序算法.md
@@ -0,0 +1,45 @@
+## 前言
+
+思路：依次寻找[i, n)区间里的最小值的索引。
+
+动态图
+
+![选择排序动态图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/selectionSort.gif)
+
+- 时间复杂度：O(N^2)
+- 空间复杂度：O(1)
+- 稳定性：不稳定
+
+## 正文
+
+### 1. 代码实现
+
+```
+public class SelectionSort {
+    
+    public static void sort(int[] arr) {
+        
+        int n = arr.length;
+
+        for (int i = 0; i < n; i++) {
+            int min = i;
+            for (int j = i+1; i < n; i++) {
+                if (arr[j] < arr[min]) {
+                    min = j;
+                }
+            }
+            swap(arr, i, min);
+        }
+    }
+
+    public static void swap(int[] arr, int i, int j) {
+        int tmp = arr[i];
+        arr[i] = arr[j];
+        arr[j] = tmp;
+    }
+}
+```
+
+## 参考
+
+- [动态图参考](https://www.runoob.com/w3cnote/bubble-sort.html)
diff --git a/src/main/java/com/bruis/algorithminjava/datastructures/heap/IndexMapHeap.java b/src/main/java/com/bruis/algorithminjava/datastructures/heap/IndexMapHeap.java
