最近百度实习生笔试题里考了这个,要求归并算法里空间复杂度为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),因为在合并过程中需要额外的空间来存储临时变量。
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(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),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,即相等的元素在排序后保持原有的相对顺序。 直接插入排序适用于待排序序列较小或基本有序的情况,因为它在处理小规模...
当n较大,则应采用时间复杂度为O(nlogn)的排序方法:快速排序、堆排序或归并排序。 时间复杂度:冒泡排序=选择排序=插入排序=O(N的平方);其他都是O(NlogN),但是并不是绝对的。 详细内容请见文档。
空间复杂度 快速排序 n^2 日志(n) 归并排序 日志 n n 冒泡排序 n^2 1 插入排序 n^2 1 选择排序 n^2 1 数据结构(最差) 算法 使用权 搜索 插入 删除 空间复杂度 大批 1 n n n n 哈希表 不适用 n (平均 1) n (平均 1)...