Manchester


私信TA

用户名:wenyajie

访问量:20739

签 名:

男孩

排  名 3
经  验 12580
参赛次数 0
文章发表 152
年  龄 0
在职情况
学  校 Qing Dao University
专  业

  自我简介:

干大事,12月26号之后长期回归

TA的其他文章

解题思路:

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

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

别忘点赞哦-.-



  评论区