程序 ＝ 算法 ＋ 数据结构。这么来说，学好算法和数据结构的重要性不言而喻。数据结构对于算法的关系，有点类似于辅助工具。学习算法时，多半会涉及到数据结构的知识，无形中进行了数据结构知识的温习和巩固。另外，算法有其趣味性，学习它也是件相当有乐趣的事情。因此，想要提高代码能力，时常的学习一些经典算法不失为一种不错的方式。
个人在学习算法时遇到过很多问题，一个非常头疼的问题就是，常常学习了，过了一段时间就忘记。在学习一个新的算法时，看着文章中纷繁复杂的公式，眼花缭乱的动图，觉得理解起来比较困难。读代码更加困难。即使大致理解了，往往也无法自己完成算法，照着网上的代码写一遍，似乎觉得已经记住。再次提起这个算法时，脑子里几乎一片空白。（我个人是这样，可能是因为笨）。于是我打算写歌文章能将这些算法讲的通俗易懂，如果能帮助别人自然是极好的。
一些巧妙的思维方式，通过老师的讲解，深深的烙印在脑海里无法忘却。之所以这样，那是因为我们记住了那些巧思中的关键部分，有一种理所当然的感觉。举个例子，1+2+3+.....+100.巧解得关键是将99次的加法转换成一次乘法和一次除法。乘法是什么呢？10个5相加等于5*10，也就是说加法是可以转化成乘法的，关键是这些用来相加的数字都得相同。于是这个解法的关键就在于将不同转化成相同。(1+100) + (2+ 99) + .....+(50+51)，100个不同数字相加的问题就变成了50个相同的数字相加的问题。
好了，讲了这么多废话再不进入正题估计得被揍了。开始讲解第一个算法：快速排序算法。排序算法，其实在生活中经常用到，只是在不经意间。设想下你是个班长，体育课上同学们一字排开，你负责将队伍调整为按个头从高到矮排列。快速排序算法的关键就是选择一个目标作为参考，小的放一边，大的放另一边。结下来对左边的队伍和右边的队伍进行同样的处理直到队伍的人数为1。（即递归处理）。这样整个队伍就排列好了。为什么是这样的，因为你每次选择一个目标将小的放左边，大的放右边。将保证此次操作之后，右边的任何一个都大于左边的人和一个。于是整个算法被拆分成如下关键两步。
一：只要队伍中的人数大于1，从队伍中选择一个目标，小的放左边，大的放右边。
二：对左边的队伍和右边的队伍分别重复第一步。
让我们还是去考虑班长给同学们排队的情况。快速排序的核心就是找一个目标做基准，然后每个同学去跟他比较，矮的在左边，高的在右边。假设被找出用来参照的是A，这么做的结果就是，A左边的都比A矮，右边的都比A高。然后分别对左边的队伍和右边的队伍进行这样的调整。直到所做调整的队伍只有一个人。这样之后，队伍将是从矮到高依次排列的。
光说不练假把式。具体操作环节应该怎么做呢？容易想到的方式，也是比较自然的方式就是：选定一个人，然后从队伍的第一个人开始，拉过去跟他比较，如果比他矮就让他站到队伍的最前面去，否则站到队伍的最后面。另外需要注意的就是不要进行重复的比较，这就需要班长去记住每个同学是否已经被比较过（如果代码实现，浅显的办法就是维护一张表，记录每个元素是否已经被比较过，不过想想都挺麻烦的）。
切换到思考代码：一个班上的同学可以用一个数组表示。但是有一件事情需要处理，就是在现实中，比较完之后，班长可以说张三你去最前面吧，然后张三就乖乖的到了队伍的最前面，为了是整个队伍还像之前一样井然有序，同学们挪着小碎步。张三站到队伍前面之后，大家自觉的往后挪了一个身位，好让排头的位置留给张三。代码实现移动一个元素到数组的第一个位置：
void MoveFront(int *arr,int low,int index)
{
if (index == low)
return;
T temp = arr[index];
for(int m = index;m>low;m--)
{
arr[m] = arr[m-1];
}
arr[low] = temp;
}
移动到最后一个位置同理。
不能犯了刻舟求剑的错，当人被移动时，这个纪录的表也要跟着做相应移动。两种移动似乎是相同的，于是写下这样的代码:
template <typename T>
void MoveFront(int index,T arr[10])
{
T temp = arr[index];
for(int m = index;m > 0 ;m--)
{
arr[m] = arr[m-1];
}
arr[0] = temp;
}
照着这个思路，这部分代码是这个样子的：
void MoveFront(T *arr,int low,int index)
{
if (index == low)
return;
T temp = arr[index];
for(int m = index;m>low;m--)
{
arr[m] = arr[m-1];
}
arr[low] = temp;
}
template <typename T>
void MoveBack(T *arr,int high,int index)
{
if(index == high)
return;
T temp = arr[index];
for(int m = index;m<high;m++)
{
arr[m] = arr[m+1];
}
arr[high] = temp;
}
int split(int *arr,int low,int high)
{
bool *brr = new bool[high-low+1]; //新建一张表，记录每个对应的位置是否已经被比较过
int pivotIndex = high;
for(int m =low;m<=high;m++)
{
brr[m] = false;
}
brr[pivotIndex] = true;
for(int n = low;n<=high;n++)
{
if(!brr[n])//判断是否被检查过
{
brr[n] = true;
if(arr[n] < arr[pivotIndex])
{
MoveFront(arr,low,n); //移动到最前面
MoveFront(brr,low,n);//这张表也都跟随移动，否则就不匹配了，现在看来人脑不假思索想到的步骤让计算机执行就不是那么回事了，比较麻烦，或者干脆说挺蠢的，不过没关系，一会儿我们就回改进它
pivotIndex = (n > pivotIndex ? pivotIndex +1 : pivotIndex);
}
if(arr[n] > arr[pivotIndex])
{
MoveBack(arr,high,n);
MoveBack(brr,high,n);
pivotIndex = (n < pivotIndex ? pivotIndex -1 : pivotIndex);
n--;
}
}
}
delete []brr;
return pivotIndex;
}
最后整个代码如下：
#include "stdio.h"
template <typename T>
void MoveFront(T *arr,int low,int index)
{
if (index == low)
return;
T temp = arr[index];
for(int m = index;m>low;m--)
{
arr[m] = arr[m-1];
}
arr[low] = temp;
}
template <typename T>
void MoveBack(T *arr,int high,int index)
{
if(index == high)
return;
T temp = arr[index];
for(int m = index;m<high;m++)
{
arr[m] = arr[m+1];
}
arr[high] = temp;
}
int split(int *arr,int low,int high)
{
bool *brr = new bool[high-low+1];
int pivotIndex = high;
for(int m =low;m<=high;m++)
{
brr[m] = false;
}
brr[pivotIndex] = true;
for(int n = low;n<=high;n++)
{
if(!brr[n])
{
brr[n] = true;
if(arr[n] < arr[pivotIndex])
{
MoveFront(arr,low,n);
MoveFront(brr,low,n);
pivotIndex = (n > pivotIndex ? pivotIndex +1 : pivotIndex);
}
if(arr[n] > arr[pivotIndex])
{
MoveBack(arr,high,n);
MoveBack(brr,high,n);
pivotIndex = (n < pivotIndex ? pivotIndex -1 : pivotIndex);
n--;
}
}
}
delete []brr;
return pivotIndex;
}
void QuickSort(int *arr,int low,int high)
{
if(low<high){
int mid=split(arr,low,high);
QuickSort(arr,low,mid-1);
QuickSort(arr,mid+1,high);
}
}
//测试
int main()
{
int arr[10]={4,3,5,5,1,2,10,9,7,8};
QuickSort(arr,0,9);
for(int m=0;m<10;m++)
{
printf("%d ",arr[m]);
}
}
这样，一份完全凭着直觉转化而来的代码就完成了。不过真的是很low。接下来稍加思索修改下代码（刚才的代码完全是用脚趾头想出来的）。
首先，有必要比较之后分大小两种情况去处理么？显然要么大，要么小。所以只要挑出小的，剩下的肯定都是大的。代码稍加变形之后得到：
#include "stdio.h"
template <typename T>
void MoveFront(T *arr,int low,int high,int index)
{
if (index == low)
return;
T temp = arr[index];
for(int m = index;m>low;m--)
{
arr[m] = arr[m-1];
}
arr[low] = temp;
}
int split(int *arr,int low,int high)
{
int pivotIndex = high;
int smallCount = 0;//用来记录被挑出来较小的人的数量
for(int n = low;n<=high;n++)
{
if(arr[n] < arr[pivotIndex])
{
MoveFront(arr,low,high,n);
smallCount ++;
}
}
//遍历完成之后的队伍大约是这样的 sssssssbbbbbbbbbp ,s = small b = big p = pivot
//于是我们考虑一下如何将队伍变成这个样子的 sssssssspbbbbbbbb 如果我们依然用还沿用脚趾头思考问题的方式，那就是将p放到最后一个s后面
//然后依次将每个b往后挪动..... 脑瓜子不乐意了“当我是装饰品？”，于是经过0.0001秒思考后想到 ，其实只要将p和第一个b交换一下位置就ok了
//这个想法还不错，因为一会儿它将彻底改变我们之前的low逼代码
int temp = arr[pivotIndex];
arr[pivotIndex] = arr[smallCount+low];
arr[smallCount+low] = temp;
return smallCount+low;
}
void QuickSort(int *arr,int low,int high)
{
if(low<high){
int mid=split(arr,low,high);
QuickSort(arr,low,mid-1);
QuickSort(arr,mid+1,high);
}
}
//测试
int main()
{
int arr[10]={4,3,5,5,1,2,10,9,7,8};
QuickSort(arr,0,9);
for(int m=0;m<10;m++)
{
printf("%d ",arr[m]);
}
}
鉴于最后我们将参照目标放到合适位置的想法，再去回想之前不加思索的处理方式，觉得每次移动到队伍前端这个操作也显得有点大费周章，很有必要改进一下。我们已经引入了记录队伍中被挑出来较小的元素的个数的变量，可以利用一下。于是代码进一步被改进成这个样子。
#include "stdio.h"
int split(int *arr,int low,int high)
{
int temp;
int smallCount = 0;//用来记录被挑出来较小的人的数量
for(int n = low;n<high;n++)
{
if(arr[n] < arr[high])
{
temp = arr[low + smallCount];
arr[low+smallCount] = arr[n];
arr[n] = temp;
smallCount++;
}
}
//遍历完成之后的队伍大约是这样的 sssssssbbbbbbbbbp ,s = small b = big p = pivot
//于是我们考虑一下如何将队伍变成这个样子的 sssssssspbbbbbbbb 如果我们依然用还沿用脚趾头思考问题的方式，那就是将p放到最后一个s后面
//然后依次将每个b往后挪动..... 脑瓜子不乐意了“当我是装饰品？”，于是经过0.0001秒思考后想到 ，其实只要将p和第一个b交换一下位置就ok了
//这个想法还不错，因为一会儿它将彻底改变我们之前的low逼代码
temp = arr[high];
arr[high] = arr[smallCount+low];
arr[smallCount+low] = temp;
return smallCount+low;
}
void QuickSort(int *arr,int low,int high)
{
if(low<high){
int mid=split(arr,low,high);
QuickSort(arr,low,mid-1);
QuickSort(arr,mid+1,high);
}
}
//测试
int main()
{
// int arr[10]={4,3,5,5,1,2,10,9,7,8};
int arr[10]={1,4,6,2,5,8,7,6,9,12};
QuickSort(arr,0,9);
for(int m=0;m<10;m++)
{
printf("%d ",arr[m]);
}
}
现在这个代码看起来好些了。
