update quicksort (examplehub#189)

realDuYuanChao · web-flow · commit d04f4fcc12a6 · 2021-11-02T19:34:57.000+08:00
diff --git a/src/main/java/com/examplehub/sorts/QuickSort.java b/src/main/java/com/examplehub/sorts/QuickSort.java
@@ -1,7 +1,5 @@
 package com.examplehub.sorts;
 
-import com.examplehub.utils.SortUtils;
-
 public class QuickSort implements Sort {
 
   @Override
@@ -11,18 +9,15 @@ public void sort(int[] numbers) {
 
   private int partition(int[] number, int left, int right) {
     int pivot = number[left];
-    while (left < right) {
-      while (left < right && number[right] >= pivot) {
+    while (left != right) {
+      while (left != right && number[right] >= pivot) {
         right--;
       }
-      while (left < right && number[left] <= pivot) {
-        left++;
-      }
-      if (left < right) {
-        SortUtils.swap(number, left, right);
+      number[left] = number[right];
+      while (left != right && number[left] <= pivot) {
         left++;
-        right--;
       }
+      number[right] = number[left];
     }
     number[left] = pivot;
     return left;
@@ -54,18 +49,15 @@ public <T extends Comparable<T>> void sort(T[] array) {
 
   private static <T extends Comparable<T>> int partition(T[] array, int left, int right) {
     T pivot = array[left];
-    while (left < right) {
-      while (left < right && array[right].compareTo(pivot) >= 0) {
+    while (left != right) {
+      while (left != right && array[right].compareTo(pivot) >= 0) {
         right--;
       }
-      while (left < right && array[left].compareTo(pivot) <= 0) {
+      array[left] = array[right];
+      while (left != right && array[left].compareTo(pivot) <= 0) {
         left++;
       }
-      if (left < right) {
-        SortUtils.swap(array, left, right);
-        left++;
-        right--;
-      }
+      array[right] = array[left];
     }
     array[left] = pivot;
     return left;
