学网站开发工作好找吗,常州网站建设培训,wordpress解析,我要自学网官网评判一个排序算法时除了时间复杂度和空间复杂度之外还要考虑对cache的捕获效果如何#xff0c;cache友好的排序算法应该对数据的访问相对集中#xff0c;快速排序相较于堆排序优点就是在于对cache的捕获效果好。 堆排序 时间复杂度#xff1a;O#xff08;n log n #xf… 评判一个排序算法时除了时间复杂度和空间复杂度之外还要考虑对cache的捕获效果如何cache友好的排序算法应该对数据的访问相对集中快速排序相较于堆排序优点就是在于对cache的捕获效果好。 堆排序 时间复杂度On log n 空间复杂度 O1 不稳定 cache不友好
void func(vectorintnums){functionvoid(int,int)merge[](int start,int end){int childstart;int father2*child1;while(childend){if(child1endnums[child1]nums[child]) child;if(nums[father]nums[child]){swap(nums[father],nums[child]);childfather;father2*child1;}else break;}};int nnums.size();for(int in/2-1;i0;i--){merge(i,n-1);}for(int in-1;i0;i--){swap(nums[0],nums[i]);merge(0,i-1);}
}快速排序 时间复杂度On log n- O(n^2) 空间复杂度 O1 cache友好
void func(vectorintnums,int start,int end){if(startend) return;int sstart-1;int eend1;int valnums[start];//这里选值可以优化int indexstart;while(indexe){if(nums[index]val) {index;}else if(nums[index]val){swap(nums[index],nums[s]);index;}else swap(nums[index],nums[--e]);}func(nums,start,s);func(nums,e,end);
}归并排序 时间复杂度 On log n 空间复杂度 On cache友好
void func(vectorintnums,int start,int end){if(startend) return;int mid(startend)/2;func(nums,start,mid);func(nums,mid1,end);vectorinttmp(end-start1);int start1start,start2mid1;int index0;while(start1midstart2end){int val1start1mid?nums[start1]:INT_MAX;int val2start2end?nums[start2]:INT_MAX;if(val1val2) tmp[index]nums[start2];else tmp[index]nums[start1];}for(int istart;iend;i) nums[i]nums[i-start];
}选择排序 时间复杂度 On^2 空间复杂度 O1 cache不友好
void func(vectorintnums){int nnums.size();for(int i1;in;i){int index0;for(int j0;jn-i;j){if(nums[index]nums[j]) indexj;}swap(nums[index],nums[n-i]);}
}插入排序 时间复杂度 On^2 空间复杂度 O1 cache友好
void func(vectorintnums){int nnums.size();for(int i1;in;i){int valnums[i],ji-1;while(j0nums[j]val){nums[j1]nums[j--];}nums[j1]val;}
}冒泡排序 时间复杂度 On^2 空间复杂度 O1 cache不友好
void func(vectorintnums){int nnums.size();for(int i0;in;i){bool btrue;for(int ji1;jn;j){if(nums[i]nums[j]) {bfalse;swap(nums[i],nums[j]);}}if(b) break;}
}
