5 没事儿就学习：快速排序（Fortran） _排序

老师让我学以备不时之需，刚好又在复习数据结构，那就先把C++放一边去，拿来写个快速排序快速入门算了。于是感觉坑好深........被水淹没不知所措。（突然感觉C++真简单）
一上来肯定是用写一个“Hello World”以表尊敬，于是就出现了下面的代码。
program Helloimplicit nonecharacter(12) :: aa = "Hello World!"print *, aend program Hello
在这个神奇的交互过程中，我得到了以下几个信息：（1）每一个代码片段都会有end作为结尾，所以判断、循环、函数中的代码片段也是需要用end结尾的；（2）还是要老老实实的声明变量类型，类型和变量间用::隔开；（3）打印函数是print 。
然后再尝试写一个函数，那就两数相加这种简单的东西吧，按照C的写法模仿一个出来。
program Helloimplicit nonereal :: a = 1.0, b = 2.1, sumsum = Add(a, b)end program Helloreal function Add(a, b)Add = a + bend function
Emmmm.........好的我太天真了。
error #6404: This name does not have a type, and must have an explicit type.[ADD]
折腾了一段时间之后发现，这个错误好像看起来很有道理，没有指定明确的参数类型啊，那怎么办？说，我给你们提供了神奇的关键字，可以在这个里面声明需要使用函数的参数类型。于是就变成了这样。（也一样，C++里函数写在主函数后面也是要声明函数的么，何况我都把函数写在外面了）
program Helloimplicit nonereal :: a = 1.0, b = 2.1, suminterfacereal function Add(a, b)real a, bend function Addend interfacesum = Add(a, b)print *, sumend program Helloreal function Add(a, b)Add = a + bend function
这就很完美，于是把结果打出来看看。
好了，有了那么薄弱的基础，我觉得我已经可以开着我的塑料遥控车开启我的快速排序之旅了。
快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成两个独立的部分，其中一部分记录的关键字均比另一部分的关键字要小，则可分别对这两个序列继续进行排序，直到整个序列有序。
所以从字面上看，这种排序它会将一个序列一分为二，二分为四......一直分到子序列长度为1时停止，这时所有的数值都保证了左边的数比它小，右边的数比它大，真是个神奇的方法........下面我们的白板君入场，好久没擦了，估计快阵亡了。（白板君阵亡了，明天去买块新的再继续写）

文章插图
以{5,3,7,0,1}这个序列作为例子，我们首先将序列首位的值作为基准值，开始与后面的所有值进行比较。将所有小于5的数字放在5的前面，所有大于5的数字放在5的后面。在第一趟排序之后出现的序列为{3,0,1,5,7} 。此时基准值被放在了第四格的位置上，后续对基准值左侧和右侧的序列分别进行排序。由于3的右侧仅存在一个数值，因此无需对右侧序列进行下一步排序，左侧的{3,0,1}子序列，以3作为基准值进行排序，排序结果为{0,1,3}，此时3右侧无子序列，继续对3的做侧子序列{0,1}进行排序，得到最后的排序结果{0,1,3,5,7} 。
在快速排序算法的实现上，为了降低算法的时间复杂度，可以设置两个指针分别位于序列list的起始位置和终止位置，其值分别为low和high，为方便起见可以将基准值设置为list(low)，然后先从high所指位置向前搜索，找到第一个值比基准值小的数值，与基准值交换位置，交换完毕后从low所指位置向后搜索，找到第一个值比基准值大的数值，再与基准值交换位置。如此反复，知道low>=high为止，一趟排序结束。此时基准值的位置就是下一躺排序的序列分割的位置。