添加冒泡排序和选择排序

coderbruis · web-flow · commit 07aab34bf418 · 2020-08-07T17:15:46.000+08:00
diff --git a/notes/algorithms/基础排序算法.md b/notes/algorithms/基础排序算法.md
@@ -7,8 +7,116 @@
 
 #### 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都是同样的优化思路。
+
 #### 2. 选择排序
 
+思路：依次寻找[i, n)区间里的最小值的索引。
+
+```
+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;
+    }
+}
+```
+
 #### 3. 插入排序
 
 #### 4. 归并排序
