奇數個數尋找中位數，有O(N)復雜度的算法，這里采用的方式是先排序，然后找出中間那一個，等寫到快排時在寫線性時間的算法吧。
以下采用的方式分別是冒泡排序和堆排序：
1
#include<stdio.h>
2#include<stdlib.h>
3#define LEN 10010
4void swap(int *a, int *b)
5
{
6
int t = *a;
7 *a = *b;
8 *b = t;
9
}
10void bsort(int *a, int n)
11{
12 int i, j;
13 for(j = n; j > 1; j--)
14 for(i = 1; i < j; i++)
15
{
16 if(a[i] > a[i + 1])
17 swap(&a[i], &a[i + 1]);
18
}
19}
20int main()
21{
22 int i, j;
23 int N;
24 int a[LEN];
25 scanf("%d", &N);
26 for(i = 1; i <= N; i++)
27 scanf("%d", &a[i]);
28 bsort(a, N);
29 printf("%d\n", a[i / 2]);
30
31
1#include<stdio.h>
2#include<stdlib.h>
3#define LEN 10010
4void swap(int *a, int *b)
5{
6 int t = *a;
7 *a = *b;
8 *b = t;
9}
10void f(int *a, int top, int r)
11{
12 int j;
13 int t = a[top];
14 int top1 = top;
15 for(j = 2 * top; j <= r; j *= 2)
16 {
17 if(j < r && a[j] < a[j + 1])
18 j++;
19 if(a[j] < a[j / 2])
20 break;
21 int t = a[j];
22 a[j] = a[j / 2];
23 a[j / 2] = t;
24 }
25}
26void heapsort(int *a, int N)
27{
28 int i, j;
29 for(i = N / 2; i >= 1; i--)
30 f(a, i, N);
31 for(i = N; i > 1; i--)
32 {
33 swap(&a[1], &a[i]);
34 f(a, 1, i - 1);
35 }
36}
37int main()
38{
39 int i, j;
40 int N;
41 int a[LEN];
42 scanf("%d", &N);
43 for(i = 1; i <= N; i++)
44 scanf("%d", &a[i]);
45 heapsort(a, N);
46 printf("%d\n", a[i
#include<stdio.h>
#include<stdlib.h>
#define LEN 10010
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
int Partition(int *a, int f, int r)
{
int i = f;
int j = r + 1;
int t = a[f];
while(1)
{
while(a[++i] < t && i < r);
while(a[--j] > t);
if(i >= j)
break;
swap(&a[i], &a[j]);
}
a[f] = a[j];
a[j] = t;
return j;
}
int Select(int *a, int f, int r, int k)
{
int j = Partition(a, f, r);
if(j == k + f - 1)
return a[j];
else if(j > k + f - 1)
return Select(a, f, j - 1, k);
else
return Select(a, j + 1, r, k + f - j - 1);
}
int main()
{
int i, j;
int N;
int a[LEN];
scanf("%d", &N);
for(i = 1; i <= N; i++)
scanf("%d", &a[i]);
int t = Select(a, 1, N, i / 2);
printf("%d\n", t);
//
//system("pause");
}
47
48 //system("pause");
49}
50
32--------------------------------------
現在補上線性時間選擇的方法：
posted on 2012-07-16 15:52
小鼠標 閱讀(581)
評論(0) 編輯 收藏 引用 所屬分類:
排序