题解 | #排序#

此笔记仅用于本人记录。

NC140 排序
中等 通过率：34.98% 时间限制：1秒 空间限制：256M
知识点 排序
描述
给定一个数组，请你编写一个函数，返回该数组排序后的形式。

这题用题解里面教的快排真是快速有效容易记！

首先是数组里面取第一位数为中枢，快排思想不就是比中枢小的在中枢左边、比中枢大的在中枢右边嘛。

然后从中枢后一位开始遍历这部分数组（注意不是整个数组，因为是分治策略），只要遇到比中枢值小的数就交换这个数到中枢后n位，第一个比中枢小就和中枢后一位交换；第二个比中枢小就和中枢后两位交换；......第i位比中枢小就交换到中枢后第i位，这样遍历结束时，中枢后第一位到第i位都是比中枢小的数（但是他们没有大小排序，完全是乱序）。

最后将第i位和中枢（也就是此部分数组的第一位）交换，就完成了本轮中枢的快排要求————比中枢小的在中枢左边、比中枢大的在中枢右边。

接下来就是分治了。

import java.util.*;


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