最近百度实习生笔试题里考了这个,要求归并算法里空间复杂度为O(1),不能设置辅助数组
# include <stdio.h>
# define N 10
int binarySearch(int m,int* unsort ,int low,int high){
int mid;
while(low<=high){
mid=(low+high)/2;
if(unsort[mid]>m)
high=mid-1;
else if(unsort[mid]<m)
low=mid+1;
else return mid;
}
return low;
}
void merge(int * unsort,int low,int mid,int num){
int i,j,k,count=0,temp;
for(j=mid;j<num;j++)
{
i=binarySearch(unsort[j],unsort,low,mid+count-1);
temp=unsort[j];
for(k=j;k>i;k--){
unsort[k]=unsort[k-1];
}
unsort[i]=temp;
++count;
}
}
void main(){
int i,unsort[]={1,4,5,7,9,0,2,3,6,8};
merge(unsort,0,5,N);
for(i=0;i<N;i++)
printf("%d ",unsort[i]);
}
分享到:
相关推荐
O(1) 归并排序时间复杂度:O(nlogn) 空间复杂度:O(n) 计数反转时间复杂度:O(nlogn) 空间复杂度:O(n) 基于自顶向下归并排序。 唐叶乘法不打算实施这个。 施特拉森朴素矩阵乘法分治矩阵乘法时间复杂度:O(n^3) 空间...
空间复杂度 O(1) BubbleSort 冒泡排序 SelectionSort 选择排序 InsertionSort 插入排序 平均时间复杂度 O(n (log n)^2) 空间复杂度 O(1) ShellSort 希尔排序 | 优化版插入排序;多轮步长缩小的方式,步长为 x = x * ...
时间复杂度大小比较 在计算机科学中,时间复杂度用于描述算法执行时间随输入规模增长而变化的趋势。常见的时间复杂度包括O(1)、O...在实际应用中,还需要考虑算法的空间复杂度、实现细节以及硬件环境等因素。 此外,
直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,即相等的元素在排序后保持原有的相对顺序。 直接插入排序适用于待排序序列较小或基本有序的情况,因为它在处理小规模...
归并排序(Merge Sort)是一种采用分治法(Divide and Conquer)策略的排序算法。该算法首先将已有序的子序列合并,得到完全有序的...归并排序的空间复杂度是 O(n),因为在合并过程中需要额外的空间来存储临时变量。
归并排序具有稳定性好、时间复杂度低(O(n log n))的特点,但其需要额外的空间来存储合并过程中的临时数据,空间复杂度为O(n)。在Python中,归并排序可以通过递归和迭代两种方式实现,是一种广泛应用的排序算法。
Swift 实现快速排序最坏情况性能 O(n2) 最佳情况性能 O(n log n)(简单分区)或 O(n)(三路分区和等键) 平均案例表现 O(n log n) 最坏情况空间复杂度 O(n) 辅助(朴素) O(log n) 辅助归并排序最坏情况性能 ...
scau归并排序归并排序 归并排序:就是利用归并的思想,实现的排序方法。要实现归并排序,需要完成两个步骤。一是“分”,就是将数组分到原子级;二是“合”,将原子级别的元素两两排序,合并,最终...空间复杂度为O(n)
快速排序时间复杂度平均状态下O(NlogN),空间复杂度O(1),归并排序最坏情况下时间复杂度O(NlogN),空间复杂度O(N) 入门题目: Leetcode 148. Sort List Leetcode 56. Merge Intervals 进阶题目: Leetcode ...
归并排序的时间复杂度为O(nlogn),是一种稳定的排序算法,适用于各种规模的数据集。在Java实现中,归并排序通过递归调用mergeSortHelper方法将数组划分为更小的子数组,并在最后使用merge方法将有序子数组合并成一个...
直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,即相等的元素在排序后保持原有的相对顺序。 直接插入排序适用于待排序序列较小或基本有序的情况,因为它在处理小规模...
归并排序(Merge Sort)是一种采用分治法(Divide and Conquer)策略的排序算法。该算法首先将已有序的子序列合并,得到完全有序的...归并排序的空间复杂度是 O(n),因为在合并过程中需要额外的空间来存储临时变量。
空间复杂度 大批 O(n) O(n) O(1) O(n) O(n) 哈希集 O(1) O(1) - O(1) O(n) Big O Notation 中的排序算法 排序算法 最好的 平均数 最差 空间复杂度 选择排序 O(n^2) O(n^2) O(n^2) O(1) 冒泡排序 O(n^2) O(n^2) O(n^2...
1. 排序算法分类 排序算法可以分为 外部排序 和 内部排序: (1)外部排序 (External sorting)是指能够处理极大量数据的排序...需要额外内存空间(out-place,即空间复杂度不是O(1)O(1)O(1))的算法有:桶排序,基数
直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,即相等的元素在排序后保持原有的相对顺序。 直接插入排序适用于待排序序列较小或基本有序的情况,因为它在处理小规模...
2.通用数据结构操作:常见数据类型(数组、栈、队列、单链表、双向链表、哈希表、二叉搜索树、红黑树、B-树……)的增删改查操作的最好最坏时间复杂度,最坏空间复杂度 3.数组排序算法:快排、归并、堆排序、冒泡、...
## 九种内部排序算法的Java实现及其性能测试 ### 9种内部排序算法性能比较 第九种为java.util.Arrays.sort(改进的快速排序方法) ...复杂度:O(n^2) - O(n) - O(n^2) - O(1)[平均 - 最好 - 最坏 - 空间复杂度]
直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,即相等的元素在排序后保持原有的相对顺序。 直接插入排序适用于待排序序列较小或基本有序的情况,因为它在处理小规模...
直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,即相等的元素在排序后保持原有的相对顺序。 直接插入排序适用于待排序序列较小或基本有序的情况,因为它在处理小规模...
直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,即相等的元素在排序后保持原有的相对顺序。 直接插入排序适用于待排序序列较小或基本有序的情况,因为它在处理小规模...