⭐️ 题目描述
🌟 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
代码:文章来源地址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模板网!