【优质题解】问题 1716: 算法10-6~10-8：快速排序

解题思路:

1):先选取一个元素作为枢纽，把比枢纽小的元素置于枢纽前，比枢纽大的元素置于枢纽后，此时枢纽前的元素都比它小，其后面的元素都比它大，然后再按以上方法递归处理枢纽前，后序列。

①：设待排序序列为：5 4 3 2 6

②：第一趟排序，选取枢纽为5

5 4 3 2 6

i j

（一）：

从j向前找到2<5

5 4 3 2 6

i j

j在该位置停下，把j元素换到i上，i++

2 4 3 6

i j

从i向后找到，到i=j之前没找到元素大于5，第一遍排序结束

2 4 3 5 6

j

i 把枢纽元素放到i位置上

对枢纽元素即i之前，之后的序列分别进行快排如下

（二）：

（前）

选取枢纽为2

2 4 3

i j

从j向前找，直到i=j没找到小于2的元素，结束这一趟排序

2 4 3

i

j

把枢纽元素放到i位置上（i上元素没变）

对枢纽元素即i之前，之后的序列分别进行快排如下

（三）：

（后）

选取枢纽4

4 3

i j

从j向前找到元素3<4

j在该位置停下，把j元素换到i上，i++

3

j

i

从前往后找，此时i=j遍历结束

3 4

j

i

把枢纽元素放到i位置上

这样所有数就排完了

注意事项:

下面代码中if(i<j)判断不可以省略，带代码中已标出

参考代码:

#include<stdio.h>

#include<malloc.h>

void QuickSort(int R[],int low,int high);

void input(int R[],int n);

void printout(int R[],int n);

int main()

{

int n;/*元素个数*/

int *R;/*数组指针*/

while(scanf("%d",&n)!=EOF)

{

/*开辟空间*/

R=(int *)malloc(n*sizeof(int ));

/*输入数据*/

input(R,n);

/*快速排序*/

QuickSort(R,0,n-1);

/*输出数据*/

printout(R,n);

/*释放空间*/

free(R);

}

return 0;

}

/*-------------------------------------------------------*/

void QuickSort(int R[],int low,int high)

{

int term;/*枢纽元素*/

int i=low,j=high;/*用i，j代替low，high，因为后面递归还要用到此时的low，high的值*/

if(low<high)/*满足该条件才进行一遍排序*/

{

term=R[low];/*这里默认每次排序的枢纽为第一个元素*/

while(i<j)/*i=j时一趟排序结束*/

{ /*从j向前找到一个比枢纽term小的数，放到i下标所指的元素上,同时i++*/

while(i<j&&R[j]>=term)

j--;

if(i<j)/*这个判断不能少*/

{

R[i]=R[j];

i++;

}

/*从i向后找到一个比枢纽term大（等）的数，放到j下标所指的元素上，同时j--*/

while(i<j&&R[i]<term)

i++;

if(i<j)/*这个判断不能少*/

{

R[j]=R[i];

j--;

}

}

/*一趟排序完，i=j，此时i下标所指位置就是枢纽term的最终位置*/

R[i]=term;

/*递归的对枢纽前后的序列快排*/

QuickSort(R,low,i-1);/*枢纽前*/

QuickSort(R,i+1,high);/*枢纽后*/

}

}

/*-------------------------------------------------------*/

void input(int R[],int n)

{

for(int i=0;i<n;i++)

scanf("%d",&R[i]);

}

void printout(int R[],int n)

{

for(int i=0;i<n;i++)

printf("%d ",R[i]);

printf("\n");

}