步驟為：
1.從數列中挑出一個元素，稱為 "基準"（pivot）;
2.重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
3.遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
//分區操作
int Partition(int array[], int left, int right)
{
int i,j;
int temp;
j = left-1;
for (i=left; i<=right; i++)
{
if (array[i] <= array[right]) //以最后一個數組的值為基準
{
j++;
temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
return j;
}
//迭代運算
void QuikSort(int array[], int left, int right)
{
int pivot;
if (left < right)
{
pivot = Partition(array, left, right);
QuikSort(array, left, pivot-1);
QuikSort(array, pivot+1, right);
}
}
//示例
int main()
{
int i = 0;
int a[N];
srand((int)time(0)); //設置隨機數種子
for (i=0; i<N; i++) //排序前
{
a[i] = RANDOM(100);
printf("%d/t", a[i]);
}
printf("/n/n");
QuikSort(a, 0, N-1);
for (i=0; i<N; i++) //排序后
{
printf("%d/t", a[i]);
}
}
新聞熱點
疑難解答
圖片精選
