leetcode 912.排序数组

这篇具有很好参考价值的文章主要介绍了leetcode 912.排序数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

⭐️ 题目描述

leetcode 912.排序数组,刷题,排序,leetcode,算法,刷题


🌟 leetcode链接:排序数组

思路: 此题如果使用冒泡插入选择这些时间复杂度 O ( N 2 ) O(N^2) O(N2) 的算法会超时,使用快排 + 优化也过不去,因为里面有一个测试用例全是 2 即使加了三数取中也会是 O ( N 2 ) O(N^2) O(N2) ,以下实现主要使用归并排序。如果需要其他排序的可以看我往期的排序详解✨ 七大经典比较排序算法

代码:文章来源地址https://www.toymoban.com/news/detail-626645.html

void mergeSort (int * nums , int begin , int end , int* temp) {
    // 区间不存在
    if (begin >= end) {
        return;
    }

    int midIndex = (begin + end) >> 1;
    mergeSort(nums , begin , midIndex , temp);
    mergeSort(nums , midIndex + 1 , end , temp);

    int leftBegin = begin;
    int leftEnd = midIndex;
    int rightBegin = midIndex + 1;
    int rightEnd = end;
    int i = begin;
    while (leftBegin <= leftEnd && rightBegin <= rightEnd) {
        if (nums[leftBegin] < nums[rightBegin]) {
            temp[i++] = nums[leftBegin++];
        } else {
            temp[i++] = nums[rightBegin++];
        }
    }

    while (leftBegin <= leftEnd) {
        temp[i++] = nums[leftBegin++];
    }

    while (rightBegin <= rightEnd) {
        temp[i++] = nums[rightBegin++];
    }

    // 拷贝
    memcpy(nums + begin , temp + begin , sizeof(int) * (end - begin + 1));
}

int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    // 直接归并排序秒杀
    int * temp = (int*)malloc(sizeof(int) * numsSize);

    mergeSort(nums , 0 , numsSize - 1 , temp);

    free(temp);

    return nums;
}

到了这里,关于leetcode 912.排序数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包