① 简单介绍一下快速排序的思想
基本思想快速排序（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");
}