Initial commit

guaong · guaong · commit b0387ea33a4d · 2020-09-14T19:48:04.000+08:00
diff --git a/.idea/misc.xml b/.idea/misc.xml
diff --git a/.idea/modules.xml b/.idea/modules.xml
diff --git a/Algorithm.iml b/Algorithm.iml
@@ -0,0 +1,11 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<module type="JAVA_MODULE" version="4">
+  <component name="NewModuleRootManager" inherit-compiler-output="true">
+    <exclude-output />
+    <content url="file://$MODULE_DIR$">
+      <sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
+    </content>
+    <orderEntry type="inheritedJdk" />
+    <orderEntry type="sourceFolder" forTests="false" />
+  </component>
+</module>
diff --git a/src/sort/BubbleSort.java b/src/sort/BubbleSort.java
@@ -0,0 +1,31 @@
+package sort;
+
+/**
+ * 冒泡排序
+ */
+public class BubbleSort {
+
+    public static void main(String[] args) {
+        int[] arr = {2, 12, 43, 56, 32, 12, 14};
+        BubbleSort.sort(arr);
+    }
+
+    public static void sort(int[] arr) {
+        // 记录已经排过序的位置,即每次可以少比较一次
+        int end = arr.length;
+        // 每次取一个和其他比较
+        for (int k = 0; k < arr.length; k++) {
+            for (int i = 1; i < end; i++) {
+                // 小则交换位置
+                if (arr[i - 1] > arr[i]) {
+                    int temp = arr[i];
+                    arr[i] = arr[i - 1];
+                    arr[i - 1] = temp;
+                }
+            }
+            end--;
+        }
+        for (int i : arr) System.out.print(i + " ");
+    }
+
+}
diff --git a/src/sort/InsertionSort.java b/src/sort/InsertionSort.java
@@ -0,0 +1,28 @@
+package sort;
+
+/**
+ * 直接插入排序
+ */
+public class InsertionSort {
+
+    public static void main(String[] args) {
+        int[] arr = {1,4,56,3,12,54,76,98,100,98,12,13,87,5,3,23};
+        InsertionSort.sort(arr);
+    }
+
+    public static void sort(int[] arr){
+        // 从下标为1的开始
+        for (int i = 1; i < arr.length; i++){
+            // 只考虑已插入的,即之和下标i之前的已经排序好的比较
+            for (int j = i; j > 0; j--){
+                if (arr[j] < arr[j-1]){
+                    int temp = arr[j];
+                    arr[j] = arr[j-1];
+                    arr[j-1] = temp;
+                }
+            }
+        }
+        for (int i:arr) System.out.print(i + " ");
+    }
+
+}
diff --git a/src/sort/MergeSort.java b/src/sort/MergeSort.java
@@ -0,0 +1,62 @@
+package sort;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * 归并排序
+ * 没有考虑性能,使用了list
+ */
+public class MergeSort {
+
+    public static void main(String[] args) {
+        List<Integer> arr = new ArrayList<>();
+        for (int i = 0; i < 1000; i++){
+            arr.add((int)(Math.random()*1000));
+        }
+        MergeSort.merge(arr, 0, arr.size() - 1);
+        System.out.println(arr);
+    }
+
+    // 分治
+    public static void merge(List<Integer> arr, int left, int right){
+        // 如果left == right说明已经不可再分割
+        if (left == right) return;
+        // 获取中间的下标
+        int mid = (left + right) / 2;
+        // 数组左半部分再分治
+        merge(arr, left, mid);
+        // 数组右半部分再分治
+        merge(arr, mid + 1, right);
+        // 进行排序
+        sort(arr, left, mid, right);
+    }
+
+    public static void sort(List<Integer> arr, int left, int mid, int right){
+        // 标记位.当前一个right的元素已经插入到left的某一位flag,
+        // 则表示该位flag之前的left中的元素对于其他right中的其他元素都不需要再进行无意义的比较
+        // 因为right的剩余元素恒大于flag之前的元素
+        int flag = left;
+        // 标记位,用于记录动态变化中的left中最后一个元素下标
+        // 因为right中的元素插入到left中会使原mid对应的元素后移
+        int fakeMid = mid;
+        for (int i = mid + 1; i <= right; i++){ // 从right中依次取出一个
+            for (int j = flag; j <= fakeMid; j++){ // 将right中的元素和left中的每个元素比较
+                if (arr.get(i) < arr.get(j)){
+                    Integer remove = arr.remove(i);
+                    arr.add(j,remove);
+                    // 原mid对应元素后移一位
+                    fakeMid++;
+                    // 记录right中元素插入位置,下一个right中元素从该位置和left中元素开始比较
+                    flag = j;
+                    break;
+                }
+                flag = j;
+            }
+            // 如果right中某个元素比left中所有元素都大,则表示其后的right的元素恒大于left中元素
+            // 则不需要再进行排序
+            if (flag > fakeMid) break;
+        }
+    }
+
+}
diff --git a/src/sort/QuickSort.java b/src/sort/QuickSort.java
@@ -0,0 +1,70 @@
+package sort;
+
+/**
+ * 快速排序 没有达到要求
+ */
+public class QuickSort {
+
+    public static void main(String[] args) {
+        int[] arr = {2, 3, 24, 123, 333, 445, 521, 663, 723, 856, 1765, 3312};
+//        for (int i = 0; i < 100; i++) arr[i] = (int)(Math.random()*100);
+        long start = System.currentTimeMillis();
+        QuickSort.merger(arr, 0, arr.length - 1);
+        for (int i : arr
+        ) {
+            System.out.print(i + " ");
+        }
+        System.out.println("\n时长:" + (System.currentTimeMillis() - start));
+    }
+
+    private static void merger(int[] arr, int left, int right) {
+        // 递归到剩余一个时停止递归
+        // 由于会出现left = flag(flag左侧没有任何元素),因此merger(arr, left, flag - 1)会导致left > right的情况出现
+        if (left >= right) return;
+        // 每次以第一个值为flag
+        int flag = left;
+        // 用于交换位置的临时变量
+        int temp;
+        // 会变化的left,right
+        // 即currentLeft的左边的值已经和flag比较过,并且一定小于flag的值
+        // 所以下一轮比较就可以不再重复比较了,直接从currentLeft开始比较
+        int currentLeft = left;
+        int currentRight = right;
+        while (currentLeft + 1 >= flag && currentRight - 1 >= flag) {
+            // 从后向前找第一个比temp小的
+            int i = currentRight;
+            while (i >= flag) {
+                if (arr[flag] > arr[i]) {
+                    temp = arr[i];
+                    arr[i] = arr[flag];
+                    arr[flag] = temp;
+                    flag = i;
+                    // -- 和 =i 一样
+                    currentRight--;
+                    break;
+                }
+                // 不符合就左移
+                currentRight = i;
+                i--;
+            }
+            // 从前向后找第一个比temp大的
+            int j = currentLeft;
+            while (j < flag) {
+                if (arr[flag] < arr[j]) {
+                    temp = arr[j];
+                    arr[j] = arr[flag];
+                    arr[flag] = temp;
+                    flag = j;
+                    // ++ 和 =j 一样
+                    currentLeft++;
+                    break;
+                }
+                // 不符合就右移
+                currentLeft = j;
+                j++;
+            }
+        }
+        merger(arr, left, flag - 1);
+        merger(arr, flag + 1, right);
+    }
+}
diff --git a/src/sort/SelectionSort.java b/src/sort/SelectionSort.java
@@ -0,0 +1,27 @@
+package sort;
+
+/**
+ * 选择排序
+ */
+public class SelectionSort {
+
+    public static void main(String[] args) {
+        int[] arr = {1,3,4,2,5,6,11,77,32,98,666,78,54,32,45,2};
+        SelectionSort.sort(arr);
+    }
+
+    public static void sort(int[] arr){
+        for (int i = 0; i < arr.length; i++){
+            // 用于记录每次最小值的下标
+            int index = i;
+            for (int j = i+1; j < arr.length; j++){
+                if (arr[index] > arr[j]) index = j;
+            }
+            int temp = arr[index];
+            arr[index] = arr[i];
+            arr[i] = temp;
+        }
+        for (int i:arr) System.out.print(i + " ");
+    }
+
+}
diff --git a/src/tree/Tree.java b/src/tree/Tree.java
