C++快速排序

　　快速排序作為排序家族里面最為快捷的方式，值得思考。我們將一個數組中的某一個數定為基點，然后通過快速排序按照需求（假設升序），將比基點小的數丟在基點左邊，把比基點大的數丟在基點右邊這樣來將基點數的正確位置找到。接著，我們再對基點兩邊的數組分別進行快排以達到有序的目的。

　　舉例實際分析如下：

　　int data[6] = {6,2,7,3,8,9};

　　int i = left，j = right，key = data[left];

　　初始數組為6 2 3 7 8 9，我們將基點數定位6進行第一次比較。

　　此時right = 5，left = 0。先從右往左找尋比key小的數，right = 3時找到。將data[ left]賦值為data[right] -> 3 2 7 3 8 9。

　　然后從左往右找比key大的數，i = 2時找到。我們將data[right]賦值為data[left] -> 3 2 7 7 8 9。

　　左右找尋數的任務已經完成，此時應該將key值放在正確位置去了，但是這個位置是哪里？現在還不知道，因為左右標志位還不等，但是下一次循環開始后，發現left 和 right 在2的地方相等了。所以這個位置應該是2 -> 3 2 6 7 8 9。這樣，一次排序完成了。

　　現在i 和 j 已經都變成了2而且6的正確位置已經找到了。但是按照算法的思路將這個數組分為左右兩部分該怎么辦，我們的left和right派上了大用場。從left 到 i - 1為左邊部分，從j + 1 到 right則為右半部分，對這兩部分進行遞歸快排最終可得到結果。

//
//  main.cpp
//  test
//
//  Created by MadMarical on 15/11/20.
//  Copyright (c) 2015年 com. All rights reserved.
//

#include <iostream>using namespace std;int pData[] = {6,2,7,3,8,9};void quickSort(int *p,int s,int t)
{int left,right;int key;left = s,right = t;key = p[left];if (s >= t){return;}while (left != right) //左右標志不等，在數組內尋找
    {while (left != right && p[right] >= key) //因為是升序，在數組里從右往左找尋一個比key小的數。
        {right--;}p[left] = p[right];while (left != right && p[left] <= key){left++;}p[right] = p[left];}p[left] = key;quickSort(p, s, left - 1);quickSort(p, right + 1, t);
}int main(int argc, const char * argv[])
{quickSort(pData, 0, 5);cout<<pData[0]<<" "<<pData[1]<<" "<<pData[2]<<" "<<pData[3]<<" "<<pData[4]<<" "<<pData[5]<<endl;return 0;
}

反思：

1.如果使用swap進行交換，在代碼理解上會減輕不少。

2.快速排序中的判斷方法和遞歸調用值得深思，網上的許多答案也是模棱兩可，還是要自己理解比較靠譜。

　　

　　

?