题解 | #排序#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }

    private void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = partition(arr, start, end);
        quickSort(arr, start, mid - 1);
        quickSort(arr, mid + 1, end);
    }

    private int partition(int[] arr, int start, int end) {
        int pivot = arr[start];
        int left = start + 1;
        int right = end;

        while (left < right) {
            while (left < right && pivot >= arr[left]) {
                left++;
            }
            if (left != right) {
                swap(arr, left, right);
                right--;
            }


        }

        if (left == right && arr[right] >= pivot) {
            right--;
        }

        if (start != right) {
            swap(arr, start, right);
        }

        return right;
    }

    private void swap(int[] arr, int i, int j) {
        if (arr[i] == arr[j] || arr.length <= 2) {
            return;
        }


        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

}