快排写法有误

[zhengzavan]

用 https://javaguide.cn/cs-basics/algorithms/10-classical-sorting-algorithms.html#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-5
是过不了 https://leetcode.cn/problems/sort-an-array/description/
因为有很多没有意义的交换

这里给出正确的代码，除了最后一个三元组外其他用例都能过

class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}

public int partition(int[] nums, int low, int high) {
  int pivot = nums[high];
  int left = low, right = high - 1;
  while (left <= right) {
    while (left <= right && nums[left] <= pivot) {
      left++;
    }
    while (left <= right && nums[right] > pivot) {
      right--;
    }

    if (left < right) {
      swap(nums, left, right);
      left++;
      right--;
    }
  }
  swap(nums, left, high);
  return left;
}

public void swap(int[] nums, int a, int b) {
  if(a == b) return;
  int temp = nums[a];
  nums[a] = nums[b];
  nums[b] = temp;
}

public void quickSort(int[] nums, int low, int high) {
  if(low < high) {
    int position = partition(nums, low, high);
    quickSort(nums, low, position - 1);
    quickSort(nums, position + 1, high);
  }
}

}

[Snailclimb]

public int partition(int[] nums, int low, int high) {
int pivot = nums[high];
int left = low, right = high - 1;
while (left <= right) {
while (left <= right && nums[left] <= pivot) {
left++;
}
while (left <= right && nums[right] > pivot) {
right--;
}

if (left < right) {
  swap(nums, left, right);
  left++;
  right--;
}

}
swap(nums, left, high);
return left;
}

public void swap(int[] nums, int a, int b) {
if(a == b) return;
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}

我看评论区的题解这个快排实现更好一些：

import java.util.concurrent.ThreadLocalRandom;

class Solution {

    public int[] sortArray(int[] a) {
        quick(a, 0, a.length - 1);
        return a;
    }

    void quick(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(a, left, right);
        quick(a, left, p - 1);
        quick(a, p + 1, right);
    }

    int partition(int[] a, int left, int right) {
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(a, left, idx);
        int pv = a[left];
        int i = left + 1;
        int j = right;
        while (i <= j) {
            while (i <= j && a[i] < pv) {
                i++;
            }
            while (i <= j && a[j] > pv) {
                j--;
            }
            if (i <= j) {
                swap(a, i, j);
                i++;
                j--;
            }
        }
        swap(a, j, left);
        return j;
    }

    void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}