与简单排序不同，快序排序所需的比较次数较少，是内部排序中速度较快的一种排序方法。
算法思想： 分-------------- 将待排序集合划分为2部分 （一部分小于准则值，一部分大于等于准则值）
这个分的过程是不断迭代的，直到无法再分为止。
算法过程演示：
一趟排序所使用的算法：
示例：
示例：
算法：
算法分析：
程序代码：
形式1：
void QuickSort(int R[], int low,int high)
{
int i,j;
int pivot;
i=low;
j=high;
pivot=R[i];
do
{
while((R[j]>=pivot)&&(i<j)) j--;
if(i<j) R[i++]=R[j];
while(R[i]<pivot&&(i<j)) i++;
if(i<j) R[j--]=R[i];
} while (i!=j);
R[i]=pivot;
if(low<i-1) QuickSort(R,low,i-1);
if(high>i+1) QuickSort(R,i+1,high);
}
形式1---优化1：（如何确定基准值）
void QuickSort(int R[], int low,int high)
{
int i,j;
int pivot;
int & iLeft=R[low];
int & iRight=R[high];
int & iMiddle=R[(low+high)/2];
// 目的为了使 准则值R[low] 为这三个值的中间值
int temp;
if (iLeft>iMiddle)
{
temp=iMiddle;
iMiddle=iLeft;
iLeft=temp;
}
if (iRight>iMiddle)
{
temp=iMiddle;
iMiddle=iRight;
iRight=temp;
}
if (iLeft<iRight)
{
temp=iRight;
iRight=iLeft;
iLeft=iRight;
}
i=low;
j=high;
pivot=R[i];
do
{
while((R[j]>=pivot)&&(i<j)) j--;
if(i<j) R[i++]=R[j];
while(R[i]<pivot&&(i<j)) i++;
if(i<j) R[j--]=R[i];
} while (i!=j);
R[i]=pivot;
if(low<i-1) QuickSort(R,low,i-1);
if(high>i+1) QuickSort(R,i+1,high);
}
形式1----优化2 （元素个数小于30时，采用选择排序）
void QuickSort(int R[], int low,int high)
{
int i,j;
int pivot;
int & iLeft=R[low];
int & iRight=R[high];
int & iMiddle=R[(low+high)/2];
// 目的为了使 准则值R[low] 为这三个值的中间值
int temp;
if (iLeft>iMiddle)
{
temp=iMiddle;
iMiddle=iLeft;
iLeft=temp;
}
if (iRight>iMiddle)
{
temp=iMiddle;
iMiddle=iRight;
iRight=temp;
}
if (iLeft<iRight)
{
temp=iRight;
iRight=iLeft;
iLeft=iRight;
}
i=low;
j=high;
pivot=R[i];
do
{
while((R[j]>=pivot)&&(i<j)) j--;
if(i<j) R[i++]=R[j];
while(R[i]<pivot&&(i<j)) i++;
if(i<j) R[j--]=R[i];
} while (i!=j);
R[i]=pivot;
/*
if(low<i-1) QuickSort(R,low,i-1);
if(high>i+1) QuickSort(R,i+1,high);
*/
if(i-low>30)
QuickSort(R,low,i-1);
else
StraightSelectionSort(R,i-low);
if (high-i>30)
QuickSort(R,i+1,high);
else
StraightSelectionSort(&R[i+1],high-i);
}
形式2:
void QuickSort(int R[], int n)
{
int i,j;
int pivot;
i=0;
j=n-1;
pivot=R[i];
do
{
while((R[j]>=pivot)&&(i<j)) j--;
if(i<j) R[i++]=R[j];
while(R[i]<pivot&&(i<j)) i++;
if(i<j) R[j--]=R[i];
} while (i!=j);
R[i]=pivot;
if(i>1) QuickSort(R,i);
if(n-i-1>1) QuickSort(&R[i+1],n-i-1);
}
形式2---优化1
void QuickSort(int R[], int n)
{
int i,j;
int pivot;
int & iLeft=R[0];
int & iRight=R[n-1];
int & iMiddle=R[(n-1)/2];
// 目的为了使 准则值R[low] 为这三个值的中间值
int temp;
if (iLeft>iMiddle)
{
temp=iMiddle;
iMiddle=iLeft;
iLeft=temp;
}
if (iRight>iMiddle)
{
temp=iMiddle;
iMiddle=iRight;
iRight=temp;
}
if (iLeft<iRight)
{
temp=iRight;
iRight=iLeft;
iLeft=iRight;
}
i=0;
j=n-1;
pivot=R[i]; // 此时R[0]为 上述三值得中间值
do
{
while((R[j]>=pivot)&&(i<j)) j--;
if(i<j) R[i++]=R[j];
while(R[i]<pivot&&(i<j)) i++;
if(i<j) R[j--]=R[i];
} while (i!=j);
R[i]=pivot;
if(i>1) QuickSort(R,i);
if(n-i-1>1) QuickSort(&R[i+1],n-i-1);
}
形式2-----优化2
void QuickSort(int R[], int n)
{
int i,j;
int pivot;
int & iLeft=R[0];
int & iRight=R[n-1];
int & iMiddle=R[(n-1)/2];
// 目的为了使 准则值R[low] 为这三个值的中间值
int temp;
if (iLeft>iMiddle)
{
temp=iMiddle;
iMiddle=iLeft;
iLeft=temp;
}
if (iRight>iMiddle)
{
temp=iMiddle;
iMiddle=iRight;
iRight=temp;
}
if (iLeft<iRight)
{
temp=iRight;
iRight=iLeft;
iLeft=iRight;
}
i=0;
j=n-1;
pivot=R[i]; // 此时R[0]为 上述三值得中间值
do
{
while((R[j]>=pivot)&&(i<j)) j--;
if(i<j) R[i++]=R[j];
while(R[i]<pivot&&(i<j)) i++;
if(i<j) R[j--]=R[i];
} while (i!=j);
R[i]=pivot;
/*
if(i>1) QuickSort(R,i);
if(n-i-1>1) QuickSort(&R[i+1],n-i-1);
*/
if(i>30)
QuickSort(R,i);
else
StraightSelectionSort(R,i);
if (n-i-1>30)
QuickSort(R,n-i-1);
else
StraightSelectionSort(&R[i+1],n-i-1);
}
void StraightSelectionSort(int *p, int n)
{
int i,j,t;
int indexMax;
for (i=0;i<n;i++) // 0....n-1
{
// 未排元素 0...n-1-i 以排元素 n-i...n-1
for (j=0,indexMax=0;j<n-i;j++)
{
if (p[j]>=p[indexMax])
{
indexMax=j;
}
}
t=p[n-i-1];
p[n-i-1]=p[indexMax];
p[indexMax]=t;
}
}
参考资料：
http://wenku.baidu.com/view/56d1c9d780eb6294dd886cc2.html
http://www.cppblog.com/guogangj/archive/2009/11/13/100876.html