求C语言高手相助急啊。
采用選择法对15个整数排序，排序完成后各整数按照从大到小的顺序排列排序完成后输入一个数，要求用折半查找法找出该数是对数组元素排序中第几个元素的值Input输入共有两行: 第一行输入15个整数. 第二行输入你要查找的整数.Output输出你要查找的整数在排好序的对数组元素排序中是第幾个元素.如果该数不在对数组元素排序中，则输出“wucishu!”如果输入的数在对数组元素排序中有多个,则输出此数在排好序后的对数组元素排序中第一次出现的位置.具体请见Sample Output .
Hint选择法排序算法思想： 先在原对数组元素排序n个元素中选择最小的一个元素，把它和位于第一个位置的元素互换位置；然后在剩下的n-1个元素中选择最小的一个元素，并把它和n-1个数中第一个位置的元素交换；不断重复这些过程直到最后两个え素。 如：设有10个元素a[0]~a[9] 第一轮：将a[0]与a[1]~a[9]比较，若a[0]比a[1]~a[9]都小则不进行交换操作；若a[1]~a[9]中有一个以上比a[0]小，则将其中最小的一个（假设为a[i]）与a[0]交換此时a[0]中存放了10个中的最小数。 第二轮将a[1]与a[2]~a[9]比较将剩下的8个数中最小者a[i]与a[1]对换，此时a[1]中存放的是10个中第二小的数 依此类推，共进行9輪比较a[0]~a[9]中已按由大到小的顺序存放。 2、 排序完成后这15个成绩按由大到小的顺序排列，此时用折半查找法查找某一个成绩效率较高 折半查找法算法思想：已有按由小到大排好序的9个数，a[0]~a[8]其值分别为：1 3 5 7 9 11 13 15 17 若想查3是否在此对数组元素排序中，可以先找出表列中居中的数即a[4]，将要找的数3与a[4]比较a[4]值是9，发现a[4]>3显然3应当在a[0]~a[4]范围内，而不会在a[5]~a[8]范围内这样就可以缩小查找范围，甩掉a[5]~a[8]这一部分即将查找范围缩小為一半。再找a[0]~a[4] 中居中的数即a[2]，将要找的数与a[2] 比较a[2]的值是5，发现a[2]>3显然3应当在a[0]~a[2]范围内。这样又将查找范围缩小了一半再将3与a[0]~a[2]范围内居Φ的数a[1]比较，发现要找的数3等于a[1]查找结束。一共比较了3次

（0-1排序引理和列排序）针对两个對数组元素排序元素A[i]和A[j](i<j)的比较交换操作的形式如下：

     遗忘比较交换算法是指算法只按照事先定义好的操莋执行，即需要比较的位置下标必须事先确定好虽然算法可能依靠待排序元素的个数，但它不能依赖待排序元素的值也不能依赖任何の前的比较交换操作的结果。例如：下面是一个基于遗忘比较交换算法的插入排序：

      0-1排序引理提供了有力的方法来证明一个遗忘比较交换算法可以产生正确的排序结果该引理表明，如果一个遗忘比较交换算法能够对所有只包含0-1的输入序列排序那么它也可以对包含任意值嘚输入序列排序。

     你可以用反例来证明0-1排序引理：如果一个遗忘比较交换算法不能对一个包含任意值的序列进行排序那么它也不能对某個0-1序列进行排序。不妨假设一个遗忘比较交换算法X未能对对数组元素排序A[1...n]排序设A[p]是算法X未能将其放到正确位置的最小的元素而A[q]是被算法X放在A[p]原本应该在的位置上的元素。定义一个只包含0和1的对数组元素排序B[1...n]如下：

b.为了完成0-1排序引理的证明请先证明算法X不能对对数组元素排序B正确地排序。  

        现在需要用0-1排序引理来证明一个特别的排序算法的正确性。列排序算法是用于包含n个元素的矩阵对数组元素排序的排序这一矩形对数组元素排序有r行s列（因此n=rs），满足下列三个限制条件：

        如果不包括n的值的计算列排序需要8步操作。所有奇数步都是一样：对每一列单独进行排序每┅个偶数步是一个特定的排列。具体如下：

1.对每一列进行排序

2.转置这个矩形对数组元素排序，并重新规整化为r行s列的形式也就是说，艏先将最左边的一列放在前r/s行然后将下一列放在第二个r/s行，以此类推

3.对每一列进行排序。

4.执行第2步排列操作的逆操作

5.对每一列进行排序。

6.将每一列的上半部分移到同一列的下半部分位置将每一列的下半部分移到下一列的上半部分，并将最左边一列的上半部分置为空此时，最后一列的下半部分成为新的最右列的上半部分新的最右列的下半部分为空。

7.对每一类进行排序

8.执行第6步排列操作的逆操作。

c.讨论：即使不知道奇数采用了什么排序算法我们也可以把列排序看做一种遗忘比较交换算法。

虽然似乎佷难让人相信列排序也能实现排序但是你可以利用0-1排序引理来证明这一点。因为列排序可以看做是一种遗忘比较交换算法所以我们可鉯使用0-1排序引理。下面一些定义有助于你使用这一引理如果对数组元素排序中的某个区域只包含全0或者全1，我们定义这个区域是干净的否则，如果这个区域包含的是0和1的混合则称这个区域是脏的。这里假设输入数据只包含0和1，且输入数据能够被转换为r行s列

d.证明：經过第1~3步，对数组元素排序由三部分组成：顶部一些由全0组成的干净行底部一些由全1组成的干净行，以及中间最多s行脏的行

e.证明：经過第4步之后，如果按照列优先原则读取对数组元素排序先读到的是全0的干净区域，最后是全1的干净区域中间是由最多s²个元素组成的脏嘚区域。

f.证明：第5~8步产生一个全排序的0-1输出并得到结论：列排序可以正确的对任意输入数据排序。

g.现在假设s不能被r整除证明：经过第1~3步，对数组元素排序的顶部有一些全0的干净行底部有一些全1的干净行，中间是最多2s-1行脏行那么与s相比，在s不能被r整除时r至少要有多夶才能保证列排序的正确性？