① 簡單介紹一下快速排序的思想
基本思想快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。 快排 演算法過程設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。一趟快速排序的演算法是：
1）設置兩個變數I、J，排序開始的時候：I=1，J=N-1；
2）以第一個數組元素作為關鍵數據，賦值給X，即 X=A[0]；
3）從J開始向前搜索，即由後開始向前搜索（J=J-1），找到第一個小於X的值，讓該值與X交換；
4）從I開始向後搜索，即由前開始向後搜索（I=I+1），找到第一個大於X的值，讓該值與X交換；
5）重復第3、4步，直到 I=J；
例如：待排序的數組A的值分別是：（初始關鍵數據：X=49）
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
進行第一次交換後： 27 38 65 97 76 13 49
( 按照演算法的第三步從後面開始找)
進行第二次交換後： 27 38 49 97 76 13 65
( 按照演算法的第四步從前面開始找>X的值，65>49,兩者交換，此時：I=3 )
進行第三次交換後： 27 38 13 97 76 49 65
( 按照演算法的第五步將又一次執行演算法的第三步從後開始找
進行第四次交換後： 27 38 13 49 76 97 65
( 按照演算法的第四步從前面開始找大於X的值，97>49,兩者交換，此時：J=4 )
此時再執行第三步的時候就發現I=J，從而結束一躺快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。
快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示：
初始狀態 {49 38 65 97 76 13 27}
進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65}
分別對前後兩部分進行快速排序 {27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。
{76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。
變種演算法快速排序(Quicksort)有三個值得一提的變種演算法，這里進行一些簡要介紹：
平衡快排（Balanced Quicksort）: 每次盡可能地選擇一個能夠代表中值的元素作為關鍵數據，然後遵循普通快排的原則進行比較、替換和遞歸。
外部快排（External Quicksort）: 與普通快排不同的是，關鍵數據是一段buffer，首先將之前和之後的M/2個元素讀入buffer並對該buffer中的這些元素進行排序，然後從被排序數組的開頭（或者結尾）讀入下一個元素，假如這個元素小於buffer中最小的元素，把它寫到最開頭的空位上；假如這個元素大於buffer中最大的元素，則寫到最後的空位上；否則把buffer中最大或者最小的元素寫入數組，並把這個元素放在buffer里。保持最大值低於這些關鍵數據，最小值高於這些關鍵數據，從而避免對已經有序的中間的數據進行重排。完成後，數組的中間空位必然空出，把這個buffer寫入數組中間空位。然後遞歸地對外部更小的部分，循環地對其他部分進行排序。
三路基數快排（Three-way Radix Quicksort，也稱作Multikey Quicksort、Multi-key Quicksort）: 結合了基數排序（radix sort，如一般的字元串比較排序就是基數排序）和快排的特點，是字元串排序中比較高效的演算法。該演算法被排序數組的元素具有一個特點，即multikey，如一個字元串，每個字母可以看作是一個key。演算法每次在被排序數組中任意選擇一個元素作為關鍵數據，首先僅考慮這個元素的第一個key（字母），然後把其他元素通過key的比較分成小於、等於、大於關鍵數據的三個部分。然後遞歸地基於這一個key位置對「小於」和「大於」部分進行排序，基於下一個key對「等於」部分進行排序。
② 快排 遞歸演算法
procere qsort(i,j:longint);
var r,l:longint;mid,temp:longint;
begin
r:=j;
l:=i;
mid:=a[r];
repeat
while a[r]>mid do dec(r);
while a[l]<mid do inc(l);
if r>=l
then
begin
temp:=a[r];
a[r]:=a[l];
a[l]:=temp;
inc(l);dec(r);
end;
until r<l;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
//A是排序數組
//基本方法:把小於MIN的放在一邊,
把大於MIN的放在另一邊. 遞歸解決.時間復雜度o(n*log(n))
③ 快速排序的原理是什麼
先
數據序列
選
元素,並
序列
所
比該元素
元素都放
右邊或左邊,再
左右兩邊
別用同
處
直
每
待處理
序列
度
1,
處理結束
前
序區R[1..H]
任取
數據元素作
比較
"基準"(
妨記
X)
用
基準
前
序區劃
左右兩
較
序區：R[1..I-1]
R[I+1..H]
且左邊
序
區
數據元素均
於等於基準元素
右邊
序
區
數據元素均
於等於基準元素
基準X則位於
終排序
位置
即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)
R[1..I-1]
R[I+1..H]均非空
別
進行
述
劃
程
直至所
序
區
數據元素均已排序
止
快速排序
基本思想
基於
治策略
於輸入
序列L[p..r]
規模足夠
則直接進行排序（比
用前述
冒泡、選擇、插入排序均
）
否則
三步處理：
解(Divide)：
待排序列L[p..r]劃
兩
非空
序列L[p..q]
L[q+1..r]
使L[p..q]
任
元素
值
於L[q+1..r]
任
元素
值
具體
通
途徑實現：
序列L[p..r]
選擇數據元素L[q]
經比較
移
L[q]
處於L[p..r]
間
適
位置
使
數據元素L[q]
值
於L[q+1..r]
任
元素
值
遞歸求解(Conquer)：通
遞歸調用快速排序算
別
L[p..q]
L[q+1..r]進行排序
合並(Merge)：由於
解
兩
序列
排序
進行
所
L[p..q]
L[q+1..r]都排
序
需要執行任何計算L[p..r]
已排
序
即自
合並
解決流程
符合
治
基本步驟
快速排序
治
經典應用實例
④ 快速排序遞歸為什麼還要用棧
首先清楚的是：只要發生函數的調用，肯定需要棧來保存調用函數當前的執行狀態等信息。
快速排序是遞歸的，排序過程中會不斷調用自身（作為函數參數，待排序序列的長度在縮短），所以需要藉助工作棧來保存每次遞歸調用的必要信息。
棧的容量：
①最好的情況是：每次PivotPos都在序列的中間，棧深=⌈log₂(n+1)⌉；
②最壞的情況是：每次PivotPos都在序列的兩端，棧深=n-1。
⑤ C語言中快速排序法的原理及應用
「快速排序法」使用的是遞歸原理，下面我結合一個例子來說明「快速排序法」的原理。首先給出一個數組{53，12，98，63，18，72，80，46， 32，21}，先找到第一個數--53，把它作為中間值，也就是說，要把53放在一個位置，使得它左邊的值比它小，右邊的值比它大。{21，12，32， 46，18，53，80，72，63，98}，這樣一個數組的排序就變成了兩個小數組的排序--53左邊的數組和53右邊的數組，而這兩個數組繼續用同樣的方式繼續下去，一直到順序完全正確。
一般來說，冒泡法是程序員最先接觸的排序方法，它的優點是原理簡單，編程實現容易，但它的缺點就是--程序的大忌--速度太慢。
附上快速排序代碼：
#include<stdio.h>
voidquicksort(inta[],intleft,intright)
{
inti,j,temp;
i=left;
j=right;
temp=a[left];
if(left>right)
return;
while(i!=j)
{
while(a[j]>=temp&&j>i)
j--;
if(j>i)
a[i++]=a[j];
while(a[i]<=temp&&j>i)
i++;
if(j>i)
a[j--]=a[i];
}
a[i]=temp;
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
voidmain()
{
inta[]={53,12,98,63,18,72,80,46,32,21};
inti;
quicksort(a,0,9);
/*排好序的結果*/
for(i=0;i<10;i++)
printf("%4d ",a[i]);
}
⑥ 輸入10個數，用遞歸演算法實現快速排序
#include<iostream>
using namespace std;
int a[10];
void qs(int s,int e)
{
int x=a[s],l=s,r=e;//以第一個數為參照做比較
if(l>=r)return;
while(l<r)
{
while(l<r&&a[r]>=x)
r--; //不小於分界值的留在右邊，遇到小於的停止
a[l]=a[r];
while(l<r&&a[l]<=x)
l++; //小於分界值的留在左邊，遇到不小於的停止
a[r]=a[l];
}
a[r]=x;
qs(s,r-1);
qs(r+1,e);//遞歸
}
int main()
{
int i;
for(i=0;i<10;i++)
cin>>a[i]; //輸入數組元素
qs(0,9); //執行排序函數
for(i=0;i<10;i++) //輸出排序後結果
cout<<a[i];
system("pause");
}
⑦ 寫出快速排序的演算法
快速排序演算法通過多次比較和交換來實現排序，其排序演算法如下：
(1)首先設定一個分界值，通過該分界值將數組分成左右兩部分。
(2)將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於或等於分界值，而右邊部分中各元素都大於或等於分界值。
(3)然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。
(4)重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。
⑧ 快速排序的遞歸深度問題
你的舉例來說，確實應該是2而不是你所說的1.
因為第一趟排序後，
序列為1，2，3
但是，此時，快排還需要進行遞歸
遞歸的序列為[1]和[3]，是第二層（雖然只有一個元素）
⑨ 快速排序最差時間復雜度遞歸公式 t(n-1)
T(n) = n+T(n-1) =n+n-1+T(n-2)=...=n+(n-1)+(n-2)+...+1+T(0)=(1+n)*n/2=O(n^2)
理論計算機研究中，衡量演算法一般從兩個方面分析：時間復雜度和空間復雜度。空間復雜度跟時間復雜度是類似的，下面簡單解釋一下時間復雜度：對於一個數據規模為n的問題，解決該問題的演算法所用時間可以用含有n的函數T(n)來表示。
對於絕大多數情況，只需要了解演算法的一般性能而不考慮細節，也就是說，我們只關心函數T(n)的表達式的形式，而不關心表達式的常數系數等與數據規模沒有關系的量值。
對於函數T(n)，我們又進一步將它簡化為O(n)，即只考慮演算法平均運行時間的「瓶頸」，也就是T(n)表達式中，關於變數n增長最快的哪一項。
(9)快速排序遞歸方法擴展閱讀：
二進制整數的基數排序是一個非常特殊的情形，因為只有兩個數字 0 和 1，故每次將數據分成 2 個小組。假設所有數據屬於[0，21+m-1], m 為一整數，則先根據最高位（m 位）的數字將數據分成 2 個小組，分別屬於[0，2m-1]和[2m，21 + m-1]；
根據次高位（m-1 位）的數字將[0，2m-1]的數據分成 2 個小組，分別屬於[0，21 - m-1]和[21 - m，2m-1]，將[2m，21 + m-1]的數據分成 2 個小組，分別屬於[2m，2m+21 - m-1]和[2m+21 - m，21 + m-1]；……；這完全類似於快速排序的分治演算法結構，因而可以類似於快速排序實現該演算法。
⑩ 輸入10個數，如何用遞歸演算法實現快速排序
#include<iostream>
using
namespace
std;
int
a[10];
void
qs(int
s,int
e)
{
int
x=a[s],l=s,r=e;//以第一個數為參照做比較
if(l>=r)return;
while(l<r)
{
while(l<r&&a[r]>=x)
r--;
//不小於分界值的留在右邊，遇到小於的停止
a[l]=a[r];
while(l<r&&a[l]<=x)
l++;
//小於分界值的留在左邊，遇到不小於的停止
a[r]=a[l];
}
a[r]=x;
qs(s,r-1);
qs(r+1,e);//遞歸
}
int
main()
{
int
i;
for(i=0;i<10;i++)
cin>>a[i];
//輸入數組元素
qs(0,9);
//執行排序函數
for(i=0;i<10;i++)
//輸出排序後結果
cout<<a[i];
system("pause");
}