A. 快速排序的原理是什么
先
数据序列
选
元素,并
序列
所
比该元素
元素都放
右边或左边,再
左右两边
别用同
处
直
每
待处理
序列
度
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]
已排
序
即自
合并
解决流程
符合
治
基本步骤
快速排序
治
经典应用实例
B. 如何理解快速排序算法的思想
#include <iostream>
using std::cout;
using std::endl;
int Partition( int *R, int low, int high){
// 对记录子序列 R[low..high] 进行一趟快速排序，并返回枢轴记录
// 所在位置，使得在它之前的记录的关键字均不大于它的关键字，
// 而在它之后的记录的关键字均不小于它的关键字
R[0] = R[low]; // 将枢轴记录移至数组的闲置分量
int pivotkey = R[low]; // 枢轴记录关键字
cout << endl << "pivotkey : " << pivotkey << endl;
while(low < high){ // 从表的两端交替地向中间扫描
while( low<high && R[high]>=pivotkey ){
--high;
}
if(low < high){//需要进行这样的判断，如果是由于low>=high而退出的循环，不需要移动数据
R[low++] = R[high]; // 将比枢轴记录小的记录移到低端
//cout << "移动的hign数据：" << R[high] << endl;
}
while (low<high && R[low]<=pivotkey )
++low;
if(low < high){
R[high--] = R[low]; // 将比枢轴记录大的记录移到高端
//cout << "移动的low数据：" << R[low] << endl;
}
} // while
R[low] = R[0]; // 枢轴记录移到正确位置
//cout << "返回的pivotkey: " << low << endl;
for(int i = 1; i<=10; i++){
cout << R[i-1] << " ";
}
return low; // 返回枢轴位置
} // Partition
void QSort(int *R, int s, int t ){
// 对记录序列 R[s..t] 进行快速排序
if (s < t){ // 长度大于1
int pivotloc = Partition(R, s, t);// 对 R[s..t] 进行一趟快排，并返回枢轴位置
QSort(R, s, pivotloc-1);//对低子序列递归进行排序
QSort(R, pivotloc+1, t);//对高子序列递归进行排序
}//if
}//Qsort
int main(){
int li[10] = {0,38,65,97,76,13,27,48,55,4};
cout<<"注意:R[0]为数组的闲置分量"<<endl;
for(int i = 1; i<=10; i++){
cout << li[i-1] << " ";
}
cout << endl;
QSort(li,1,9);
cout << endl;
for(int i = 1; i<=10; i++){
cout << li[i-1] << " ";
}
cout << endl;
return 0;
}
C. 快速排序方法的简单解释
快排的思想是（假设都是从小到大排列）：
选一个值作为“轴值”，所有小于轴值的都移动到轴值左边，所有大于轴值的都移动到轴值右边。这一步是让数列变得较为有序
然后分别再对轴值的左边、右边分别进行快排，一步一步提高整个数列的有序程度，直到最后完全有序。
轴值的选取有多种方式，这里就假设是选正中间的一个
70，75，82，90，23，16，10，68
选择轴值 90，排列后得到：
70，75，82，23，16，10，68，(90)
括号括起来的我表示是轴值，这里运气不好，轴值选中了一个最大的
下面对轴值左边排序，在选择轴值为23：
16，10，(23)，70，75，82，68
再分别对16， 10 和 70，75，82，68进行排序
一般快排在待排序的数字个数较少时，会选取其它排序来进行排列，比如插入排序。这里16，10数字个数已经太少，用插入排序排成10， 16
然后对 70，75，82，68进行排序……
整个排序过程就这样
D. 简单介绍一下快速排序的思想
基本思想快速排序（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对“等于”部分进行排序。
E. 快速排序算法（free pascal)详解，不要源程序，时间复杂度n（logn）；谢了//
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：
1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；
2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；
3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
5）、重复第3、4步，直到I>j；
详细过程举例如下：
原序： [26 5 37 1 61 11 59 15 48 19]
一： [19 5 15 1 11] 26 [59 61 48 37]
二： [11 5 15 1] 19 26 [59 61 48 37]
三： [1 5] 11 [15] 19 26 [59 61 48 37]
四： 1 5 11 [15] 19 26 [59 61 48 37]
五： 1 5 11 15 19 26 [59 61 48 37]
六： 1 5 11 15 19 26 [37 48] 59 [61]
七： 1 5 11 15 19 26 37 48 59 [61]
八： 1 5 11 15 19 26 37 48 59 61
快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下：
var a:array[0..10] of integer；
n:integer;
procere qsort(l,r:longint);{r，l表示集合的左右边界，即把第r到第l个数进行排序}
var i,j,m:longint;
begin
m:=a[l];{标准数}
i:=l; {I，J为指针}
j:=r;
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then begin
a[0]:=a[i];
a[i]:=a[j];
a[j]:=a[0];
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j); {如果集合中不止一个数则进入下一层递归，l，J为新边界}
if i<rthen qsort(i,r); {如果集合中不止一个数则进入下一层递归，i，r为新边界}
end;
begin
for n:=1 to 10 do read(a[n]);
qsort(1,10);
for n:=1 to 10 do write(a[n]:4);
end.
F. 如何用java实现快速排序，简答讲解下原理
快速排序思想：
通过对数据元素集合Rn 进行一趟排序划分出独立的两个部分。其中一个部分的关键字比另一部分的关键字小。然后再分别对两个部分的关键字进行一趟排序，直到独立的元素只有一个，此时整个元素集合有序。
快速排序的过程，对一个元素集合R[ low ... high ] ,首先取一个数（一般是R[low] ）做参照 ， 以R[low]为基准重新排列所有的元素。
所有比R[low]小的放前面，所有比R[low] 大的放后面，然后以R[low]为分界，对R[low ... high] 划分为两个子集和，再做划分。直到low >= high 。
比如：对R={37, 40, 38, 42, 461, 5, 7, 9, 12}进行一趟快速排序的过程如下(注:下面描述的内容中元素下表从 0 开始)：
开始选取基准 base = 37，初始位置下表 low = 0 ， high = 8 ， 从high=8，开始如果R[8] < base , 将high位置中的内容写入到R[low]中, 将high位置空出来, low = low +1 ;
从low开始探测，由于low=1 ， R[low] > base ,所以将R[low]写入到R[high] , high = high -1 ;
检测到low < high ,所以第一趟快速排序仍需继续:
此时low=1，high=7，因为 R[high] < base ,所以将 R[high] 写入到到R[low]中,low = low + 1;
从low开始探测,low = 2 , R[low] >base ,所以讲R[low]写入到R[high]，high=high-1;
继续检测到 low 小于high
此时low=2，high=6，同理R[high] < base ,将R[high] 写入到R[low]中，low=low+1;
从low继续探测,low = 3 , high=6 , R[low] > base , 将R[low]写入到R[high]中，high = high-1;
继续探测到low小于high
此时low=3，high=5，同理R[high] < base,将R[high]写入到R[low]中，low = low +1；
从low继续探测，low = 4，high=5，由于R[low] > base , 将R[low]写入到R[high]中，high = high -1 ;
此时探测到low == high == 4 ；该位置即是base所在的位置，将base写入到该位置中.
然后再对子序列Rs1 = {12,9,7,5} 和 Rs2={461,42,38,40}做一趟快速排序，直到Rsi中只有一个元素，或没有元素。
快速排序的Java实现：
private static boolean isEmpty(int[] n) {
return n == null || n.length == 0;
}
// ///////////////////////////////////////////////////
/**
* 快速排序算法思想——挖坑填数方法：
*
* @param n 待排序的数组
*/
public static void quickSort(int[] n) {
if (isEmpty(n))
return;
quickSort(n, 0, n.length - 1);
}
public static void quickSort(int[] n, int l, int h) {
if (isEmpty(n))
return;
if (l < h) {
int pivot = partion(n, l, h);
quickSort(n, l, pivot - 1);
quickSort(n, pivot + 1, h);
}
}
private static int partion(int[] n, int start, int end) {
int tmp = n[start];
while (start < end) {
while (n[end] >= tmp && start < end)
end--;
if (start < end) {
n[start++] = n[end];
}
while (n[start] < tmp && start < end)
start++;
if (start < end) {
n[end--] = n[start];
}
}
n[start] = tmp;
return start;
}
在代码中有这样一个函数：
public static void quickSortSwap(int[] n, int l, int h)
该函数可以实现，元素集合中特定的 l 到 h 位置间的数据元素进行排序。
G. 快速排序的原理 详细点 谢谢
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将值为key的项与A[j]交换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将值为key的项与A[i]交换；
5）重复第3步
6）重复第3、4、5步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
H. 按键精灵快速排序（比冒泡更快更有效率的算法）是怎么样的
冒泡排序为O(N^2)，在排序过程中其实是效率较低的。在扫拍卖或者其他需要比拼速度的时候，时间就是金钱~越快越能抢占先机。
今天我们介绍另一种更快更有效率的排序——快速排序，时间复杂度为O(n*logn)。
快速排序的算法思想
快速排序采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3 . 再对左右区间重复第二步，直到各区间只有一个数。
白话讲解算法：
假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边。
方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。
2014-8-29 13:45 上传
下载附件 (9.51 KB)
首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。
2014-8-29 13:45 上传
下载附件 (9.74 KB)
2014-8-29 13:45 上传
下载附件 (8.13 KB)
现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：
6 1 2 5 9 3 4 7 10 8
2014-8-29 13:45 上传
下载附件 (9.74 KB)
2014-8-29 13:45 上传
下载附件 (8.37 KB)
到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：
6 1 2 5 4 3 9 7 10 8
第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下：
3 1 2 5 4 6 9 7 10 8
2014-8-29 13:45 上传
下载附件 (8.28 KB)
2014-8-29 13:45 上传
下载附件 (10.45 KB)
2014-8-29 13:45 上传
下载附件 (8.48 KB)
到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。
OK，解释完毕。现在基准数6已经归位，它正好处在序列的第6位。
3
1
2
5
4
6
9
7
10
8
此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。
左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整，使得3左边的数都小于等于3，3右边的数都大于等于3。
3
1
2
5
4
第一次交换完：以3为分界点，拆分了两个序列。左边都比3小，右边都比3大。
2
1
3
5
4
再分别处理3左右的两个序列“2 1”和“5 4”
1
2
3
4
5
这样，最初我们划分的6左侧的序列都已经处理好了~~我们再来处理6右侧的序列
9
7
10
8
以9为基准数，第一次交换完：
9
7
8
10
第二次交换：
8
7
9
10
再交换一次：
7
8
9
10
这样，我们整个序列就排序完毕了
1
2
3
4
5
6
7
8
9
10
快排算法代码实现：
su = "6|1|2|7|9|3|4|5|10|8"
su=Split(su, "|")
L = UBound(su)
Call ks(0, L)
Function ks(L, B)
If L > B Then
Exit Function
End If //判断数组上标下标是否超出范围
i = L
j = B
key =int( su(L) ) //数组第一位提取作为基数
While j>i
While int ( su(j)) >= key and j > i //要先从最右边开始找 找到第一个小于key的数 这里添加的j>i的判断是为了防止j的值不断递减导致下标越界
j = j - 1
Wend
While int (su(i)) <= key and j > i //从最左边开始找 找到第一个大于key的数 （这里的字符串数组需要转换为数值型）
i = i + 1
Wend
If j>i then // 将和基数key对比得到的两个数对换 将大于key的值往右边放 小于key的值往左边放
T = su(i)
su(i) = su(j)
su(j) = T
End If
Wend // 这个 While 循环当i=j 第一轮比较完退出
su(L) = su(i) // 重新设置数组第一个元素为基数
su(i) = key// 基数归位 （排完一轮之后 左边的数<基数<右边的数 那么基数就到了排序中它该在的位置。）
Call ks(L, i - 1)//继续处理左边的数
Call ks(i + 1, B)//继续处理右边的数
End Function
For i = 0 To UBound(su)
TracePrint su(i)
Next
I. 快速排序算法为什么要双指针
这是快速排序的思路决定的。快速排序的思想是这样的：
从数组中选取一个元素作为基准值，将待排序的数组分成左右两部分，左边的部分小于基准值，右边的部分大于基准值。左右两部分继续如此递归下去，不断分裂，直到待排序数组的元素为1，此时递归条件结束。
所以使用双指针交替向中间移动，左边的指针在比基准值大的下标时停下，右边的指针在比基准小的下标时停下，双方交换数组元素，继续向左、向右移动。
这一轮的移动到什么地方停止呢？那就是在左右指针下标值相等的时候，将这个下标值的元素与基准值元素交换。
一轮下来，这个基准值位置确定，就不会再发生改变了。以它为分界线，分成左右两部分，剩下的排序它都不用参与了。
分开了左右两段之后，我们把左右段看成各自独立的待排序数组就好，做法与上面一致，只不过此时的待排序数组比较短了。使用递归实现就非常方便。
在不断的分裂过后，待排序数组只为一个元素的时候，排序就结束了。
J. 谁能帮我讲解一下 作业排序的一个更快算法的思想～
快速排序是一种分割处理式的排序算法，它将一个复杂的排序问题分解为若干较容易处理的排序问题，然后逐一解决。在快速排序算法中，首先要从数据集的数据中选择一个数据作为分割值，然后将数据分成以下3个子集：
(1) 将大于分割值的数据移到分割值前面，组成子集1；
(2) 分割值本身为子集2；
(3) 将小于分割值的数据移到分割值后面，组成子集3。
等于分割值的数据可以放在任意一个子集中，这对快速排序算法没有任何影响。由于子集2已经是有序的，所以此后只需对子集1和子集3进行快速排序。
需要注意的是，当数据集很小时，无法进行快速排序，而要使用其它排序算法。显然，当数据集中的数据只有两个或更少时，就不可能将数据集再分割成三个子集。实际上，当数据集比较小时，程序员就应该考虑是否仍然采用快速排序算法，因为在这种情况下另外一些排序算法往往更快。