求快速排序程序示例代码

来源：百度知道 编辑：UC知道 时间：2024/05/18 04:46:12
#define N 10//要求排序数的个数
自行输入N个数,用快序排序法进行排序.求完整代码示例.
请问,快序排序,第一次快排后,分别对划分的区域再快排,
是不是第二次排出的序一定是成品?或是怎么判断是否已排完.
谢谢指点.
注意要求的是快排,别上来给一大堆选择,冒泡等其它方法.
二楼给点注释好吗?感觉好像和书上写的思想有点出路,可能是扩展了点,所以,我就有点看不太懂了,麻烦多给出点注释啊.谢谢了.

//快速排序的平均时间复杂度为O(nlgn)

//最坏时间复杂度为O(n^2)

//空间复杂度为O(logn), 递归造成的

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define ARRAY_SIZE 10

int partitionArray(int* sortArray, int st, int end)
{
int i, j, temp;
j = st+1; // j is from st+1 through end

i = st; // i is the exact one before any elements larger than pivot

for (;j<=end;j++)
if (*(sortArray+j)<=*(sortArray+st))
{
i++;
if (i!=j)
{
temp = *(sortArray+i);
*(sortArray+i) = *(sortArray+j);
*(sortArray+j) = temp;
}
}
temp = *(sortArray+i);
*(sortArray+i) = *(sortArray+st);
*(sortArray+st) = temp;
return i;
}

void qSort(int* sortArray, int st, int end)
{
int pivot;
if (st<end)
{
pivot = partitionArray(so