2 thenq←PARTITION（A，p，r）
3 QUICKSORT（A，p，q-1）
4 QUICKSORT（A，q+1，r）
为排序一个完整的数组A，最初的调用是QUICKSORT（A，1，length[A]）。
快速排序算法的关键是PARTITION过程，它对子数组A[p..r]进行就地重排：
PARTITION（A，p，r）
1 x←A[r]
2 i←p-1
3 forj←ptor-1
4 doifA[j]≤x
5 theni←i+1
6 exchangeA[i]←→A[j]
7 exchangeA[i+1]←→A[r]
8 returni+1
六快排小组安排及模块
A、主要分工:
1算法实现
该部分主要由xx实现
2代码联动
该部分主要由
3GUI
该部分主要由xx完成
4输入保护
由xx完成
B、主要模块：
1.开始排序
OnBnClickedButtonStart（）电脑自动动态演示，
2.清空所有状态调用
quickSort（）函数，开始排序，保存状态
2.快速排序：
quickSort（）排序的实现及状态保存。
3.暂停执行：
OnBnClickedButtonPause（）
排序暂停之后，用户就可以手动点击上一步或下一步来查看程序执行步骤，并且可以通过代码联动模块即时查看变量的值。
4.上一步手动执行：
OnBnClickedButtonNext（），
下一步
OnBnClickedButtonLast（）
点击上一步下一步按钮之后，显示区域就会显示程序上一步或下一步的状态
5.终止排序：
OnBnClickedButtonStop（）
结束当前排序，点击终止排序之后，即可重新输入新的序列，对新的序列进行排序。
6.重新输入：
OnBnClickedButtonRestart（）
清空数据输入框，以便重新输入待排序数据
7.修改间隔时间：
OnBnClickedButtonRevice（）
修改程序自动显示的间隔时间
快速排序的步骤如下：
<1>找中间轴
pl是左箭头，pr是右箭头，快速排序结束的标志是左箭头与右箭头指向同一个数或者左箭头移动到右箭头的右边，所以，在最开始先判断左右箭头的大小，若pl>=pr，直接return，排序结束。
若pl>=pr不成立，p=（l+r）/2取中间为轴。
设置Arrowaxil为中间轴箭头，axil.Create（'P',m_nums[cur][p].pos）初始化指向中间轴的坐标。
设置vectorvecA1用来存储该行的轴。
再依次放入左箭头—vecA1.push_back（left）
右箭头—vecA1.push_back（right）
轴箭头—vecA1.push_back（axil）
最后用m_arrows.push_back（vecA1）保存此行箭头，
再添加轴值m_axis.push_back（m_nums[cur][p].value）
算法实现：
（张萌，王彪）
快速排序属于分治算法设计范型，主要就是划分、解决和合并。
划分的重点即是寻找中间轴和左右比较交换。
对于寻找中间轴这一重点很简单，当然，在快速排序中我们最少是需要三个箭头的，左箭头pl、右箭头pr和中间箭头p。
因为快速排序结束的标志是左箭头与右箭头指向同一个数或者左箭头移动到右箭头的右边，所以，在最开始先判断左右箭头的大小，若pl>=pr，直接return，排序结束。
若pl>=pr不成立，则取p=（l+r）/2为中间轴。
设置Arrowaxil为中间轴箭头，axil.Create（'P',m_nums[cur][p].pos）初始化指向中间轴的坐标。
设置vectorvecA1用来存储该行的轴。
再依次放入左箭头—vecA1.push_back（left）右箭头—vecA1.push_back（right）轴箭头—vecA1.push_back（axil）最后用m_arrows.push_back（vecA1）保存此行箭头，再添加轴值m_axis.push_back（m_nums[cur][p].value）
要注意的是，在分割之前要将轴值与最后一个记录交换，并将轴值保存到一个临时变量中，此时序列中的最后一个位置是空闲的。
“tmpN[p].value=tmpN[r].value;//将最右端的值放入轴值位置tmpN[r].value=EMPTY;//右端变为空位，EMPTY是常量”这两句即是这一过程。
左右比较交换，即是先将左箭头所指数字与轴值相比，若大于轴值，则交换，若不大于，左箭头向右移动。
再将右箭头与所指数字与轴值相比，若小于轴值，则交换，否则右箭头左移一位。
循环进行这一过程直到左右箭头指向同一个数。
这里有好几处需要注意。
第一，因为我们有上下部查找这一功能，所以每一步都需要保存，“//保存新状态m_axis.push_back（m_axis[level-1]）;//轴值与上一轴值相同m_nums.push_back（m_nums[level]）;”即是保存的过程。
第二，空位交换“m_nums[level+1][r].value=m_nums[level+1][l].value;m_nums[level+1][l].value=EMPTY;”也是需要注意的，还有“te=Arrow（'E',m_nums[cur][l].pos）;//改变空位位置”。
第三，我们还设置了一个另外的绿色箭头“pp.SetComplete（）;//设置箭头已找到正确位置，显示绿色”。
解决即是递归调用快速排序算法，对子序列进行排序“quickSort（pl,e-1,level）;//递归调用轴值左端子序列快level=m_nums.size（）-1;quickSort（e+1,pr,level）;//递归调用轴值右端子序列快排”如此直接调用即可。
合并即是将完成排序的子序列按顺序合并。
代码联动：
（）
快速排序时，在每一次排序之后，数组的顺序、箭头的位置、轴值都会改变，但改变一次都属于一个状态，对应着一句快速排序的基本实现代码。
用一个二维数组（vector>m_nums）存储每一次改变后的状态，用一个数组（vectorm_axis）保存各行轴值，用一个二维数组（vector>m_arrows）保存所有的箭头状态，用数组（vector>m_lines）存储每一次实现功能的对应代码文本，把这四个数组用一个节点存储，就形成了每次排序对应的状态，每个对应状态层次用个一变量（intm_cur）存储。
功能演示时，就把每个节点对应的数组序列、轴值、箭头状态、对应代码调出。
这样，我们就能在演示的时候看到每一次排序的序列、轴值、箭头状态、对应代码，“上一步”就是把层次变量（intm_cur）减1，到达上个状态显示出来，“下一步”就是把层次变量（intm_cur）加1，到达下一个状态显示出来，就成为了代码联动功能。
GUI及数据有效性检验：
（）
本次算法课程设计我主要是负责快速排序的GUI，和数据的有效性检验。
因为这是一个演示性质的程序，所以GUI的设计是关键，我们的设计目标就是为了让不懂这个算法的人看到此演示之后可以较好地理解此算法。
经过全组认真的的讨论，我们最终确认了可以即时输出待排序序列的即时状态，可以看到相应的执行代码段，显示的指出当前排序选定的轴值和左右指针的位置，并且可以手动调节，查看程序运行时的上一步下一步的状态的方案。
方案确定后，我就主要负责GUI实现了。
这个程序GUI的绘制主要分为4个部分，分别是：
绘制即时待排序列，绘制指针即空位指针，输出当前轴值，输出算法代码，并使响应代码变色实现代码联动。
以上四部分的绘制都是通过获得QuickSortDlg的成员来实现：
vectorm_codes;//存储整个伪代码
vectorm_axis;//存储当行轴值
vector>m_nums;//存储所有的排序数目状态
vector>m_lines;//存储执行状态的代码
vector>m_arrows;//存储所有的箭头状态
对于一维的向量（除了m_codes），下标值就是状态标号，对应位置存储的值即为对应状态标号的状态。
对于二维向量，第一维的下表是状态标号，第二维是对应第一维状态标号的状态值（此时单个状态是用一维向量表示的）。
通过接收传递过来的状态标号值，程序就可以绘制出该状态标号所对应的状态了。
此次我负责的另一个部分就是输入数据的有效性检验，经过小组讨论，我们最终确定的方法是先以字符串形式读入整个输入，然后对输入的字符串的每个字符进行检查，看看是否含有我们所认为的非法字符，若含有非法字符，则弹出提示信息报错。
主要代码如下：
stringline;
for（inti=0;i!
=m_EditInput.GetLength（）;++i）
{charch=（char）m_EditInput.GetAt（i）;//得到整个字符串的单个字符
if（ch!
=''&&（ch<'0'||ch>'9'））//判断单个字符是否有效
{MessageBox（_T（"输入不可识别的字符（数据间用空格隔开），请重新输入！
"））;
return;
}
line.push_back（ch）;//将有效字符存入新的字符串中，方便之后数据的读出
}
通过这次的算法程序设计，我又把C++的GUI绘制好好地复习了一遍，深刻认识到，只有通过不断运用学过的知识，才能让知识真正变为自己的东西。
之后的学习中，我将继续坚持动手来实际运用知识，而不只是停留于理论的学习。
六界面
下面是带绿色箭头的界面：
在完成要求的情况下有所增加，效果如右图所示。
在主界面进行快速排序的同时，右侧显示其对应的程序并显示为红色。
左右数据比较时数组的下标随排序的变换及时改变。
6、实现功能
1.序列由用户从键盘输入
2.限制性输入
3.查看即时排序序列
4.暂停排序
5.查看中间轴的选取
6.查看上一序列和下一序列
7.查看已确定数字
8.动态演示
9.修改时间间隔
10.代码联动
7、总结
经过为期三天的时间，在我们小组的共同努力下完成了快速排序程序演示。
这个题目的算法是不用我们多做研究的，可以直接拿来用，那么我们在完成这个题目时要想完成的有质量，就需要我们在GUI方面做出自己的特色。
在我们共同讨论下达成共识，我们这个题目将要实现代码联动、轴值标记、排序速度、查看排序过程等功能，其中主要的难点在代码联动上，但是经过我们一天的时间，在小组的共同努力下我们将这个难题攻克了，另外的一个难点就是轴值的标记，但是也在我们的讨论下得到了很好的解决。
此次课程设计完成，我们颇有收获。
首先，我们对自己要做的题目的算法是了解的非常清楚，只有在我们对算法实现很清楚的前提下，我们才可以实现GUI，在实现GUI时需要做很多的参数传递，而这些参数大部分都是来源于主算法的变量值，所以我们在了解算法的同时，也必须将每个参数的变化过程弄得很清楚，通过这样对算法的剖析，我们也就算是对该算法熟记于心了。
其次，我们自学了MFC的部分操作，我们所选用的语言工具是C++，要实现动态演示，MFC是最好的工具，我们在初期花了较多的时间在研究MFC的操作上，在熟悉操作后，我们实现动态演示就很轻松了。
再次，我们学会了团队意识，在做这个题目时我们都有自己的想法，但是个人想法毕竟有限，所以我们在完成的过程中，总是会不断的讨论，在讨论中得到最佳的解决方法，我们每个成员在该问题的完成上都付出了自己的努力。
代码（vs2005）
//QuickSortDlg.cpp:
实现文件
//
#include"stdafx.h"
#include"QuickSort.h"
#include"QuickSortDlg.h"
#include
#include
#include
#ifdef_DEBUG
#definenewDEBUG_NEW
#endif
//用于应用程序“关于”菜单项的CAboutDlg对话框
classCAboutDlg:
publicCDialog
{
public:
CAboutDlg（）;
//对话框数据
enum{IDD=IDD_ABOUTBOX};
protected:
virtualvoidDoDataExchange（CDataExchange*pDX）;//DDX/DDV支持
//实现
protected:
DECLARE_MESSAGE_MAP（）
};
CAboutDlg:
:
CAboutDlg（）:
CDialog（CAboutDlg:
:
IDD）
{
}
voidCAboutDlg:
:
DoDataExchange（CDataExchange*pDX）
{
CDialog:
:
DoDataExchange（pDX）;
}
BEGIN_MESSAGE_MAP（CAboutDlg,CDialog）
END_MESSAGE_MAP（）
//CQuickSortDlg对话框
CQuickSortDlg:
:
CQuickSortDlg（CWnd*pParent/*=NULL*/）
:
CDialog（CQuickSortDlg:
:
IDD,pParent）
m_EditInput（_T（""））
m_deltT（0）
{
m_hIcon=AfxGetApp（）->LoadIcon（IDR_MAINFRAME）;
}
voidCQuickSortDlg:
:
DoDataExchange（CDataExchange*pDX）
{
CDialog:
:
DoDataExchange（pDX）;
DDX_Text（pDX,IDC_EDIT_INPUT,m_EditInput）;
DDX_Control（pDX,IDC_BUTTON_START,m_butmStart）;
DDX_Control（pDX,IDC_BUTTON_RESTART,m_butmRestart）;
DDX_Control（pDX,IDC_BUTTON_REVICE,m_butmRevice）;
DDX_Control（pDX,IDC_BUTTON_PAUSE,m_butmPause）;
DDX_Control（pDX,IDC_BUTTON_CONTINUE,m_butmCont）;
DDX_Control（pDX,IDC_BUTTON_LAST,m_butmLast）;
DDX_Control（pDX,IDC_BUTTON_NEXT,m_butmNext）;
DDX_Control（pDX,IDC_BUTTON_STOP,m_butmStop）;
DDX_Text（pDX,IDC_EDIT_DELT_T,m_deltT）;
DDV_MinMaxInt（pDX,m_deltT,100,10000）;
}
BEGIN_MESSAGE_MAP（CQuickSortDlg,CDialog）
ON_WM_SYSCOMMAND（）
ON_WM_PAINT（）
ON_WM_QUERYDRAGICON（）
//}}AFX_MSG_MAP
ON_BN_CLICKED（IDC_BUTTON_START,&CQuickSortDlg:
:
OnBnClickedButtonStart）
ON_BN_CLICKED（IDC_BUTTON_RESTART,&CQuickSortDlg:
:
OnBnClickedButtonRestart）
ON_BN_CLICKED（IDC_BUTTON_PAUSE,&CQuickSortDlg:
:
OnBnClickedButtonPause）
ON_BN_CLICKED（IDC_BUTTON_STOP,&CQuickSortDlg:
:
OnBnClickedButtonStop）
ON_WM_TIMER（）
ON_BN_CLICKED（IDC_BUTTON_REVICE,&CQuickSortDlg:
:
OnBnClickedButtonRevice）
ON_BN_CLICKED（IDC_BUTTON_LAST,&CQuickSortDlg:
:
OnBnClickedButtonLast）
ON_BN_CLICKED（IDC_BUTTON_NEXT,&CQuickSortDlg:
:
OnBnClickedButtonNext）
ON_BN_CLICKED（IDC_BUTTON_CONTINUE,&CQuickSortDlg:
:
OnBnClickedButtonContinue）
END_MESSAGE_MAP（）
//CQuickSortDlg消息处理程序
BOOLCQuickSortDlg:
:
OnInitDialog（）
{
CDialog:
:
OnInitDialog（）;
//将“关于...”菜单项添加到系统菜单中。
//IDM_ABOUTBOX必须在系统命令范围内。
ASSERT（（IDM_ABOUTBOX&0xFFF0）==IDM_ABOUTBOX）;
ASSERT（IDM_ABOUTBOX<0xF000）;
CMenu*pSysMenu=GetSystemMenu（FALSE）;
if（pSysMenu!
=NULL）
{
CStringstrAboutMenu;
strAboutMenu.LoadString（IDS_ABOUTBOX）;
if（!
strAboutMenu.IsEmpty（））
{
pSysMenu->AppendMenu（MF_SEPARATOR）;
pSysMenu->AppendMenu（MF_STRING,IDM_ABOUTBOX,strAboutMenu）;
}
}
//设置此对话框的图标。
当应用程序主窗口不是对话框时，框架将自动
//执行此操作
SetIcon（m_hIcon,TRUE）;//设置大图标
SetIcon（m_hIcon,FALSE）;//设置小图标
//TODO:
在此添加额外的初始化代码
m_butmCont.EnableWindow（false）;
m_butmNext.EnableWindow（false）;
m_butmLast.EnableWindow（false）;
m_butmPause.EnableWindow（false）;
m_butmStop.EnableWindow（false）;
GetDlgItem（IDC_EDIT_DISP）->GetWindowRect（&range）;
range.bottom=range.bottom-range.top;
range.right=range.right-range.left;
range.left=5;
range.top=5;
GetDlgItem（IDC_EDIT_CODE）->GetWindowRect（&codeRange）;//设置代码显示框大小
codeRange.bottom
升级会员 