【排序算法】希尔排序

2016-03-20

ORZ，似乎还能用
不是很符合希尔排序，对每组元素的排序不是严格的插入排序
嵌套了4层for…
下周看看能不能优化下

// ShellSort.cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <cassert>
using namespace std;

template <typename T>
void mySwap(T &a, T &b)
{
	T t(a);
	a = b;
	b = t;
}

template <typename T>
void mySwap(typename T::iterator *a, typename T::iterator *b)
{
	T t(*a);
	*a = *b;
	*b = t;
}

template <typename T>
void myDisplay(typename T::const_iterator begin, typename T::const_iterator end, ostream &os = std::cout)
{
	while (begin != end - 1)
	{
		os << *begin << " ";
		begin++;
	}
	os << *begin;
}


template <typename T>
int shellSort(vector<T> &data)
{
	typedef vector<T> container_type;
	typedef typename container_type::size_type container_size_type;
	container_size_type times = static_cast<container_size_type>(floor(log(data.size() + 1) / log(2)));
	// 分组间隔减少直到1，即所有数据分成1组
	for (container_size_type cnt = 1; cnt <= times; ++cnt)
	{
		container_size_type gap = static_cast<container_size_type>(pow(2, times - cnt + 1) - 1);
		// 对所有组进行逐组排序
		for (container_size_type i = 0; i < gap; ++i)
		{
			// 对当前组的元素a[j+n*gap]逐个进行排序
			for (container_size_type j = i; j < data.size(); j += gap)
			{
				// 比较当前元素a[j]与当前组其他元素a[j+n*gap]
				for (container_size_type k = j + gap; k < data.size(); k += gap)
				{
					if (data[j] > data[k])
					{
						mySwap(data[j], data[k]);
					}
				}
			}
		}
	}
	return 0;
}

int main()
{
	vector<int> data;
	int t;
	while (cin >> t)
	{
		data.push_back(t);
	}
	shellSort(data);
	myDisplay< vector<int> >(data.begin(), data.end());
#ifdef _DEBUG
	cin.get();
#endif
	return 0;
}

写了一个随机生成数据来测试算法正确性的函数模板，也顺便一起贴了吧

#include <random>
#include <limits>
template <typename T>
bool testSort(int (*func)(vector<T> &data), int times = 5, int amount = 1000, T rangeMin = std::numeric_limits<T>::min(), T rangeMax = std::numeric_limits<T>::max())
{
	typedef vector<T> container_type;
	typedef typename container_type::size_type container_size_type;

	default_random_engine generator;
	uniform_int_distribution<T> distribution(rangeMin, rangeMax);

	for (int i = 0; i <= times; ++i)
	{
		// start new turn
		container_type dataGroup;
		// generate test data group
		for (int j = 0; j < amount; ++j)
		{
			T random = distribution(generator); 
			dataGroup.push_back(random);
		}

		// test func
		func(dataGroup);

		// check sort result
		container_size_type len = dataGroup.size();
		if (len > 1)
		{
			for (container_size_type j = 1; j < len; ++j)
			{
				if (dataGroup[j - 1] > dataGroup[j])
				{
					// failed at some data
					cerr << "test failed at: " << endl;
					myDisplay< container_type >(dataGroup.begin(), dataGroup.end(), cerr);
					return false;
				}
			}
		}
	}
	clog << "pass all test" << endl;
	// pass all test
	return true;
}

int main()
{
    // for example
    assert( true == testSort<int>( shellSort ) );
}

Typecho插件：运行时间显示

2016-03-20

软件发布

之前看一些朋友博客上有，就自己写了一个~~并没有多少技术含量~~

插件效果图

效果就是本博客页脚这样，你也可以自己选择显示在页面的任意地方。

【排序算法】冒泡排序

2016-03-13

学习记录

无意翻出了以前写的排序
开个坑，用C++造轮子系列。。
为了凸显自己造轮子，不使用algorithm标准库

// 133.冒泡排序.cpp
// http://nanti.jisuanke.com/t/133

#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void mySwap(T &a, T &b)
{
    T t(a);
    a = b;
    b = t;
}

template <typename T>
void myDisplay(typename T::const_iterator begin, typename T::const_iterator end, ostream &os = std::cout)
{
	while (begin != end - 1)
	{
		os << *begin << " ";
		begin++;
	}
	os << *begin;
}

