|
|
問題描述:給定一個(gè)序列,以及指定這個(gè)序列的一個(gè)范圍,尋找這個(gè)范圍之內(nèi)第n大的元素,如果n大于這個(gè)范圍之內(nèi)的元素?cái)?shù)量那么就返回-1.
這是快速排序算法中partiton算法的一個(gè)應(yīng)用,不斷的分割序列,如果分割的位置正好是要找的位置,那么返回結(jié)果,否則視情況在前半部分和后半部分繼續(xù)查找,當(dāng)然這個(gè)時(shí)候n值也要相應(yīng)的變化了~~
/**/
/*
*******************************************************************
 ????created:????2006/07/04
????filename:?????nthElement.cpp
????author:????????李創(chuàng)
????????????????
http://www.shnenglu.com/converse/
????purpose:????得到一個(gè)序列某個(gè)范圍以內(nèi)的第n個(gè)元素的算法演示
????????????????提供了這個(gè)算法的遞歸和非遞歸的實(shí)現(xiàn)算法
????????????????同時(shí)為了測試之用提供了堆算法,用于在找到第N個(gè)元素之后
????????????????和排序之后的數(shù)組對(duì)應(yīng)位置元素進(jìn)行比較以測試代碼是否正確
 ********************************************************************
*/
#include?
<
stdio.h
>
#include?
<
stdlib.h
>
#include?
<
time.h
>
//
?交換元素
void
?Swap(
int
?
*
a,?
int
?
*
b)
{
????
int
?temp;
????temp?
=
?
*
a;
????
*
a???
=
?
*
b;
????
*
b???
=
?temp;
}
//
?打印數(shù)組元素
void
?DisplayArray(
int
?array[],?
int
?length)
{
????
int
?i;
????
for
?(i?
=
?
0
;?i?
<
?length;?i
++
)
  ????
{
????????printf(
"
array[%d]?=?%d\n
"
,?i,?array[i]);
 ????}
}
//
?隨機(jī)創(chuàng)建一個(gè)數(shù)組
void
?CreateNewArray(
int
?array[],?
int
?length)
{
????
for
?(
int
?i?
=
?
0
;?i?
<
?length;?i
++
)
????
{
????????array[i]?
=
?rand()?
%
?
256
;
????}
}
//
?對(duì)一個(gè)給定范圍的子序列選定一個(gè)樞紐元素,執(zhí)行完函數(shù)之后返回分割元素所在的位置,
//
?在分割元素之前的元素都小于樞紐元素,在它后面的元素都大于這個(gè)元素
int
?Partition(
int
?array[],?
int
?low,?
int
?high)
{
????
//
?采用子序列的第一個(gè)元素為樞紐元素
????
//
?非常奇怪,如果我把選擇樞紐元素的算法改成注釋掉的那一行那么就會(huì)出錯(cuò)(不是必現(xiàn)的)
????
//
?難道樞紐元素的選擇也會(huì)對(duì)這個(gè)算法產(chǎn)生影響?
????
//
?我在快速排序算法中測試了這個(gè)函數(shù),兩種選擇樞紐元素的算法最后得到的結(jié)果都是正確的~~
????
//
int?pivot?=?array[(low?+?high)?/?2];
????
int
?pivot?
=
?array[low];
????
while
?(low?
<
?high)
????
{
????????
//
?從后往前在后半部分中尋找第一個(gè)小于樞紐元素的元素
????????
while
?(low?
<
?high?
&&
?array[high]?
>=
?pivot)
????????
{
????????????
--
high;
????????}
????????
//
?將這個(gè)比樞紐元素小的元素交換到前半部分
????????Swap(
&
array[low],?
&
array[high]);
????????
//
?從前往后在前半部分中尋找第一個(gè)大于樞紐元素的元素
????????
while
?(low?
<
?high?
&&
?array[low]?
<=
?pivot)
????????
{
????????????
++
low;
????????}
????????
//
?將這個(gè)比樞紐元素大的元素交換到后半部分
????????Swap(
&
array[low],?
&
array[high]);
????}
????
//
?返回樞紐元素所在的位置
????
return
?low;
}
//
?尋找數(shù)組array中區(qū)間為[low,?high]中的第n大的元素,
//
?如果n大于這個(gè)區(qū)間的元素個(gè)數(shù)就返回-1
//
?非遞歸實(shí)現(xiàn),這個(gè)非遞歸的實(shí)現(xiàn)很是簡單,就是把幾個(gè)出口的遞歸調(diào)用改寫成循環(huán)就好了~~
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
);
????????}
????}
}
//
?尋找數(shù)組array中區(qū)間為[low,?high]中的第n大的元素,
//
?如果n大于這個(gè)區(qū)間的元素個(gè)數(shù)就返回-1
//
?遞歸實(shí)現(xiàn)
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
));
????}
}
//
?調(diào)整堆數(shù)組
//
?array是待調(diào)整的堆數(shù)組,i是待調(diào)整的數(shù)組元素的位置,length是數(shù)組的長度
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
;
????????
//
?得到子結(jié)點(diǎn)中較小的結(jié)點(diǎn)
????????
if
?(child?
!=
?length?
-
?
1
?
&&
?array[child?
+
?
1
]?
>
?array[child])
????????????
++
child;
????????
//
?如果較小的子結(jié)點(diǎn)大于父結(jié)點(diǎn)那么把較小的子結(jié)點(diǎn)往上移動(dòng),替換它的父結(jié)點(diǎn)
????????
if
?(temp?
<
?array[child])
????????
{
????????????array[i]?
=
?array[child];
????????}
????????
else
????
//
?否則退出循環(huán)
????????
{
????????????
break
;
????????}
????}
????
//
?最后把需要調(diào)整的元素值放到合適的位置
????array[i]?
=
?temp;
}
//
?堆排序算法
void
?HeapSort(
int
?array[],?
int
?length)
{
????
//
?調(diào)整序列的前半部分元素,調(diào)整完之后第一個(gè)元素是序列的最大的元素
????
for
?(
int
?i?
=
?length?
/
?
2
?
-
?
1
;?i?
>=
?
0
;?
--
i)
????
{
????????HeapAdjust(array,?i,?length);
????}
????
//
?從最后一個(gè)元素開始對(duì)序列進(jìn)行調(diào)整,不斷的縮小調(diào)整的范圍直到第一個(gè)元素
????
for
?(
int
?i?
=
?length?
-
?
1
;?i?
>
?
0
;?
--
i)
????
{
????????
//
?把第一個(gè)元素和當(dāng)前的最后一個(gè)元素交換,
????????
//
?保證當(dāng)前的最后一個(gè)位置的元素都是在現(xiàn)在的這個(gè)序列之中最大的
????????Swap(
&
array[
0
],?
&
array[i]);
????????
//
?對(duì)當(dāng)前的序列進(jìn)行調(diào)整,調(diào)整完之后保證第一個(gè)元素是當(dāng)前序列的最大值
????????HeapAdjust(array,?
0
,?i);
????}
}
int
?main(
void
)
{
????
int
?array[
10
];
????srand(time(NULL));
????
int
?n;
????printf(
"
input?n:\n
"
);
????scanf(
"
%d
"
,?
&
n);
????
//
?測試遞歸程序
????printf(
"
測試算法的遞歸函數(shù)實(shí)現(xiàn)\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
"
);
????}
????
//
?測試非遞歸函數(shù)的實(shí)現(xiàn)
????printf(
"
測試算法的遞歸函數(shù)實(shí)現(xiàn)\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
;
}
|