快速排序是當(dāng)遇到較大數(shù)據(jù)時,排序快,高效的方法(公司面試時,基本上會被問到...)該方法的基本思想是：
1．先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)音婶。
2．分區(qū)過程货抄，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。3．再對左右區(qū)間重復(fù)第二步塌计，直到各區(qū)間只有一個數(shù)栗恩。
? ? ? 簡單地理解就是,找一個基準(zhǔn)數(shù)(待排序的任意數(shù),一般都是選定首元素),把比小于等于基準(zhǔn)數(shù)的元素放到基準(zhǔn)數(shù)的左邊,把大于基準(zhǔn)數(shù)的元素放在基準(zhǔn)數(shù)的右邊.排完之后,在把基準(zhǔn)數(shù)的左邊和右邊各看成一個整體,? 左邊:繼續(xù)選擇基準(zhǔn)數(shù)把小于等于基準(zhǔn)數(shù)的元素放到基準(zhǔn)數(shù)的左邊,把大于基準(zhǔn)數(shù)的元素放在基準(zhǔn)數(shù)的右邊,右邊也是一樣..直到各區(qū)間只有一個數(shù)位置.
? ? ? ?快速排序之所比較快男窟，因為相比冒泡排序势决，每次交換是跳躍式的步淹。每次排序的時候設(shè)置一個基準(zhǔn)點(diǎn)从隆，將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的左邊，將大于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的右邊缭裆。這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數(shù)之間進(jìn)行交換键闺，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了澈驼，速度自然就提高了辛燥。當(dāng)然在最壞的情況下，仍可能是相鄰的兩個數(shù)進(jìn)行了交換。因此快速排序的最差時間復(fù)雜度和冒泡排序是一樣的都是O(N2)挎塌，它的平均時間復(fù)雜度為O(NlogN)畅铭。
圖片詮釋上面的思想技術(shù)分享 <書面語解釋>
1、算法思想? ??
快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序勃蜘。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)假残。
（1）分治法的基本思想? ? 分治法的基本思想是：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題缭贡。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解辉懒。
（2）快速排序的基本思想? ? 設(shè)當(dāng)前待排序的無序區(qū)為R[low..high]阳惹，利用分治法可將快速排序的基本思想描述為：①分解：? ? 在R[low..high]中任選一個記錄作為基準(zhǔn)(Pivot)，以此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左眶俩、右兩個較小的子區(qū)間R[low..pivotpos-1)和R[pivotpos+1..high]莹汤，并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為pivot)的關(guān)鍵字pivot.key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot.key颠印，而基準(zhǔn)記錄pivot則位于正確的位置(pivotpos)上纲岭，它無須參加后續(xù)的排序。?
?注意：劃分的關(guān)鍵是要求出基準(zhǔn)記錄所在的位置pivotpos线罕。劃分的結(jié)果可以簡單地表示為(注意pivot=R[pivotpos])：? ? R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys? ? ? ? ? ? ? ? ? 其中l(wèi)ow≤pivotpos≤high止潮。
②求解：通過遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序钞楼。
③組合：因為當(dāng)"求解"步驟中的兩個遞歸調(diào)用結(jié)束時喇闸，其左、右兩個子區(qū)間已有序询件。對快速排序而言燃乍，"組合"步驟無須做什么，可看作是空操作宛琅。代碼實現(xiàn): #import#define COUNT 100? ? ? //定義數(shù)組元素的個數(shù)
int a[COUNT], n; //定義全局變量刻蟹，這兩個變量需要在子函數(shù)中使用
//給快速排序方法連個參數(shù),開始位置(左),和結(jié)束位置(右)
void quicksort(int left, int right){
int i, j, t, temp;
if(left > right)? //開始位置坐標(biāo)大于結(jié)束位置坐標(biāo)時,直接return,結(jié)束下面的操作
return;
temp = a[left];? //temp中存的就是基準(zhǔn)數(shù)(基準(zhǔn)數(shù)是隨機(jī)的,但一般都是第一個元素)
i = left;
j = right;
while(i != j)
{
//順序很重要，要先從右邊開始找
while(a[j] >= temp && i
