使用 oh-my-zsh

912、排序数组

给你一个整数数组 nums，将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 50000
• -50000 <= nums[i] <= 50000

链接：https://leetcode-cn.com/problems/sort-an-array

题解

常见的排序算法：

• 快速排序
• 堆排序
• 归并排序
• 希尔排序
• 冒泡排序、鸡尾酒排序
• 插入排序、快速插入排序
• 选择排序

1、快速排序

• 随机选择一个数字，利用原地算法，按照这个数字将数组一分为二。

class Solution {
    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) return;
        int p = partition(nums,left,right);
        // System.out.println("p: "+p);
        quickSort(nums,left,p-1);
        quickSort(nums,p+1,right);
    }

    private int partition(int[] nums,int left,int right){
        // 移动大于p的数字
        // int p = nums[left];
        // int index = right;
        // for (int i = right;i >= left;i--){
        //     if (nums[i] > p) {
        //         int t = nums[i];
        //         nums[i] = nums[index];
        //         nums[index] = t;
        //         index--;
        //     }
        // }
        // 移动小于p的数字
        int p = nums[right];
        int index = left;
        for (int i = left;i <= right;i++){
            if (nums[i] < p) {
                int t = nums[i];
                nums[i] = nums[index];
                nums[index] = t;
                index++;
            }
        }
        int t = nums[index];
        nums[index] = nums[right];
        nums[right] = t;
        return index;
    }
}

2、堆排序

完全二叉树，根>左、右——>大顶堆；根<左、右——>小顶堆

class Solution {
    public int[] sortArray(int[] nums) {
        heapSort(nums);

    }
    // 对调整
    private void maxHeapify(int[] nums,int i,int len) {
        for (;(i << 1) + 1 <= len) {
            // 找出根、左、右那个最大
            int lson = (i << 1) + 1;
            int rson = (i << 1) + 2;
            int large = 0;
            if (lson <= len && nums[lson] > nums[i]) {
                large = lson;
            } else {
                large = i;
            }
            if (rson <= len && nums[rson] > nums[large]) {
                large = rson;
            }
            // 用i索引最大的元素
            if (large != i) {
                swap(nums,i,large);
                i = large;
            } else {
                break;
            }

        }
    }
    private void swap(int[] nums,int i,int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = nums[i];
    }
    private void buildMaxHeap(int[] nums.int len) {
        for (int i = len / 2;i >= 0;i--) {
            maxHeapify(nums,i,len);
        }
    }

    private void heapSort(int[] nums) {
        int len = nums.length - 1;
        buildMaxHeap(nums,len);
        for (int i = len;i >= 1;i--){
            // 将堆顶元素移动到最后一位
            swap(nums,i,0);
            // 堆的长度减1
            len -= 1;
            // 调整堆，确保最大的值在堆顶
            maxHeapify(nums,0,len);
        } 
    }
}

3、归并排序

二分递归+归并。

class Solution {
    int[] tmp;
    private void mergeSort(int[] nums,int l,int r) {
        if (l >= r) {return;}
        int mid = (l + r) >> 1;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid,r);
        int i = l,j = mid + 1;
        // 将数据从小到大放到新的空间
        int cnt = 0;
        while (i <= mid && j <= r) {
            if (nums[i] < nums[j]) {
                tmp[cnt++] = nums[i++];
            } else {
                tmp[cnt++] = nums[j++];
            }
        }
        while (i <= mid) {tmp[cnt++] = nums[i++];}
        while (j <= r) {tmp[cnt++] = nums[j++];}
        // 将数据从小到大放回原位
        for (i = 0;i < r - l + 1; i++) {
            nums[i + 1] = tmp[i];
        }
    }
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums,0,nums.lenght - 1);
        return nums;
    }
} 

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com