↓ 跳过正文
  1. Posts/

C++ sort学习笔记

·377 字·1 分钟

回想起大一的时候打cf…那个时候对C++还不怎么熟悉。。。用sort不会自定义排序方式。。

于是手写快排。。。直接取中间元素没加随机化。。。跪了。。。

后来知道sort怎么写以后。。发现sort是可以通过的。。。

于是我就一直以为sort是带随机化的快排。。。

然而实际上是:

sort在数据量比较大的时候用quick_sort…当分段后的数据量小于某个门槛,为了避免对此递归带来的额外负担。。采取插入排序的策略。。

std::sort 的混合策略

以及。。。快排在最快情况下还是会到达平方的复杂度。。。

于是有人发明了introsort…中文翻译叫内省排序。。。?

维基百科_introsort

这个算法其实就是。。对于数据量大的时候。。。一开始还是快排。。。但是当递归深度过深时。。用堆排。。。

据说现在的STL一般都是用了introsort….

相关文章

cpp vector学习笔记

·785 字·2 分钟
起因是百度实习二面的时候被问了一道类似这样的题: 给我下面的代码,问有没有什么问题。 1/* *********************************************** 2Author :111qqz 3Created Time :2017年02月28日 星期二 14时49分37秒 4File Name :vector.cpp 5************************************************ */ 6#include <cstdio> 7#include <vector> 8#include <ctime> 9using namespace std; 10int func( int x ) //此处函数的条件是不单调...这样才可以触发问题. 11{ 12 return (x-50)*(x-50)+1; 13} 14int main() 15{ 16 17 vector<int>vec; 18 int *pint = NULL; 19 for ( int i = 0 ; i < 100 ; i++) 20 { 21 int x = func(i); 22 vec.push_back(x); 23 if (x<500) 24 { 25 pint = & vec[0]; 26 } 27 } 28 if (pint) 29 *pint = 0 ; 30 int siz = vec.size(); 31 for ( int i = 0 ; i < siz ; i++) printf("%d\n",vec[i]); 32 return 0; 33} 面试的时候只给了部分代码,func函数没有给出。

c++11 学习笔记

·172 字·1 分钟
昨天终于搞定了ycm对c++11的支持…. 嘛,17都快出来了,我竟然连11都不会用。 不过突然把所有的11特性给我也没办法全部吸收。 所以在这里记录下用过的c++11的用法。

c语言中static的作用

·185 字·1 分钟
一般有两个 1static int a; 2int b; 3void func(void) 4{ 5 static int c=0; 6 int d; 7} 在这里,a与b都是全局变量,二者的区别是,b可以被别的文件使用,a只能在本文件中使用,这是static对全局变量的作用。 ** c和d的区别是,d是一个自动变量,func函数执行完后,d会自动被释放。但c却不会被释放,下一次调用func函数时,c的值会保留上次的值继续使用(而不是初始值0,初始化只会在函数第一次被调用的时候执行)**

0x3f3f3f3f...编程中无穷大常量的设置技巧

·1368 字·3 分钟
如果问题中各数据的范围明确,那么无穷大的设定不是问题,在不明确的情况下,很多程序员都取0x7fffffff作为无穷大,因为这是32-bit int的最大值。如果这个无穷大只用于一般的比较(比如求最小值时min变量的初值),那么0x7fffffff确实是一个完美的选择,但是在更多的情况下,0x7fffffff并不是一个好的选择。

manjaro安(zhe)装(teng)记

·730 字·2 分钟
噫。。之前x200上装的是win7+fedora25 gnome。。。 虽然感觉gnome对于09年的老电脑来说有点吃力…不过也懒得换.. 结果硬盘挂了2333 于是换了块硬盘