學(xué)了快速排序的隨機(jī)化版本，他和標(biāo)準(zhǔn)的版本沒(méi)有什么質(zhì)的區(qū)別，因?yàn)榭焖倥判虻淖顗那闆r和平均情況效率差太遠(yuǎn)，所以用隨機(jī)的版本來(lái)寫(xiě)一個(gè)更大概率平均的快速排序，也是書(shū)上的例子：
直接奉上源代碼：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//化分區(qū)間,找到最后元素的排序位置。并返回分隔的點(diǎn)（即最后一數(shù)據(jù)排序的位置）。
//劃分的區(qū)間是[nBegin, nEnd). pData是保存數(shù)據(jù)的指針
int Partition(int* pData, int nBeging, int nEnd)
{
int i = nBeging - 1; //分隔符號(hào)，最后nD保存在這里
--nEnd;
int nD = pData[nEnd]; //比較的數(shù)據(jù)。
int nTemp; // 交換用的臨時(shí)數(shù)據(jù)
//遍歷數(shù)據(jù)比較，找到nD的位置，這里注意，比較結(jié)果是,
//如果i的左邊是小于等于nD的，i的右邊是大于nD的
for (int j = nBeging; j < nEnd; ++j)
{
if (pData[j] <= nD) //如果數(shù)據(jù)比要比較的小，則在該數(shù)據(jù)的左邊，與i+1交換
{
++i; //++i小于nD的數(shù)據(jù)多一個(gè)，所以要加1
nTemp = pData[i]; //交換數(shù)據(jù)
pData[i] = pData[j];
pData[j] = nTemp;
}
}
//最后不要忘了吧nD和i+1交換，因?yàn)檫@里就是nD的位置咯。
++i;
pData[nEnd] = pData[i];
pData[i] = nD;
return i; //返回nD的位置，就是分割的位置。
}
int RandomPartition(int* pData, int nBeging, int nEnd)
{
int i = nBeging + rand() % (nEnd - nBeging - 1);
int nTemp = pData[i];
pData[i] = pData[nEnd - 1];
pData[nEnd - 1] = nTemp;
return Partition(pData, nBeging, nEnd);
}
//排序的遞歸調(diào)用。
int QuickSortRecursion(int* pData, int nBeging, int nEnd)
{
if (nBeging >= nEnd -1) //如果區(qū)域不存在或只有一個(gè)數(shù)據(jù)則不遞歸排序
{
return 1;
}
//這里因?yàn)榉指畹臅r(shí)候，分割點(diǎn)處的數(shù)據(jù)就是排序中他的位置。
//也就是說(shuō)他的左邊的數(shù)據(jù)都小于等于他，他右邊的數(shù)據(jù)都大于他。
//所以他不在遞歸調(diào)用的數(shù)據(jù)中。
int i = RandomPartition(pData, nBeging, nEnd); //找到分割點(diǎn)
QuickSortRecursion(pData, nBeging, i); //遞歸左邊的排序
QuickSortRecursion(pData, i + 1, nEnd); //遞歸右邊的排序
return 1;
}
//快速排序
int QuickSort(int* pData, int nLen)
{
srand(time(NULL));
//遞歸調(diào)用，快速排序。
QuickSortRecursion(pData, 0, nLen);
return 1;
}
int main()
{
int nData[10] = {5,9,3,2,1,6,20,45,88,75}; //測(cè)試數(shù)據(jù)
QuickSort(nData, 10); //調(diào)用快速排序
for (int i = 0; i < 10; ++i) //輸出結(jié)果
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}