|
|
問題描述:給定一個序列,以及指定這個序列的一個范圍,尋找這個范圍之內第n大的元素,如果n大于這個范圍之內的元素數量那么就返回-1.
這是快速排序算法中partiton算法的一個應用,不斷的分割序列,如果分割的位置正好是要找的位置,那么返回結果,否則視情況在前半部分和后半部分繼續查找,當然這個時候n值也要相應的變化了~~
/**/
/*
*******************************************************************
 ????created:????2006/07/04
????filename:?????nthElement.cpp
????author:????????李創
????????????????
http://m.shnenglu.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
;
}
|