织梦做企业网站,网站过期怎么找回来,app系统开发公司,水富县建设局网站⭐️ 题目描述 #x1f31f; leetcode链接#xff1a;排序数组
思路#xff1a; 此题如果使用冒泡插入选择这些时间复杂度 O ( N 2 ) O(N^2) O(N2) 的算法会超时#xff0c;使用快排 优化也过不去#xff0c;因为里面有一个测试用例全是 2 即使加了三数取中也会是 O (…⭐️ 题目描述 leetcode链接排序数组
思路 此题如果使用冒泡插入选择这些时间复杂度 O ( N 2 ) O(N^2) O(N2) 的算法会超时使用快排 优化也过不去因为里面有一个测试用例全是 2 即使加了三数取中也会是 O ( N 2 ) O(N^2) O(N2) 以下实现主要使用归并排序。如果需要其他排序的可以看我往期的排序详解✨ 七大经典比较排序算法
代码
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;
}
