Manchester-数据结构-快速排序

解题思路:

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");
}

别忘点赞哦-.-