3.5快速排序
Tony Hoare在1962年首次提出了快速排序算法。对快速排序方法的研究表明，至今快速排序算法仍然是流传久远的最实用的排序算法。只在输入数据项有更详细的信息时，其它排序算法才可能胜过快速排序算法。快速排序算法是利用分治技术的典型例子，随机分治策略是设计组合优化与计算几何一类问题有效算法的基础。分治策略分为三步：
（1）将问题分成若干大小基本相等的子问题；
（2）独立地解决这些子问题；
（3）将子问题归并成原问题的解。
快速排序的基本思路是：首先我们选择一个中间值middle（程序中我们可使用数组中间值），把比中间值小的放在其左边，比中间值大的放在其右边。由于这个排序算法较复杂，我们先给出其进行一次排序的程序框架（从各类数据结构教材中可得）：
{
int i, j;
int middle, iTemp;
i = left;
j = right;
middle = pData[(left + right) / 2]; //求中间值
do
{
while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数
i++;
while ((pData[j] > middle) && (j > left)) //从右扫描小于中值的数
j--;
if (i <= j) //找到了一对值
{
//交换
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
} while (i <= j) ; //如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left<j)，递归左半边
if(left<j)
QuickSort (pData,left,j);
//当右边部分有值(right>i)，递归右半边
if(right>i)
QuickSort (pData,i,right);
}
{
int i, j;
int middle, iTemp;
i = left;
j = right;
middle = sortObject[objectName[(left+right)/2]].iNumber; //求中间值
do
{
while ((sortObject[objectName[i]].iNumber < middle) && ( i < right))
//从左扫描大于中值的数
i++;
while ((sortObject[objectName[j]].iNumber > middle)&&(j > left))
//从右扫描小于中值的数
j--;
if (i < j) //找到了一对值
{
//交换成员名
iTemp = objectName[i];
objectName[i] = objectName[j];
objectName[j] = iTemp;
//交换序号
iTemp = sortObject[objectName[i]].iSeq;
sortObject[objectName[i]].iSeq = sortObject[objectName[j]].iSeq;
sortObject[objectName[j]].iSeq = iTemp;
//显示变化
CString strName;
CString strNum;
//显示位置j的对象
strName.Format("%d",objectName[j]);
dc.TextOut(objectCoord[j].x-5,objectCoord[j].y-8,strName);
if(sortObject[objectName[j]].iNumber<1000)
{
strNum.Format(" %d",sortObject[objectName[j]].iNumber);
}
else
{
strNum.Format("%d",sortObject[objectName[j]].iNumber);
}
dc.TextOut(objectCoord[j].x-15,objectCoord[j].y-30,strNum);
//显示位置i的对象
strName.Format("%d",objectName[i]);
dc.TextOut(objectCoord[i].x-5,objectCoord[i].y-8,strName);
if(sortObject[objectName[i]].iNumber<1000)
{
strNum.Format(" %d",sortObject[objectName[i]].iNumber);
}
else
{
strNum.Format("%d",sortObject[objectName[i]].iNumber);
}
dc.TextOut(objectCoord[i].x-15,objectCoord[i].y-30,strNum);
Sleep(1000);
i++;
j--;
}
else if (i==j)
{
i++;
j--;
}
} while (i <= j) ; //如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left<j)，递归左半边
if(left<j)
QuickSort (objectName,dc,left,j);
//当右边部分有值(right>i)，递归右半边 if(right>i)
QuickSort (objectName,dc,i,right);
}
{
CClientDC dc(this) ;
dc.SetBkColor(RGB(180,180,180));
int objectName[SORT_OBJECT_NUM]; //每个位置对应的成员名
//初始化每个位置对应的成员
for(int i=0;i<SORT_OBJECT_NUM;i++)
{
objectName[i] = i;
}
QuickSort(objectName,dc,0,SORT_OBJECT_NUM-1);
}
154 1089 456 564 554 4419 692 9859 9359 9703
154 1089 456 564 554 692 4419 9859 9359 9703
154 554 456 564 1089 692 4419 9859 9359 9703
154 456 554 564 1089 692 4419 9859 9359 9703
154 456 554 564 692 1089 4419 9859 9359 9703
154 456 554 564 692 1089 4419 9703 9359 9859
154 456 554 564 692 1089 4419 9359 9703 9859
对于n个成员，快速排序法的比较次数大约为n*logn 次，交换次数大约为(n*logn)/6次。如果n为100，冒泡法需要进行4950 次比较，而快速排序法仅需要200 次，快速排序法的效率的确很高。快速排序法的性能与中间值的选定关系密切，如果每一次选择的中间值都是最大值（或最小值），该算法的速度就会大大下降。快速排序算法最坏情况下的时间复杂度为O(n2)，而平均时间复杂度为O(n*logn)。
4.总结
冒泡排序、选择排序和插入排序等的时间复杂性是O(n2)，快速排序、堆排序和归并排序等高级排序算法的时间复杂度为O(n*logn)，因此后者的排序效率较高。但这并不意味着总是要使用高级排序算法，下面给出各种排序算法选用的一般原则：
（1）当数据量不大时选插入或选择排序，不要用冒泡排序；
事实上，冒泡排序虽然简单，但的确是最不宜采用的排序算法，因为其性能表现是最差的。
（2）当数据量大而又注重时间复杂度时选快速或堆排序等；
堆排序的设计思路是：定义堆为一个键值序列{k1 ,k2 ,…,kn}，它具有如下特性：ki < = k2i，ki < = k2i + 1 (i = 1 ,2 ,…, [ n/ 2 ]) 。对一组待排序的键值，首先把它们按堆的定义排列成一个序列(称为初建堆)，这就找到了最小键值。然后将最小的键值取出，用剩下的键值再重新建堆，便得到次小键值。如此反复进行，直到把全部键值排好序为止。
由于快速排序和堆排序算法较复杂，因此在待排序的数据量较小时反而比插入和选择排序慢；
（3）当要在已排序数据上增加新数据时选插入排序。
当原有数据本身就有序时，插入排序的性能非常好。在已排序数据上增加新数据时，时间复杂性仅为O(n)。