這次學(xué)習(xí)了快速排序的最初版的思路，基本也一樣，呵呵，不過他在分割的時(shí)候，是兩邊同時(shí)進(jìn)行而已。注意一點(diǎn)就是他只是分割的大小，但是在分割處并不是排好的數(shù)據(jù)，所以要注意一下，不能去掉該數(shù)據(jù)的迭代。
直接奉上源代碼：
#include <stdio.h>
#include <stdlib.h>
//化分區(qū)間,找到最后元素的排序位置。并返回分隔的點(diǎn)（即最后一數(shù)據(jù)排序的位置）。
//劃分的區(qū)間是[nBegin, nEnd). pData是保存數(shù)據(jù)的指針
int Partition(int* pData, int nBeging, int nEnd)
{
//這里是和hoare的最初快速排序的版本。
int x = pData[nBeging];
--nBeging;
while (nBeging < nEnd)
{
--nEnd;
//從后向前，找到比X小的元素位置
while(pData[nEnd] > x)
{
--nEnd;
}
//小的區(qū)域增加，找到一個(gè)不比x小的元素
++nBeging;
while (pData[nBeging] < x)
{
++nBeging;
}
//把不比x小的元素存放在大的區(qū)域內(nèi)。nEnd剛好預(yù)留了此位置。
if (nBeging < nEnd)
{
int nTemp = pData[nBeging];
pData[nBeging] = pData[nEnd];
pData[nEnd] = nTemp;
}
else
{
break;
}
}
//注意這里并沒有給分割點(diǎn)排序，只是做了分割，辦證nEnd+1的左邊小于
//nEnd + 1的右邊。
return nEnd + 1; //返回nD的位置，就是分割的位置。
}
//排序的遞歸調(diào)用。
int QuickSortRecursion(int* pData, int nBeging, int nEnd)
{
if (nBeging >= nEnd -1) //如果區(qū)域不存在或只有一個(gè)數(shù)據(jù)則不遞歸排序
{
return 1;
}
//也就是說他的左邊的數(shù)據(jù)都小于等于他，他右邊的數(shù)據(jù)都大于他。
//所以他不在遞歸調(diào)用的數(shù)據(jù)中。
int i = Partition(pData, nBeging, nEnd); //找到分割點(diǎn)
QuickSortRecursion(pData, nBeging, i); //遞歸左邊的排序
QuickSortRecursion(pData, i, nEnd); //遞歸右邊的排序
return 1;
}
//快速排序
int QuickSort(int* pData, int nLen)
{
//遞歸調(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;
}