Select

算法输入:$n$个元素的数组$A[1…n]$和正整数$k$,$1<=k<=n$。

算法输出:$A$中的第$k$小元素。

算法思想:现将数据按照每组5个大小分组,然后求出每一组的均值组成一个新的数组,求出新的数组mid_mid,根据mid_mid的值将数据分成3个大小的数组,将新分成的数组的大小和k比较,然后可以排除掉一部分数据,当这部分的数据比44小的时候,直接排序输出,否则的话继续运行上述步骤!

语法事项:

  • 对于静态变量,下次递归调用的时候值会不变,不会重新重新赋值初始化
  • 声明数组大小的时候,对于变量都不能直接A[n],即使这个值是从键盘中读出的,或者经过运算出来的。只能宏定义n的值。

  • 声明数组大小的时候,可以动态分配大小。

  • 可以A[] = { 数字},不必指明大小。

  • C语言中求不小于q/2的最小数可以用mid[(q+1)/2]

  • C语言中求不大于q/2的最大数可以用mid[q/2]

  • C语言中动态分配的数组指针要释放,当要递归调用的函数中包含数组指针的时候注意写法。

算法注意事项:s

  • 对于不能被5整除的数,只是求中值的时候抛弃了,但是在下面根据中值重新分到3个数组的时候是没被抛弃的。
  • 注意递归调用求中值的时候,传入的不是下标,而是第几个小的数。

算法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<stdio.h>
#include<malloc.h>
void insertionsort(int *a, int N);
int SelectAlg(int *A, int low, int high, int k);

int main()
{
int N,k,i;
int *A;
A = (int*)malloc(N * sizeof(int));
printf("Please input the number of the array:");
scanf("%d", &N);
printf("Please input the list_number to find:");
scanf("%d", &k);
printf("Please input the array:");
for(i=0; i<N; i++)
scanf("%d",&A[i]);
int k_num = SelectAlg(A, 0 , N-1 ,k);
printf("%d", k_num);
return 0;

}

int SelectAlg(int *A, int low, int high, int k)
{
int p = high - low + 1;
if (p < 44)
{
insertionsort(A, p);
return A[k-1];
}

int i,j;
int **L;
int q = p/5;
L = (int **)malloc(q * sizeof(int*));
int *mid = (int *)malloc(q * sizeof(int));
int *A_one = (int *)malloc(p * sizeof(int));
int *A_two = (int *)malloc(p * sizeof(int));
int *A_three = (int *)malloc(p * sizeof(int));
int one = 0,two = 0,three = 0;

//分配给q个大小的数组,每一个是5个大小,并找到每一个的中值,赋值给mid[]数组
for (i = 0; i < q; ++i)
{
L[i] = (int *)malloc(5 * sizeof(int));
for (j = 0; j < 5; ++j)
L[i][j] = A[(5*i)+j];

insertionsort(L[i], 5);
mid[i] = L[i][2];
}
for (i = 0; i < q; ++i)
free(L[i]);
free(L);

int mid_mid = SelectAlg(mid, 0, q-1, (q+1)/2);
//insertionsort(mid, q);
//int mid_mid = mid[(q+1)/2];

//根据mid_mid 的大小,将A分成3组数据
for (i = 0; i < p; ++i)
{
if(A[i] < mid_mid)
A_one[one++] = A[i];

else if(A[i] == mid_mid)
A_two[two++] = A[i];

else if(A[i] > mid_mid)
A_three[three++] = A[i];
}


if (one >= k)
mid_mid = SelectAlg(A_one, 0, one-1, k);
else if((one + two) < k)
mid_mid = SelectAlg(A_three, 0, three-1, k-one-two);

free(mid);
free(A_one);
free(A_two);
free(A_three);

return mid_mid;
}

void insertionsort(int *a, int N){
int i = 1;
int j,x;
while (i<N){
int j = i;
x = a[i];
while ((j>0)&&(a[j-1]>x)){
a[j] = a[j-1];
j = j -1;
}
a[j] = x;
i = i+1;
}
}
------ 本文结束------
坚持原创技术分享,您的支持将鼓励我继续创作!

欢迎关注我的其它发布渠道