数据结构 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

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 void merge(int *p,int l,int r)
 5 {
 6     if(l<=r)
 7     {
 8         int m = (l+r)/2;
 9         printf("%d ",p[m]);
10         merge(p,l,m-1);
11         merge(p,m+1,r);
12     }
13 }
14 
15 int cmp(const void *a, const void *b)
16 {
17     return *(int*)a - *(int*)b;
18 }
19 
20 int main()
21 {
22     int i,j;
23     int n;
24     scanf("%d",&n);
25     int *p = (int *)malloc(sizeof(int)*n);
26     for(i=0;i<n;i++)
27     {
28         scanf("%d",p+i);
29     }
30     qsort(p,n,sizeof(int),cmp);
31 //    for(i=0;i<n;i++) printf("%d ",p[i]); printf("
");
32     merge(p,0,n-1);
33     
34     free(p);
35     return 0;
36 }