leetcode 912.排序数组

⭐️ 题目描述

🌟 leetcode链接：排序数组

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

代码：

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;
}