912. 排序数组

查看题目

中等

数组

分治

桶排序

计数排序

基数排序

排序

堆

归并排序

高频

解法一：heap-sort

时间复杂度：O(n log n) | 空间复杂度：O(1) | 推荐使用

动画演示

数组值:

准备就绪 - 输入数组值（用逗号分隔），然后点击开始

代码实现

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

    public void heapSort(int[] nums) {
        int len = nums.length - 1;
        buildMaxHeap(nums, len);
        for (int i = len; i >= 1; --i) {
            swap(nums, i, 0);
            len -= 1;
            maxHeapify(nums, 0, len);
        }
    }

    public void buildMaxHeap(int[] nums, int len) {
        for (int i = len / 2; i >= 0; --i) {
            maxHeapify(nums, i, len);
        }
    }

    public 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;
            if (lson <= len && nums[lson] > nums[i]) {
                large = lson;
            } else {
                large = i;
            }
            if (rson <= len && nums[rson] > nums[large]) {
                large = rson;
            }
            if (large != i) {
                swap(nums, i, large);
                i = large;
            } else {
                break;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

时间复杂度：O(n log n)

空间复杂度：O(1)

算法思路：堆排序是一种基于比较的排序算法，它利用堆这种数据结构来进行排序。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。核心思想： 1. 构建最大堆：将待排序数组转换为最大堆结构，堆顶元素为最大值 2. 交换堆顶与末尾元素：将堆顶元素（最大值）与数组末尾元素交换，将最大值固定在数组末尾 3. 调整堆结构：将剩余的n-1个元素重新调整为最大堆 4. 重复步骤2和3，直到整个数组有序堆调整过程： - 从最后一个非叶子节点开始，自下而上、自右向左进行调整 - 对于每个节点，比较其与左右子节点的大小，将最大元素交换到父节点位置 - 递归调整受影响的子树复杂度分析： - 时间复杂度：O(n log n)，其中O(n)用于构建堆，O(n log n)用于n-1次堆调整 - 空间复杂度：O(1)，原地排序，只需要常数级别的额外空间

解法二：quick-sort

时间复杂度：O(n log n) | 空间复杂度：O(log n)

动画演示

数组值:

准备就绪 - 输入数组值（用逗号分隔），然后点击开始

代码实现

class Solution {
    public int[] sortArray(int[] nums) {
        randomizedQuicksort(nums, 0, nums.length - 1);
        return nums;
    }

    public void randomizedQuicksort(int[] nums, int l, int r) {
        if (l < r) {
            int pos = randomizedPartition(nums, l, r);
            randomizedQuicksort(nums, l, pos - 1);
            randomizedQuicksort(nums, pos + 1, r);
        }
    }

    public int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums, r, i);
        return partition(nums, l, r);
    }

    public int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] < pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

时间复杂度：O(n log n)

空间复杂度：O(log n)

算法思路：快速排序是一种分治算法，通过选择一个基准元素，将数组分为小于基准和大于基准的两部分，然后递归地对这两部分进行排序。核心思想： 1. 从数组中选择一个基准元素（pivot） 2. 将数组重新排列，使得所有小于基准的元素都在基准左边，所有大于基准的元素都在基准右边 3. 递归地对基准左边和右边的子数组进行快速排序优化点： - 随机选择基准元素，避免最坏情况 - 使用原地分区，减少空间复杂度复杂度分析： - 时间复杂度：平均O(n log n)，最坏O(n²)，但通过随机选择基准可以避免最坏情况 - 空间复杂度：O(log n)，递归调用栈的深度