c++ sort()是穩(wěn)定排序嗎?
c++sort不是穩(wěn)定排序，stl中stable_sort才是穩(wěn)定排序。
穩(wěn)定排序的概念：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
c++sort函數(shù)用法
用法如下：
sort函數(shù)可以三個參數(shù)也可以兩個參數(shù)，必須的頭文件＃include < algorithm>和using namespace std；它使用的排序方法是類似于快排的方法，時間復(fù)雜度為n*log2(n)。Sort函數(shù)有三個參數(shù)：（第三個參數(shù)可不寫）
第一個是要排序的數(shù)組的起始地址。
第二個是結(jié)束的地址（最后一位要排序的地址）
第三個參數(shù)是排序的方法，可以是從大到小也可是從小到大，還可以不寫第三個參數(shù)，此時默認(rèn)的排序方法是從小到大排序。
特點說明
適用對象：支持隨機訪問的容器，即只支持序列式容器（vector, deque, array）。
排序范圍：左閉右開，即 [ )。
在第 2 種版本定義中，comp 可以是 C++ STL 標(biāo)準(zhǔn)庫提供的排序規(guī)則（比如 std::greater< T >），也可以是自定義的排序規(guī)則。
關(guān)于自定義的參數(shù)comp的設(shè)計原則：comp帶兩個同類型的參數(shù)，如果第一個參數(shù)排在第二個參數(shù)前面，返回true，否則返回fal。
返回值：無，因為它直接通過迭代器（指針）改變?nèi)萜鳌?/p>
默認(rèn)進行升序排序。
不穩(wěn)定的排序：不能保證相同元素的相對順序不變，sort() 函數(shù)是基于快速排序?qū)崿F(xiàn)的。stable_sort()才是穩(wěn)定的。
c++stl中的stable-sort函數(shù)，顧名思義，推測它通常用什么算法實現(xiàn)
大家都能取得的一個共識是函數(shù)庫對數(shù)據(jù)類型的選擇對其可重用性起著至關(guān)重要的作用。舉例來說，一個求方根的函數(shù)，在使用浮點數(shù)作為其參數(shù)類型的情況下的可重用性肯定比使用整型作為它的參數(shù)類型要高。而C++通過模板的機制允許推遲對某些類型的選
c++的問題，有關(guān)數(shù)據(jù)挖掘c4.5
double
Entropy(double
p,
double
s)
{
double
n
=
s
-
p;
double
result
=
0;
if
(n
!=
0)
result
+=
-
double(n)
/
s
*
log(double(n)
/
s)
/
log(2.0);
if
(p
!=
0)
result
+=
double(-p)
/
s
*
log(double(p)
/
s)
/
log(2.0);
return
result;
}
double
Gain(double
p1,
double
s1,
double
p2,
double
s2)
{
return
Entropy(p1
+
p2,
s1
+
s2)
-
double(p1
/
s1)
*
Entropy(p1,
s1)
-
double(p2
/
s2)
*
Entropy(p2,
s2);
}
void
processConValue()
{
int
con[6]
=
{2,
3,
8,
11,
14,
15};
for
(int
i
=
0;
i
<
6;
i++)
{
sortKind
=
con[i];
stable_sort(Otrain.begin(),
Otrain.end(),
header);
/*
for
(vector<OriganData>::iterator
it
=
Otrain.begin();
it
!=
Otrain.end();
it++)
cout
<<
(*it).A2
<<
(*it).label
<<
'\t';
cout
<<
endl;
*/
double
bestGain
=
0;
//記錄最佳的Gain。
double
gain;
vector<OriganData>::iterator
bestit
=
Otrain.end();
for
(vector<OriganData>::iterator
it
=
Otrain.begin();
it
!=
Otrain.end()
-
1;
it++)
{
if
((*it).label
!=
(*(it
+
1)).label)
{
int
p1
=
0,
p2
=
0,
n1
=
0,
n2
=
0;
//記錄正反例的個數(shù)
for
(vector<OriganData>::iterator
jt
=
Otrain.begin();
jt
!=
it
+
1;
jt++)
if
((*jt).label
==
'+')
p1++;
el
n1++;
for
(vector<OriganData>::iterator
jt
=
it
+
1;
jt
!=
Otrain.end();
jt++)
if
((*jt).label
==
'+')
p2++;
el
n2++;
gain
=
Gain(p1,
p1
+
n1,
p2,
p2
+
n2);
if
(gain
>
bestGain)
{
bestGain
=
gain;
bestit
=
it;
}
}
}
if
(bestit
==
Otrain.end())
bestit
=
Otrain.begin();
switch
(sortKind)
{
ca
2:
conSpit[i]
=
((*bestit).A2
+
(*(bestit
+
1)).A2)
/
2;
break;
ca
3:
conSpit[i]
=
((*bestit).A3
+
(*(bestit
+
1)).A3)
/
2;
break;
ca
8:
conSpit[i]
=
((*bestit).A8
+
(*(bestit
+
1)).A8)
/
2;
break;
ca
11:
conSpit[i]
=
((*bestit).A11
+
(*(bestit
+
1)).A11)
/
2;
break;
ca
14:
conSpit[i]
=
((*bestit).A14
+
(*(bestit
+
1)).A14)
/
2;
break;
ca
15:
conSpit[i]
=
((*bestit).A15
+
(*(bestit
+
1)).A15)
/
2;
break;
}
}
}
