数据结构 lucky_ming幸运的小明

问题描述

在快速排序过程中，每次会找一个划分值，将小于划分值的放到其左边，大于划分值的
放右边，然后再依次递归左右两边，对子序列进行同样的操作，直到子序列为空则停止操作。
最后就得到了有序的序列。
如何找到一个合适的划分值？小茗同学也不知道，所以他用了随机算法。小茗同学的运
气很好，每次都刚好随机到中位数，但是他也不知道这个过程中使用到的划分值都是多少。
所以你需要帮助小茗同学找出整个排序过程中，用到的所有划分值，并按照其用到的顺序输
出。
假定（1）快速排序优先递归排序左边序列，然后才是右边序列；
（2）中位数定义为序列中的第⌈ n/2⌉ 大的数（n 表示序列长度， ⌈ ⌉ 表示向上取整）。
如 3 4 1 的中位数是 3， 3 4 1 2 的中位数是 2；

★数据输入
输入的第一行为数字 n (1 ≤ n ≤ 10^5)，表示给定序列的长度。
第二行包含 n 个整数，表示序列中的整数 a1, a2, ..., an。 (1 ≤ ai ≤ 10^9)。序列中的数互
不相同。

★数据输出
在一行中依次输出划分值。

输入示例	输出示例
53 1 5 2 4	3 1 2 4 5

思路

　　快排二分

code

 #include <stdio.h>

 #include <stdlib.h>

 void merge(int *p,int l,int r)

 {

     if(l<=r)

     {

         int m = (l+r)/;

         printf("%d ",p[m]);

         merge(p,l,m-);

         merge(p,m+,r);

     }

 }

 int cmp(const void *a, const void *b)

 {

     return *(int*)a - *(int*)b;

 }

 int main()

 {

     int i,j;

     int n;

     scanf("%d",&n);

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

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

     {

         scanf("%d",p+i);

     }

     qsort(p,n,sizeof(int),cmp);

 //    for(i=0;i<n;i++) printf("%d ",p[i]); printf("\n");

     merge(p,,n-);

     free(p);

     return ;

 }

巴特西

数据结构 lucky_ming幸运的小明

最新文章

热门文章