放了一個禮拜的假,沒有每天及時總結...
今天不上班,但是我也早早來到公司,上午編寫 k-順序統計量的程式,下午結束了python的學習,接下來将是python實戰了,月底完成。
來說說順序統計量。
某n元素集合的第 i 個順序統計量是指該集合中,第 i 小的元素。例如:第1個順序統計量就是集合中最小元素,第n個順序統計量則是集合中最大的元素。
輸入:一個n元數組 a,及順序統計數 k
輸出:數組a中第k小的元素的值
算法用到快速排序裡的主元選取的步驟。确切的說,選取主元pivot(對應下标index)使得:
(1)所有比pivot小的元素都在主元的前面
(2)所有比pivot大的元素都在主元的後邊
及pivot是數組的第 index+1 小的元素。沒什麼特别的難度,注意下标的變換即可。具體代碼如下:
//---------------------------------------------------------
//查找數組中第 k 大元素
/*!
函數功能:
确定主元 pivot 的下标 pivotIndex, 使得 下标小于 pivotIndex 的元素
都小于 pivot,下标大于 pivotIndex 的元素都大于 pivot
(參見快速排序裡的主元選擇方法)
(作為選擇順序統計量的一個應用,此主元選擇的方法還可以改進為:首次pivotIndex随機選取)
*/
int Partition(int a[],int low,int high) //選主元選取(參考快速排序的主元選取算法)
{
int tagValue = a[high];
int pivotIndex = low-1;
for (int i = low; i<high; i++)
{
if (a[i] <= tagValue)
{
pivotIndex++;
if (i != pivotIndex)
{
int temp = a[i];
a[i] = a[pivotIndex];
a[pivotIndex] = temp;
}
}
}
int temp = a[pivotIndex+1];
a[pivotIndex+1] = a[high];
a[high] = temp;
return pivotIndex+1;
}
/*!
函數功能:
在數組 a 中,從 low 到 high 的下标裡選擇第 kIndex 小的元素
*/
int RandomizedSelect(int a[],int low,int high,int kIndex)
{
if (low == high) {
return a[low];
}
int tempIndex = Partition(a, low, high);
int b[10];
for (int i = 0; i<10; i++) {
b[i] = a[i];
}
int iIndex = tempIndex - low + 1;
if (kIndex == iIndex)
return a[tempIndex];
else if(kIndex < iIndex)
return RandomizedSelect(a, low, tempIndex-1, kIndex);
else
return RandomizedSelect(a, tempIndex+1, high, kIndex-iIndex);
}
/*!
函數功能:
在數組 a 中,選擇第 k 小的元素
*/
int SelectThe_kth_MinimumNum(int a[],int length,int k)
{
if (length < 1) {
return ERROR;
}
return RandomizedSelect(a, 0, length-1, k); // 注意此處調用 high-1 而不是 high
}
注意:k 比1小時(如0,-1等),會傳回數組中最小的元素;k > length 時,總是會傳回數組中最大元素