排序算法

912. 排序数组

（1）堆排序

class Solution {
    public int[] sortArray(int[] nums) {
        headSort(nums,nums.length);
        for (int num : nums) {
            System.out.println(num);
        }
        return null;
    }
    private void headSort(int[]arr,int n){
        //建堆
        for(int i=n/2-1;i>=0;i--){
            heapify(arr,n,i);
        }
        //排序
        for(int i=n-1;i>0;i--){
            //交换堆顶元素和数组最后一个元素
            swap(arr,0,i);
            //维护堆顶性质
            heapify(arr,i,0);
        }
    }
    //先堆化，构建一个大顶堆；n表示数组长度，i表示待维护的节点下标
    private void heapify(int[]arr,int n,int i){
        int largest=i;
        int leftSon=2*i+1;
        int rightSon=2*i+2;
        if(leftSon<n&&arr[largest]<arr[leftSon]){
            largest=leftSon;
        }
        if(rightSon<n&&arr[largest]<arr[rightSon]){
            largest=rightSon;
        }
        //如果最大的不是下标i了，那就需要交换数组的元素
        if(largest!=i){
            swap(arr,largest,i);
            //交换以后，递归维护子孩子堆的性质
            heapify(arr,n,largest);
        }
    }
    //交换数组元素
    private void swap(int[]arr,int left,int right){
        int temp=arr[left];
        arr[left]=arr[right];
        arr[right]=temp;
        return;
    }
}

（2）归并排序

package _12codetop._912sortArray;
//归并排序
class Solution2 {
    public int[] sortArray(int[] nums) {
        int[]temp=new int[nums.length];
        split(nums,0,nums.length-1,temp);
        return nums;
    }
    //先分割
    private void split(int[] nums, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            split(nums, left, mid, temp);
            split(nums, mid + 1, right, temp);
            merge(nums,left,mid,right,temp);
        }
    }
    //合并
    private void merge(int[] nums, int left, int mid, int right, int[] temp) {
        int l = left;
        int r = mid + 1;
        int index = 0;
        while (l <= mid && r <= right) {
            if (nums[l] >= nums[r]) {
                temp[index++] = nums[r++];
            } else {
                temp[index++] = nums[l++];
            }
        }
        if (r > right) {
            while (l <= mid) {
                temp[index++] = nums[l++];
            }
        } else if (l > mid) {
            while (r <= right) {
                temp[index++] = nums[r++];
            }
        }
        //最后把temp中的元素，复制到nums数组中
        int tempLeft = left;
        index=0;
        while (tempLeft<=right){
            nums[tempLeft++]=temp[index++];
        }
    }
}

（3）快速排序

//快速排序
class Solution3 {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    private void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int mid = partition(nums, left, right);
            quickSort(nums, left, mid - 1);
            quickSort(nums, mid + 1, right);
        }
    }
    private int partition(int[] nums, int left, int right) {
        //以最右节点为基准点
        int pivot = nums[right];
        int i = left;
        //j是一个fast指针，如果扫描到有小于pivot的数，就交换ij
        for (int j = left; j < right; j++) {
            if (nums[j] < pivot) {
                //让i的指针往前移动一格
                swap(nums, i++, j);
            }
        }
        //遍历完成以后，需要交换i与right的元素，然后返回i的索引位置
        swap(nums, i, right);
        return i;
    }
    private void swap(int[] nums, int left, int right) {
        int temp = nums[right];
        nums[right] = nums[left];
        nums[left] = temp;
        return;
    }
}