heap sort (examplehub#190)

realDuYuanChao · web-flow · commit ffd6ab474760 · 2021-11-03T15:08:37.000+08:00
* heap sort

* fixed heap sort
diff --git a/src/main/java/com/examplehub/sorts/HeapSort.java b/src/main/java/com/examplehub/sorts/HeapSort.java
@@ -0,0 +1,92 @@
+package com.examplehub.sorts;
+
+import com.examplehub.utils.SortUtils;
+
+public class HeapSort implements Sort{
+
+  @Override
+  public void sort(int[] numbers) {
+    heapInsert(numbers);
+    int length = numbers.length;
+    while (length > 1) {
+      SortUtils.swap(numbers, 0, --length);
+      heapify(numbers, 0, length);
+    }
+  }
+
+  public void heapInsert(int[] numbers) {
+    for (int i = 0; i < numbers.length; ++i) {
+      int currentIndex = i;
+      int parentIndex = (currentIndex - 1) / 2;
+      while (numbers[currentIndex] > numbers[parentIndex]) {
+        SortUtils.swap(numbers, currentIndex, parentIndex);
+        currentIndex = parentIndex;
+        parentIndex = (currentIndex - 1) / 2;
+      }
+    }
+  }
+
+  public void heapify(int[] numbers, int index, int length) {
+    int leftIndex = 2 * index + 1;
+    int rightIndex = 2 * index + 2;
+    while (leftIndex < length) {
+      int maxIndex = index;
+      if (numbers[leftIndex] > numbers[maxIndex]) {
+        maxIndex = leftIndex;
+      }
+      if (rightIndex < length && numbers[rightIndex] > numbers[maxIndex]) {
+        maxIndex = rightIndex;
+      }
+      if (maxIndex == index) {
+        break;
+      }
+      SortUtils.swap(numbers, maxIndex, index);
+      index = maxIndex;
+      leftIndex = 2 * index + 1;
+      rightIndex = 2 * index + 2;
+    }
+  }
+
+  @Override
+  public <T extends Comparable<T>> void sort(T[] array) {
+    heapInsert(array);
+    int length = array.length;
+    while (length > 1) {
+      SortUtils.swap(array, 0, --length);
+      heapify(array, 0, length);
+    }
+  }
+
+  public <T extends Comparable<T>>void heapInsert(T[] numbers) {
+    for (int i = 0; i < numbers.length; ++i) {
+      int currentIndex = i;
+      int parentIndex = (currentIndex - 1) / 2;
+      while (numbers[currentIndex].compareTo(numbers[parentIndex]) > 0) {
+        SortUtils.swap(numbers, currentIndex, parentIndex);
+        currentIndex = parentIndex;
+        parentIndex = (currentIndex - 1) / 2;
+      }
+    }
+  }
+
+  public <T extends Comparable<T>> void heapify(T[] numbers, int index, int length) {
+    int leftIndex = 2 * index + 1;
+    int rightIndex = 2 * index + 2;
+    while (leftIndex < length) {
+      int maxIndex = index;
+      if (numbers[leftIndex].compareTo(numbers[maxIndex]) > 0) {
+        maxIndex = leftIndex;
+      }
+      if (rightIndex < length && numbers[rightIndex].compareTo(numbers[maxIndex]) > 0) {
+        maxIndex = rightIndex;
+      }
+      if (maxIndex == index) {
+        break;
+      }
+      SortUtils.swap(numbers, maxIndex, index);
+      index = maxIndex;
+      leftIndex = 2 * index + 1;
+      rightIndex = 2 * index + 2;
+    }
+  }
+}
diff --git a/src/test/java/com/examplehub/sorts/HeapSortTest.java b/src/test/java/com/examplehub/sorts/HeapSortTest.java
@@ -0,0 +1,59 @@
+package com.examplehub.sorts;
+
+import com.examplehub.domain.Student;
+import com.examplehub.utils.RandomUtils;
+import com.examplehub.utils.SortUtils;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+import java.util.Arrays;
+
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+class HeapSortTest {
+
+  private Sort sort;
+
+  @BeforeEach
+  public void before() {
+    sort = new HeapSort();
+  }
+
+  @Test
+  void testSort() {
+    int[] ints = RandomUtils.randomInts(-50, 50, 100);
+    sort.sort(ints);
+    assertTrue(SortUtils.isSorted(ints));
+  }
+
+  @Test
+  void testSortIntegers() {
+    Integer[] integers =
+        Arrays.stream(RandomUtils.randomInts(-50, 50, 100)).boxed().toArray(Integer[]::new);
+    sort.sort(integers);
+    assertTrue(SortUtils.isSorted(integers));
+  }
+
+  @Test
+  void testSortedDoubles() {
+    Double[] doubles = new Double[100];
+    double[] tempDoubles = RandomUtils.randomDoubles(-50, 50, 100);
+    for (int i = 0; i < doubles.length; ++i) {
+      doubles[i] = tempDoubles[i];
+    }
+    sort.sort(doubles);
+    assertTrue(SortUtils.isSorted(doubles));
+  }
+
+  @Test
+  void testComparable() {
+    Student[] students = new Student[5];
+    students[0] = new Student(1, 98, 99, 100);
+    students[1] = new Student(2, 100, 99, 98);
+    students[2] = new Student(3, 100, 98, 99);
+    students[3] = new Student(4, 100, 100, 100);
+    students[4] = new Student(5, 99, 99, 99);
+    sort.sort(students);
+    assertTrue(SortUtils.isSorted(students));
+  }
+}
