最近期末复习正好看到算法的分治策略，里面讲到两种排序算法：合并排序和快速排序。这里大概就谈下自己对算法的理解，代码不是最重要的，思想才是精华，所以这次不打算讲太多代码。
首先说一下分治法的基本思想，分治法是把一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同（这里需要注意分治算法与动态规划的区别）。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这里要谈到的合并排序和快速排序便是分治算法的典型应用之一。
首先看合并排序，其基本思想是将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终讲排好序的子集合合并成为所要求的排好序的集合。算法一般通过计算两个边界的中点作为分界点，然后再递归调用对左半边和右半边分别合并排序，递归中止条件自然是左边界小于右边界，即保证至少有两个元素参与排序。当一轮调用中，左半边和右半边分别排序完成后（或无法再划分进行排序后），就进行合并，其中对元素的真正排序便是在合并中完成的，利用一个临时数组完成对排序后数组两边元素的排序、合并。如下是一个合并排序的过程图，其中S代表mergeSort函数，即递归函数，其中参数待排序数组，左分界点，右分界点；m代表merge函数，即排序、合并函数，其参数分别为待合并数组，目的合并数组，合并左分界点，合并中点，合并右分界点。
再来看看快速排序，其基本思想是对于输入的子数组a[p:r]，按以下3个步骤进行排序：
- 分解(divide)：以a[p]为某基准元素，将a[p:r]划分成3段，a[p:q-1]， a[q]和a[q+1:r]，使得a[p:q-1]中的任何元素都小于等于a[q]，而a[q+1:r]中的任何元素大于等于a[q]，q在划分中确定；
- 递归求解(conquer)：通过递归调用快速排序算法，分别对a[p:q-1]和a[q+1:r]进行排序；
- 合并(merge)：由于对a[p:q-1]和a[q+1:]r的排序在分解过程中就已经完成，所以当前a[p:q-1]和a[q+1:r]中的元素都已经排好序了，无须再执行任何计算，a[p:r]就已经完成排序了。
如下以a = [5, 3, 7, 2, 6, 4, 8, 1, 9]为例，具体分析一下快速排序的过程，【】表示划分元素，｛｝表示需交换元素。
由上述分别对两种算法的说明，大致也能看出两算法的异同之处。两种算法都考虑到使用划分元素的方法进行分治的依据，但合并排序的划分元素是直接去两边界的中点，而快速排序的划分点则是在排序中找到；合并排序首先进行划分，然后再对划分的部分递归调用，而快速排序则是在排序过程中找到划分点，之后再递归调用；再次，合并排序需要借助一个临时数组完成合并操作，而快速排序则不需要特别地合并操作，也无需临时数组，其排序是在划分中完成，而合并则只需简单连接即可。
虽然自己已经对上述算法有了比较具体的了解，但是要深入理解还是需要慢慢体会，领悟其中玄机，同时也需要在不参考参考程序的过程中，完成自己程序的编写，这样不但锻炼了编程能力，更加需要对算法本身有较透彻的理解，所以下一步自己需要用一门语言用自己的方法实现算法。
不过一直和工作室吴迪有交流，他说PHP的很多特性比较恶心，当时没在意，不过后来想想说得的确有道理，最直接的一个就是各种函数的命名就是一个巨恶心的挑战，这里就不多说了，网上已经很多对PHP的评价的文章~后来一次偶然机会看到这个分享
不过Python好多方式和JavaScript的确不大相同，所以在学习过程中我一定要注意和JS的对比，以便能够熟练掌握两门语言而不至于相互混淆~所以以后一定要多写写读书笔记才行啊~
再接着说，5月初的时候，有了人生第一次面试经历吧，不过是电话面试哈，面试方是百度，也颇让自己有些压力，通过面试，发现自己在基础知识方面还是有不少漏洞啊，特别是很久没写页面，很多页面相关知识也是忘记得差不多了，面试过程中很多原来了解的东东，回答过程中也答得不满意，可能由于紧张吧，不过准确地说应该是自己掌握得还不足吧，不过总的来说面试还算顺利吧，貌似要等二面~最近一段时间，由于工作室另外一个项目的原因，需要去研究研究
2 Comments