程序 ＝ 算法 ＋ 數據結構。這么來說，學好算法和數據結構的重要性不言而喻。數據結構對于算法的關系，有點類似于輔助工具。學習算法時，多半會涉及到數據結構的知識，無形中進行了數據結構知識的溫習和鞏固。另外，算法有其趣味性，學習它也是件相當有樂趣的事情。因此，想要提高代碼能力，時常的學習一些經典算法不失為一種不錯的方式。

個人在學習算法時遇到過很多問題，一個非常頭疼的問題就是，常常學習了，過了一段時間就忘記。在學習一個新的算法時，看著文章中紛繁復雜的公式，眼花繚亂的動圖，覺得理解起來比較困難。讀代碼更加困難。即使大致理解了，往往也無法自己完成算法，照著網上的代碼寫一遍，似乎覺得已經記住。再次提起這個算法時，腦子里幾乎一片空白。（我個人是這樣，可能是因為笨）。于是我打算寫歌文章能將這些算法講的通俗易懂，如果能幫助別人自然是極好的。

一些巧妙的思維方式，通過老師的講解，深深的烙印在腦海里無法忘卻。之所以這樣，那是因為我們記住了那些巧思中的關鍵部分，有一種理所當然的感覺。舉個例子，1+2+3+.....+100.巧解得關鍵是將99次的加法轉換成一次乘法和一次除法。乘法是什么呢？10個5相加等于5*10，也就是說加法是可以轉化成乘法的，關鍵是這些用來相加的數字都得相同。于是這個解法的關鍵就在于將不同轉化成相同。(1+100) + (2+ 99) + .....+(50+51)，100個不同數字相加的問題就變成了50個相同的數字相加的問題。

好了，講了這么多廢話再不進入正題估計得被揍了。開始講解第一個算法：快速排序算法。排序算法，其實在生活中經常用到，只是在不經意間。設想下你是個班長，體育課上同學們一字排開，你負責將隊伍調整為按個頭從高到矮排列?？焖倥判蛩惴ǖ年P鍵就是選擇一個目標作為參考，小的放一邊，大的放另一邊。結下來對左邊的隊伍和右邊的隊伍進行同樣的處理直到隊伍的人數為1。（即遞歸處理）。這樣整個隊伍就排列好了。為什么是這樣的，因為你每次選擇一個目標將小的放左邊，大的放右邊。將保證此次操作之后，右邊的任何一個都大于左邊的人和一個。于是整個算法被拆分成如下關鍵兩步。

一：只要隊伍中的人數大于1，從隊伍中選擇一個目標，小的放左邊，大的放右邊。

二：對左邊的隊伍和右邊的隊伍分別重復第一步。

讓我們還是去考慮班長給同學們排隊的情況?？焖倥判虻暮诵木褪钦乙粋€目標做基準，然后每個同學去跟他比較，矮的在左邊，高的在右邊。假設被找出用來參照的是A，這么做的結果就是，A左邊的都比A矮，右邊的都比A高。然后分別對左邊的隊伍和右邊的隊伍進行這樣的調整。直到所做調整的隊伍只有一個人。這樣之后，隊伍將是從矮到高依次排列的。
光說不練假把式。具體操作環(huán)節(jié)應該怎么做呢？容易想到的方式，也是比較自然的方式就是：選定一個人，然后從隊伍的第一個人開始，拉過去跟他比較，如果比他矮就讓他站到隊伍的最前面去，否則站到隊伍的最后面。另外需要注意的就是不要進行重復的比較，這就需要班長去記住每個同學是否已經被比較過（如果代碼實現(xiàn)，淺顯的辦法就是維護一張表，記錄每個元素是否已經被比較過，不過想想都挺麻煩的）。
切換到思考代碼：一個班上的同學可以用一個數組表示。但是有一件事情需要處理，就是在現(xiàn)實中，比較完之后，班長可以說張三你去最前面吧，然后張三就乖乖的到了隊伍的最前面，為了是整個隊伍還像之前一樣井然有序，同學們挪著小碎步。張三站到隊伍前面之后，大家自覺的往后挪了一個身位，好讓排頭的位置留給張三。代碼實現(xiàn)移動一個元素到數組的第一個位置：

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);//這張表也都跟隨移動，否則就不匹配了，現(xiàn)在看來人腦不假思索想到的步驟讓計算機執(zhí)行就不是那么回事了，比較麻煩，或者干脆說挺蠢的，不過沒關系，一會兒我們就回改進它
                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]);
    }
}

現(xiàn)在這個代碼看起來好些了。