shell排序初探-byMATLAB

本文既是对这些天摸索shell排序相关的规律的记述，也是对寒假学习MATLAB经历的简单总结。在学习方法、程序设计、数据处理及可视化等方面肯定有诸多不足，恳请指出。

起初，学习MATLB是为了应对美赛的需要，通过MOOC《数学实验》了解了基本的学习框架，并通过自学教材接触了常用的编程指令。可惜水平太次，既没有写出可以解决问题的程序（在此膜拜两位编程大佬[抱腿.jpg]），也没能在数据处理方面省时省力。

美赛后对此坑队友的现象进行反省，认为是练习过少所致。考虑到编程零基础的现状捉襟见肘的MATLAB水平，计划选择一些入门级的程设小题目练手。

在做题的过程中，见到这样几道题：

【程序15】

题目：输入三个整数x,y,z，请把这三个数由小到大输出。

【程序28】

题目：对10个数进行排序

【程序30】

题目：有一个已经排好序的数组。现输入一个数，要求按原来的规律将它插入数组中。

怎么看都是一类题呀。。。在自己造了一个逐个比较相邻数的办法（后来发现是冒泡排序）后，就想着系统地学一学排序算法。一搜还真有，人称“八大排序算法”，便逐个尝试实现（目前快速排序和基数排序还没写，估计开学前没机会了）。

其实在我查到的文章里shell排序实在第二个介绍的，可是却一直拖着。因为看到介绍说“对数据分组排序”，便想趁机学一下多线程。现在看来我目前用不到，第一次的话叫工人就要十几秒。。。

既然说shell是优化后的插值排序，就看看时间呗~ 我试着跑了一组数据：

（谨以此变量名纪念不曾锻炼的寒假）

还真快了一些。不过问题来了：到底几次循环最快？

这个问题的解决办法是平凡的，只需要换不同的数据量和循环数多跑几遍。而插值排序就是一次循环的shell排序，于是只需要把时间一比就得到加速倍率（上面的数据显示一次循环的shell比插值快，原因是我把交换元素顺手改成了交换分块矩阵）。于是在昨天晚上，经过几分钟运算，我就得到了下图：

可以看出来，最大加速倍率随数据量增长而迅速增长，最大加速倍率对应的循环数也在增加。想要将这个趋势定量化，我希望获得更多的数据。于是，经过对电脑运算速度的乐观估计，我豪迈地输入了nmax=10^7;tmax=20;

众所周知，flag总是会倒的，这一点上电脑也不例外（由于我不敢整夜烧电脑，没有开多线程，所以CPU没有降频。这在一定程度上保障了数据的可靠性）。早上起来，它正在进行10^6.2数据量一次循环，中午接近吃饭时，还在进行10^6.4数据量一次循环（一次循环真心慢）。。。看样子晚上都算不完了，于是Ctrl+C结束程序，得到了这个

虽然终极目标没达到，但是补充手头数据的目的初步实现。下面的时间，交给数据处理和可视化（因为11轮以上的数据看起来意义不大，便没有画上去）：

（排序用时和数据量对数之间是很线性的）

（大量数据时加速还是十分可观的）

有了这些数据，就可以尝试着回答之前的问题了：

（线性拟合还不错）

顺便还能求一下最短用时和数据量之间的关系（i7-6650U 2.21GHz-3.40GHz）：

（线性程度很高）

第一个数据点的偏差似乎是普遍的，每一个程序最初几次运行的用时会远大于多次重复后的稳定用时，而且与是否clear无关。还不清楚是什么原因。

假期的MATLAB学习就以这篇文章画上句号。晚上和同学看了《红海行动》，深感和平来之不易。为学需立志。