题解 | #排序#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */

    public int[] MySort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }

    private void quickSort(int[] array, int start, int end) {
        //如果左右指针没有相交则执行
        if (start < end) {
            //记录中枢
            int k = array[start];
            //i指针指向当前要交换的位置（即遍历到比中枢值小的数，要交换该数到这个位置）
            int i = start;
            for (int j = start + 1; j <= end; j++) {
                //遇到小于中枢的值要交换到前面
                if (array[j] < k) {
                    swap(array, j, ++i);
                }
            }
            array[start] = array[i];
            array[i] = k;
            quickSort(array, start, i - 1);
            quickSort(array, i + 1, end);
        }
    }
    //交换两个数的值
    public void swap(int[] arr, int j, int i) {
        //防止出现两个相同的数想异或结果为0
        if (i != j) {
            arr[i] ^= arr[j];
            arr[j] ^= arr[i];
            arr[i] ^= arr[j];
        }

    }


}