template <typename t>
int bubbleSort(vector<t> &data)
{
	int total = 0;
    int cnt = 0;
	do
	{
		typename vector<t>::size_type j = 0;
		cnt = 0;
		for (typename vector<t>::size_type i = 0; i < data.size() - 1 - j; i++)
		{
			if (data[i] > data[i + 1])
			{
				mySwap(data[i], data[i + 1]);
				cnt++;
			}
		}
		j++;
        total += cnt;
	} while (cnt > 0);
	return total;
}

int main()
{
	vector<int> data;
	int t;
	while (cin >> t)
	{
		data.push_back(t);
	}
	bubbleSort(data);
	myDisplay< vector<int> > (data.begin(), data.end());
	return 0;
}

记一次openwrt配置ss透明转发+DNS防污染

2016-03-04

技术实践

最近新入手了一款openwrt路由~
折腾好了ss，爽多了~ 再也不用每个设备都折腾一遍。。还有手机运行SS耗电爆表问题也因此解决。
记录一下。

[player url=’//static.moew.xyz/usr/uploads/music/九九八十一.mp3’ artist=’乐正绫’ title=’九九八十一’ origin=’http://music.163.com/#/m/song?id=404543406']
[lrc]
[00:59.00]上路巩州遇虎熊（熊山君，寅将军）
[01:01.00]五百年前一场疯腾宵又是孙悟空（孙悟空）
[01:05.00]失马鹰愁涧飞白龙（白龙马）
[01:07.00]沙河阻断路难通福陵山中收天蓬（沙和尚，猪八戒）
[01:11.00]岭上前行逆黄风（黄风怪）
[01:14.00]七星不照波月洞千年白骨化阴风（奎木狼，白骨精）
[01:18.00]鱼篮网通天一尾红（灵感大王）
[01:20.00]紫金葫芦二道童九尾老狐敢压龙（金、银角大王，压龙大仙）
[01:24.00]白虹坠雪浪击石碎
[01:27.00]思归难归堕回轮回
[01:30.00]月满一江水前世莫追（花果山水帘洞&金蝉子月满抛江）
[01:33.00]福泽聚宝象春风度不让洛阳（宝象国）
[01:36.00]玉面狐折兰香七绝崖上暗伏赤色大蟒（玉面狐狸，蟒蛇精）
[01:40.00]过西梁女儿国鸳鸯罗帐（西梁女国）
[01:43.00]与三道斗法相火云扬明枪易挡暗箭难防（车迟国，红孩儿）
[01:46.00]十方魔渴饮着我的脆弱
[01:49.00]凭你计法相迫逐个击破要你识我本色（唐僧）
[01:53.00]万里恶摧垮了我的沉默
[01:55.00]一肩担路坎坷我不说又何须旁人来嚼口舌（沙和尚）
[02:02.00]借扇翠云访罗刹（罗刹女【铁扇公主】）
[02:04.00]碧波潭内结亲宴招来九头的驸马（九头虫）
[02:08.00]雾隐金斑豹伸利爪（豹子精）
[02:10.00]城北黄狮盗钉耙白毛小鼠偷烛花（黄狮精，白鼠精）
[02:14.00]思乡未敢听琵琶
[02:16.00]摄魂曲后三股叉一朝命断美人画（蝎子精）
[02:21.00]六耳幻形难辨真假（六耳猕猴）
[02:23.00]太岁摇铃唤风沙玉兔抛绣高台搭（赛太岁，玉兔精）
[02:27.00]红霓垂九重紫云飞
[02:30.00]久归未归欲回恨回
[02:32.00]凡胎恰登对天命难违（天庭贬天蓬、卷帘二将）
[02:36.00]比丘走白鹿十三娘情丝缠缚（白鹿精，春十三娘【蜘蛛精】）
[02:39.00]乌袍君生百目庙前拦路自称黄眉老祖（蜈蚣精【百目怪】，黄眉老祖）
[02:43.00]将云拂孤直公对谈诗赋（拂云叟，孤直公）
[02:45.00]还未能抵天竺金平府钺斩红尘斧辟寒暑（辟寒大仙，辟暑大仙，辟尘大仙）
[02:49.00]众笔者嘲笑着我的贪得
[02:52.00]藏美酒有甚者谁却敢说自己放肆醉过
[02:56.00]休怪我这半生痴情煞多
[02:58.00]活一遭风流客慕娇娥但愿抱拥世间真绝色（猪八戒）
[03:04.00]【间奏】
[03:29.00]浮世千寻沫冲荡了我的轮廓
[03:32.00]纵身入尘埃里雷雨大作我也放声而歌
[03:36.00]方寸中方寸却不能定夺
[03:38.00]七十二般胆魄这次我决意不闪躲
[03:42.00]世尊如来佛诘问着我的执着
[03:45.00]当年我瑶池刻闹得痛快并未想过太多
[03:49.00]状罪责拿捏了我的业果
[03:51.00]可顽心不服错不思过齐天大圣地上行者（孙悟空）
[03:55.00]那传说忘却了我的寂寞
[03:58.00]英雄名不堪得何必较我混沌徒费口沫
[04:02.00]这人间毕竟我真正走过
[04:04.00]一途平九百波九千错凌云渡成正果但我
[04:08.00]有九九八十一种不舍
[/lrc]
[/player]

【人设】
猪八戒：洛天依
沙和尚：心华
孙悟空：乐正绫
唐僧：言和
白龙：乐正龙牙
熊山君：康师傅の海鲜面
寅将军：酥妃
奎木狼：镜音レン
白骨精：歌手音ピコ
灵感大王：司鼓君
压龙大仙：战音Lorra
金角大王：纳兰寻风
银角大王：墨兰花语
玉面狐狸：IA
赤色大蟒：MEIKO
女国国王：KAITO
红孩儿：猫村いろは
鹿力大仙：东方栀子
虎力大仙：SeeU
羊力大仙：佐藤ささら
铁扇公主：初音ミク
九头虫：神威がくぽ
金斑豹：SweetAnn
白毛鼠：心响（Kokone）
蝎子精：Vy2
六耳猕猴：绫彩音
玉兔精：GUMI
白鹿精：St
春十三娘：邪叫教主
百目怪：徵羽摩柯
黄眉老祖：Oliver
孤直公：小新Xin-Kun
杏仙：巡音ルカ
赤身鬼使：骸鸦
女国太师：INxico
老龟：乌龟Sui

【文章分享】Knowlegeable & Reading

2016-02-18

转载分享

从书店出来的时候，门口的大妈看着我抱了满怀的书，很不屑的看了我一眼：
“XXX小学没毕业也当了大老板，看这些书有什么用啊，还不如多打一份工。”
我笑了笑没有说话。这是幸存者偏差，你读过书就明白了。
我想起以前我的室友也用过这种眼神看过我：
“你读这些杂书，有什么用吗？”
我依然笑了笑什么都没说。你多读一本书，就少说一句求人的话。

Song - 「さくら ~あなたに出会えてよかった~」 - RSP

2016-02-08

转载分享

[player url=’//static.moew.xyz/usr/uploads/music/sakura.mp3’ artist=’RSP’ title=’さくら ~~あなたに出会えてよかった~~‘]
[lrc]
[00:06.050]さくらさくら会いたいよいやだ君に今すぐ会いたいよ
[00:11.930]だいじょうぶもう泣かないで私は风あなたを包んでいるよ
[00:18.000]
[00:18.050]さくらさくら会いたいよいやだ君に今すぐ会いたいよ
[00:23.800]ありがとうずっと大好き私は星あなたを见守り続ける
[00:30.880]あなたに出会えてよかった本当に本当によかった
[00:42.260]ここにもういれなくなっちゃったもう行かなくちゃホントゴメンね
[00:48.500]
[00:48.530]私はもう一人で远いところに行かなくちゃ
[00:54.280]どこへって闻かないでなんでって闻かないでホントゴメンね
[00:59.990]
[01:00.000]私はもうあなたのそばにいられなくなったの
[01:06.320]いつもの散歩道桜并木を抜けてゆき
[01:12.330]よく游んだ川面の上の空の光る方へと
[01:18.400]もう会えなくなるけど寂しいけど平気だよ
[01:23.580]生まれてよかったホントよかったあなたに出会ってよかった
[01:29.700]
[01:29.900]さくらさくら会いたいよいやだ君に今すぐ会いたいよ
[01:35.800]だいじょうぶもう泣かないで私は风あなたを包んでいるよ
[01:42.050]
[01:42.080]さくらさくら会いたいよいやだ君に今すぐ会いたいよ
[01:47.830]ありがとうずっと大好き私は星あなたを见守り続ける
[01:54.790]あなたに出会えてよかった本当に本当によかった
[02:06.310]あなたの帰りを待つ午后あなたの足音何げないこと
[02:12.010]私はそう一番の喜びを知りました
[02:18.410]あなたが话してくれたこと一日のこといろいろなこと
[02:24.020]私はそう一番の悲しみも知りました
[02:30.350]それはあなたの笑颜あなたの涙その优しさ
[02:36.220]私の名を呼ぶ声抱き缔める腕その温もり
[02:42.280]もう触れられないけど忘れないよ幸せだよ
[02:47.640]生まれてよかったホントよかったあなたに出会ってよかった
[02:53.900]
[02:54.530]さくらさくら会いたいよいやだ君に今すぐ会いたいよ
[03:00.320]だいじょうぶだよここにいる私は春あなたを抱く空
[03:06.570]さくらさくら会いたいよいやだ君に今すぐ会いたいよ
[03:12.440]ありがとうずっと大好き私は鸟あなたに歌い続ける
[03:24.660]桜の舞う空の彼方目を闭じれば心の
[03:42.530]さくらさくら会いたいよいやだ君に今すぐ会いたいよ
[03:48.660]いいんだよ微笑んでごらん私は花あなたの指先の花
[03:54.660]さくらさくら会いたいよいやだ君に今すぐ会いたいよ
[04:00.410]ありがとうずっと大好き私は爱あなたの胸に
[04:09.500]さくらさくら会いたいよいやだ君に今すぐ会いたいよ
[04:15.410]だいじょうぶもう泣かないで私は风あなたを包んでいるよ
[04:21.650]
[04:21.660]さくらさくら会いたいよいやだ君に今すぐ会いたいよ
[04:27.420]ありがとうずっと大好き私は星あなたを见守り続ける
[04:35.900]あなたに出会えてよかった本当に本当によかった
[04:46.960]本当に本当によかった
[/lrc]
[/player]

http://music.163.com/#/m/song?id=805197

『さくらさくら会いたいよいやだ君に今すぐ会いたいよ』
sakura, sakura/, aitaiyo/, iyada/, kimi ni ima/ sugu aitaiyo/
樱花，樱花，想见你，不要嘛，现在就想要见你

『だいじょうぶもう泣かないで私は风あなたを包んでいるよ』
daijoubu, mou/ nakanaide/, watashi wa kaze/, anata wo tsutsu/nde iru yo/
没关系，不要再哭了，我是风，正包围在你的身边

『さくらさくら会いたいよいやだ君に今すぐ会いたいよ』
sakura, sakura/, aitaiyo/, iyada/, kimi ni ima/ sugu aitaiyo/
樱花，樱花，想见你，不要嘛，现在就想要见你

『ありがとうずっと大好き私は星あなたを见守り続ける』 ※
arigatou/, zutto daisuki/, watashi wa hoshi/, anata wo mimamori/ tsudzukeru ※
谢谢，一直都最喜欢你，我是星星，会永远看着你守护着你 ※

『あなたに出会えてよかった本当に本当によかった』
anata ni deaete yokatta/, hontouni/ hontouni/ yokatta/
和你认识真好，真的真的是很好很好

『ここにもういれなくなっちゃったもう行かなくちゃホントゴメンね』
koko ni mou/ irenaku natcha/tta, mou/ ikanakucha/ honto gomen ne/
已经不能在这里了，已经不走不行了，真的对不起

『私はもう一人で远いところに行かなくちゃ』
watashi wa mou/hitori de too/ i tokoro ni ikanakucha/
我已经必须一个人要到远方去不得不走

『どこへ？って闻かないでなんで？って闻かないでホントゴメンね』
dokohe? tte ki/ kanaide nande? tte ki/ kanaide, honto gomen ne
到哪里？不要问好吗。为什么？不要问好吗，真的对不起

『私はもうあなたのそばにいられなくなったの』
watashi wa mou/ anata no soba ni i/ rarenaku natta no
我已经不能再在你的身边了

『いつもの散歩道桜并木を抜けてゆき』
itsumo no sanpomichi/, sakura namiki/, o nukete yuki
总是在散步道，樱花树并排的地方慢慢远去

『よく游んだ川面の上の空の光る方へと』
yoku asonda kawamo no/, ue no sora no/ hikaru kata e to
经常游戏的河面上的天空的光的方向去

『もう会えなくなるけど寂しいけど平気だよ』
mou aenaku narukedo/, sabishiikedo/, heikida yo
虽然已经不能见面了，虽然孤独，但是不要紧

『生まれてよかったホントよかったあなたに出会ってよかった』
umarete yokatta/, honto yokatta/, anata ni deaete yokatta
出生真好，真的很好，和你遇见真的很好

『※くり返し』
(※重复)

【欢迎欣赏】博客添加背景音乐√

2016-02-01

公告

↖ 看左上角
可以点击控制播放/暂停哟~

由以下项目及服务提供支持：

DIYgod/APlayer
又拍云存储

## 音乐来源音乐提取自B站视频《高考英语听力（九磅十五便士）》 AV号：2344795 UP主：黄普的战神

解决 git 的中文乱码

2016-02-01

折腾记录

起因于坑爹windows对Unicode的支持。。

设置I18N

i18n.commitencoding

这一条取决于你的commit信息编码，需要repo中所有人统一，一般是utf-8

1	git config --global i18n.commitencoding utf-8

i18n.logoutputencoding

这一条取选utf-8还是gbk取决于你的终端程序。。
windows的命令提示符是gbk
git-scm自带的bash是utf-8
其他shell/terminal请自行探索……

1	git config --global i18n.logoutputencoding utf-8/gbk

设置GIT GUI的界面编码

gui.encoding

这一条设置只为gui设置，不使用GUI而只用命令行的大佬可以略过下面一条

1	git config --global gui.encoding utf-8

解决近期B站播放器在Chrome 48+ 与 Flash 20.0 下出现乱码

2016-01-29

折腾记录

触发条件

复现此问题需要同时解锁下列4个条件：

√ Windows
√ Chrome Version 48+
√ Chrome DirectWrite 字体渲染（默认开启）
√ Flash Version 20.0+

发现过程

大概15年11月下旬就发现这个问题。

哔哩哔哩乱码

如图所示，就算输入英文都会显示成其他字母，。汉字更是乱七八糟
弹幕显示正常，正常发送弹幕出去后也是正确内容

当时是Chrome 49 64bit-Dev，在Flash更新到20.0后发现此问题
手工替换Flash回19.0就正常了，但又总是自动更新回去新版。。。

问群里的小伙伴，好像没人遇到这个问题，没人回应。。
去bilibili论坛反馈，说让换Chrome稳定版（当时大概version才46大概？），换稳定版试了试，可以正常工作。

本以为就此结束，等稳定版更新到49了这问题应该早就解决了。

然而，近来Chrome稳定版到了大概48，再次出现此问题。。

最近又问小伙伴们，遇到此问题的小伙伴多了一些。。
某人说关了DirectWrite渲染就好了，试了下果然没问题了。。。

解决方案

打开实验性功能控制页面（在地址栏输入chrome://flags/转到）
找到”停用DirectWrite”选项，点击启用

解决前应该是这样的：
未启用“停用DirectWrite”功能

解决后应该是这样的：
已启用“停用DirectWrite”功能

不知道算不算Bug，已经向Google提交了Feedback
涉及到三方也不知道谁的锅，向谁提交才对。。

UPDATE 1

最新版的Chrome已经更名为“DirectWrite(启用实验性DirectWrite字体渲染系统)”，因此需要将其置为“禁用”状态

听寒's Blog

【排序算法】希尔排序

Typecho插件：运行时间显示

【排序算法】冒泡排序

记一次openwrt配置ss透明转发+DNS防污染

Song - 「九九八十一」 - 乐正绫

【文章分享】Knowlegeable & Reading

Song - 「さくら ~あなたに出会えてよかった~」 - RSP

【欢迎欣赏】博客添加背景音乐√

由以下项目及服务提供支持：

解决 git 的中文乱码

设置I18N

i18n.commitencoding

i18n.logoutputencoding

设置GIT GUI的界面编码

gui.encoding

解决近期B站播放器在Chrome 48+ 与 Flash 20.0 下出现乱码

触发条件

发现过程

解决方案

UPDATE 1