|
|
问题描述:给定一个序列,以及指定这个序列的一个范围,寻找这个范围之内第n大的元素,如果n大于这个范围之内的元素数量那么就返回-1.
这是快速排序算法中partiton算法的一个应用,不断的分割序列,如果分割的位置正好是要找的位置,那么返回结果,否则视情况在前半部分和后半部分继续查找,当然这个时候n值也要相应的变化了~~
/**/
/*
*******************************************************************
 created: 2006/07/04
filename: nthElement.cpp
author: 李创
http://www.cppblog.com/converse/
purpose: 得到一个序列某个范围以内的第n个元素的算法演示
提供了这个算法的递归和非递归的实现算法
同时为了测试之用提供了堆算法,用于在找到第N个元素之后
和排序之后的数组对应位置元素进行比较以测试代码是否正确
 ********************************************************************
*/
#include
<
stdio.h
>
#include
<
stdlib.h
>
#include
<
time.h
>
//
交换元素
void
Swap(
int
*
a,
int
*
b)
{
int
temp;
temp
=
*
a;
*
a
=
*
b;
*
b
=
temp;
}
//
打印数组元素
void
DisplayArray(
int
array[],
int
length)
{
int
i;
for
(i
=
0
; i
<
length; i
++
)
 
{
printf(
"
array[%d] = %d\n
"
, i, array[i]);
 }
}
//
随机创建一个数组
void
CreateNewArray(
int
array[],
int
length)
{
for
(
int
i
=
0
; i
<
length; i
++
)
{
array[i]
=
rand()
%
256
;
}
}
//
对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,
//
在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素
int
Partition(
int
array[],
int
low,
int
high)
{
//
采用子序列的第一个元素为枢纽元素
//
非常奇怪,如果我把选择枢纽元素的算法改成注释掉的那一行那么就会出错(不是必现的)
//
难道枢纽元素的选择也会对这个算法产生影响?
//
我在快速排序算法中测试了这个函数,两种选择枢纽元素的算法最后得到的结果都是正确的~~
//
int pivot = array[(low + high) / 2];
int
pivot
=
array[low];
while
(low
<
high)
{
//
从后往前在后半部分中寻找第一个小于枢纽元素的元素
while
(low
<
high
&&
array[high]
>=
pivot)
{
--
high;
}
//
将这个比枢纽元素小的元素交换到前半部分
Swap(
&
array[low],
&
array[high]);
//
从前往后在前半部分中寻找第一个大于枢纽元素的元素
while
(low
<
high
&&
array[low]
<=
pivot)
{
++
low;
}
//
将这个比枢纽元素大的元素交换到后半部分
Swap(
&
array[low],
&
array[high]);
}
//
返回枢纽元素所在的位置
return
low;
}
//
寻找数组array中区间为[low, high]中的第n大的元素,
//
如果n大于这个区间的元素个数就返回-1
//
非递归实现,这个非递归的实现很是简单,就是把几个出口的递归调用改写成循环就好了~~
int
nthElement2(
int
array[],
int
low,
int
high,
int
n)
{
if
(low
>
high
||
n
<
1
||
n
>
high
-
low
+
1
)
{
return
-
1
;
}
int
i;
while
(
1
)
{
i
=
Partition(array, low, high);
if
(low
+
n
-
1
==
i)
{
return
array[i];
}
else
if
(low
+
n
-
1
<
i)
{
//
return nthElement(array, low, i - 1, n);
high
=
i
-
1
;
}
else
if
(low
+
n
-
1
>
i)
{
//
return nthElement(array, i + 1, high, n - (i - low + 1));
low
=
i
+
1
;
n
=
n
-
(i
-
low
+
2
);
}
}
}
//
寻找数组array中区间为[low, high]中的第n大的元素,
//
如果n大于这个区间的元素个数就返回-1
//
递归实现
int
nthElement(
int
array[],
int
low,
int
high,
int
n)
{
if
(low
>
high
||
n
<
1
||
n
>
high
-
low
+
1
)
{
return
-
1
;
}
int
i
=
Partition(array, low, high);
if
(low
+
n
-
1
==
i)
{
return
array[i];
}
else
if
(low
+
n
-
1
<
i)
{
return
nthElement(array, low, i
-
1
, n);
}
else
if
(low
+
n
-
1
>
i)
{
return
nthElement(array, i
+
1
, high, n
-
(i
-
low
+
1
));
}
}
//
调整堆数组
//
array是待调整的堆数组,i是待调整的数组元素的位置,length是数组的长度
void
HeapAdjust(
int
array[],
int
i,
int
length)
{
int
child, temp;
for
(temp
=
array[i];
2
*
i
+
1
<
length; i
=
child)
{
child
=
2
*
i
+
1
;
//
得到子结点中较小的结点
if
(child
!=
length
-
1
&&
array[child
+
1
]
>
array[child])
++
child;
//
如果较小的子结点大于父结点那么把较小的子结点往上移动,替换它的父结点
if
(temp
<
array[child])
{
array[i]
=
array[child];
}
else
//
否则退出循环
{
break
;
}
}
//
最后把需要调整的元素值放到合适的位置
array[i]
=
temp;
}
//
堆排序算法
void
HeapSort(
int
array[],
int
length)
{
//
调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素
for
(
int
i
=
length
/
2
-
1
; i
>=
0
;
--
i)
{
HeapAdjust(array, i, length);
}
//
从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素
for
(
int
i
=
length
-
1
; i
>
0
;
--
i)
{
//
把第一个元素和当前的最后一个元素交换,
//
保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
Swap(
&
array[
0
],
&
array[i]);
//
对当前的序列进行调整,调整完之后保证第一个元素是当前序列的最大值
HeapAdjust(array,
0
, i);
}
}
int
main(
void
)
{
int
array[
10
];
srand(time(NULL));
int
n;
printf(
"
input n:\n
"
);
scanf(
"
%d
"
,
&
n);
//
测试递归程序
printf(
"
测试算法的递归函数实现\n
"
);
CreateNewArray(array,
10
);
DisplayArray(array,
10
);
int
i
=
nthElement(array,
0
,
9
, n);
HeapSort(array,
10
);
printf(
"
after Heap Sort:\n
"
);
DisplayArray(array,
10
);
printf(
"
\nfind %d = %d\n
"
, n, i);
if
(array[n
-
1
]
==
i)
{
printf(
"
found!!\n
"
);
}
//
测试非递归函数的实现
printf(
"
测试算法的递归函数实现\n
"
);
CreateNewArray(array,
10
);
DisplayArray(array,
10
);
i
=
nthElement2(array,
0
,
9
, n);
HeapSort(array,
10
);
printf(
"
after Heap Sort:\n
"
);
DisplayArray(array,
10
);
printf(
"
\nfind %d = %d\n
"
, n, i);
if
(array[n
-
1
]
==
i)
{
printf(
"
found!!\n
"
);
}
system(
"
pause
"
);
return
0
;
}
|