STL_算法_02_排序算法

◆ 常用的排序算法：

1.1、合并（容器A(全部/部分)&容器B(全部/部分)==>容器C(全部/部分)，容器C中元素已经排好顺序），返回的值==>iteratorOutBegin.end()

iterator merge(iterator1Begin, iterator1And, iterator2Begin, iterator2End, iteratorOutBegin);

iterator merge(iterator1Begin, iterator1And, iterator2Begin, iterator2End, iteratorOutBegin, functor排序); // ZC: 这里的functor指定，排序的话采用何种方式

1.2、排序

void sort(iteratorBegin, iteratorEnd);

void sort(iteratorBegin, iteratorEnd, functor排序);

1.3、随机洗牌（shuffle是洗牌的意思）（记得初始化随机种子）

void random_shuffle(iteratorBeign, iteratorEnd);

// ZC: 下面的functor作用是，通过容器中某个元素(传入参数) 计算得到它在容器中的新的位置，然后与这个位置上的原来的元素进行位置交换

void random_shuffle(iteratorBeign, iteratorEnd, functor产生随机位置);

1.4、反转

void reverse(iteratorBegin, iteratorEnd);

1、

◆ 以下是排序和通用算法：提供元素排序策略

1.1、第6讲 PPT.25

◆ merge() : 合并两个有序序列，存放到另一个序列。

ZC: 最终得到的result容器里面的元素是经过有序的

ZC: 有两种参数格式，返回值是 iterator[ 该值==result容器.end() ]

ZC: VC6 测试代码 - 1：

 1 #ifdef WIN32
 2 #pragma warning (disable: 4786)
 3 #endif
 4 
 5 #include <vector>
 6 #include <set>
 7 
 8 #include <algorithm>    // 算法
 9 #include <numeric>    // 算法
10 #include <functional>    // 算法
11 
12 using namespace std;
13 
14 void main()
15 {
16     vector<int> vecIntA;
17     vecIntA.push_back(1);
18     vecIntA.push_back(3);
19     vecIntA.push_back(5);
20     vecIntA.push_back(7);
21     vecIntA.push_back(9);
22 
23     vector<int> vecIntB;
24     vecIntB.push_back(2);
25     vecIntB.push_back(4);
26     vecIntB.push_back(6);
27     vecIntB.push_back(8);
28 
29     vector<int> vecIntC;
30     vecIntC.resize(9);  // 扩大容量 // ZC: 如果不做这一步，VC6编译的exe就崩溃了
31     merge(
32         vecIntA.begin(), vecIntA.end(),
33         vecIntB.begin(), vecIntB.end(),
34         vecIntC.begin());
35     vector<int>::iterator it = vecIntC.begin();
36     // ZC: 从这里打印的信息来看，它自动做了排序处理
37     int iIdx = 0;
38     while (it != vecIntC.end())
39     {
40         printf("[%02d] ==> *it : %d
", iIdx, *it);
41         it ++;
42         iIdx ++;
43     }
44 }

ZC：控制台输出 - 1：

 1 [00] ==> *it : 1
 2 [01] ==> *it : 2
 3 [02] ==> *it : 3
 4 [03] ==> *it : 4
 5 [04] ==> *it : 5
 6 [05] ==> *it : 6
 7 [06] ==> *it : 7
 8 [07] ==> *it : 8
 9 [08] ==> *it : 9
10 Press any key to continue

ZC: VC6 测试代码 - 2：

来自msdn的例子（https://msdn.microsoft.com/en-us/library/9ew9xdb2(v=vs.80).aspx）

  1 // alg_merge.cpp
  2 // compile with: /EHsc
  3 #include <vector>
  4 #include <algorithm>
  5 #include <functional>   // For greater<int>( )
  6 #include <iostream>
  7 
  8 // Return whether modulus of elem1 is less than modulus of elem2
  9 bool mod_lesser ( int elem1, int elem2 )
 10 {
 11    if (elem1 < 0) 
 12       elem1 = - elem1;
 13    if (elem2 < 0) 
 14       elem2 = - elem2;
 15    return elem1 < elem2;
 16 }
 17 
 18 int main()
 19 {
 20    using namespace std;
 21    vector <int> v1a, v1b, v1 ( 12 );
 22    vector <int>::iterator Iter1a,  Iter1b, Iter1;
 23 
 24    // Constructing vector v1a and v1b with default less than ordering
 25    int i;
 26    for ( i = 0 ; i <= 5 ; i++ )
 27       v1a.push_back(  i );
 28 
 29    int ii;
 30    for ( ii =-5 ; ii <= 0 ; ii++ )
 31       v1b.push_back(  ii  );
 32 
 33    cout << "Original vector v1a with range sorted by the
 "
 34         << "binary predicate less than is  v1a = ( " ;
 35    for ( Iter1a = v1a.begin( ) ; Iter1a != v1a.end( ) ; Iter1a++ )
 36       cout << *Iter1a << " ";
 37    cout << ")." << endl;
 38 
 39    cout << "Original vector v1b with range sorted by the
 "
 40         << "binary predicate less than is  v1b = ( " ;
 41    for ( Iter1b = v1b.begin ( ) ; Iter1b != v1b.end ( ) ; Iter1b++ )
 42       cout << *Iter1b << " ";
 43    cout << ")." << endl;
 44    
 45    // Constructing vector v2 with ranges sorted by greater
 46    vector <int> v2a ( v1a ) , v2b ( v1b ) ,  v2 ( v1 );
 47    vector <int>::iterator Iter2a,  Iter2b, Iter2;
 48    sort ( v2a.begin ( ) , v2a.end ( ) , greater<int> ( ) );
 49    sort ( v2b.begin ( ) , v2b.end ( ) , greater<int> ( ) );
 50 
 51    cout << "Original vector v2a with range sorted by the
 "
 52         <<  "binary predicate greater is   v2a =  ( " ;
 53    for ( Iter2a = v2a.begin ( ) ; Iter2a != v2a.end ( ) ; Iter2a++ )
 54       cout << *Iter2a << " ";
 55    cout << ")." << endl;
 56 
 57    cout << "Original vector v2b with range sorted by the
 "
 58         <<  "binary predicate greater is   v2b =  ( " ;
 59    for ( Iter2b = v2b.begin ( ) ; Iter2b != v2b.end ( ) ; Iter2b++ )
 60       cout << *Iter2b << " ";
 61    cout << ")." << endl;
 62 
 63    // Constructing vector v3 with ranges sorted by mod_lesser
 64    vector <int> v3a ( v1a ), v3b ( v1b ) ,  v3 ( v1 );
 65    vector <int>::iterator Iter3a,  Iter3b, Iter3;
 66    sort ( v3a.begin ( ) , v3a.end ( ) , mod_lesser );
 67    sort ( v3b.begin ( ) , v3b.end ( ) , mod_lesser );
 68 
 69    cout << "Original vector v3a with range sorted by the
 "
 70         << "binary predicate mod_lesser is   v3a =  ( " ;
 71    for ( Iter3a = v3a.begin ( ) ; Iter3a != v3a.end ( ) ; Iter3a++ )
 72       cout << *Iter3a << " ";
 73    cout << ")." << endl;
 74 
 75    cout << "Original vector v3b with range sorted by the
 "
 76         << "binary predicate mod_lesser is   v3b =  ( " ;
 77    for ( Iter3b = v3b.begin ( ) ; Iter3b != v3b.end ( ) ; Iter3b++ )
 78       cout << *Iter3b << " ";
 79    cout << ")." << endl;
 80 
 81    // To merge inplace in ascending order with default binary 
 82    // predicate less <int> ( )
 83    merge ( v1a.begin ( ) , v1a.end ( ) , v1b.begin ( ) , v1b.end ( ) , v1.begin ( ) );
 84    cout << "Merged inplace with default order,
 vector v1mod =  ( " ;
 85    for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
 86       cout << *Iter1 << " ";
 87    cout << ")." << endl;
 88 
 89    // To merge inplace in descending order, specify binary 
 90    // predicate greater<int>( )
 91    merge ( v2a.begin ( ) , v2a.end ( ) , v2b.begin ( ) , v2b.end ( ) ,
 92        v2.begin ( ) ,  greater <int> ( ) );
 93    cout << "Merged inplace with binary predicate greater specified,
 "
 94         << "vector v2mod  = ( " ;
 95    for ( Iter2 = v2.begin( ) ; Iter2 != v2.end( ) ; Iter2++ )
 96       cout << *Iter2 << " ";
 97    cout << ")." << endl;
 98 
 99    // Applying A user-defined (UD) binary predicate mod_lesser
100    vector <int>::iterator itRtn = merge ( v3a.begin ( ) , v3a.end ( ) , v3b.begin ( ) , v3b.end ( ) ,
101        v3.begin ( ) ,  mod_lesser );
102    cout << "Merged inplace with binary predicate mod_lesser specified,
 "
103         << "vector v3mod  = ( " ; ;
104    for ( Iter3 = v3.begin( ) ; Iter3 != v3.end( ) ; Iter3++ )
105       cout << *Iter3 << " ";
106    cout << ")." << endl;
107 
108    itRtn --;
109    itRtn --;
110    cout << "*itRtn : " << *itRtn;
111 }

ZC：控制台输出 - 2 (vs2010)：

 1 Original vector v1a with range sorted by the
 2  binary predicate less than is  v1a = ( 0 1 2 3 4 5 ).
 3 Original vector v1b with range sorted by the
 4  binary predicate less than is  v1b = ( -5 -4 -3 -2 -1 0 ).
 5 Original vector v2a with range sorted by the
 6  binary predicate greater is   v2a =  ( 5 4 3 2 1 0 ).
 7 Original vector v2b with range sorted by the
 8  binary predicate greater is   v2b =  ( 0 -1 -2 -3 -4 -5 ).
 9 Original vector v3a with range sorted by the
10  binary predicate mod_lesser is   v3a =  ( 0 1 2 3 4 5 ).
11 Original vector v3b with range sorted by the
12  binary predicate mod_lesser is   v3b =  ( 0 -1 -2 -3 -4 -5 ).
13 Merged inplace with default order,
14  vector v1mod =  ( -5 -4 -3 -2 -1 0 0 1 2 3 4 5 ).
15 Merged inplace with binary predicate greater specified,
16  vector v2mod  = ( 5 4 3 2 1 0 0 -1 -2 -3 -4 -5 ).
17 Merged inplace with binary predicate mod_lesser specified,
18  vector v3mod  = ( 0 0 1 -1 2 -2 3 -3 4 -4 5 -5 ).
19 *itRtn : 5
20 请按任意键继续. . .

1.2、第6讲 PPT.26

◆ sort() : 以默认升序的方式重新排列指定范围内的元素。若要改排序规则，可以输入比较函数。

ZC: 有两种参数格式，返回值是 void 。

ZC: VC6 测试代码 - 1：

 1 #ifdef WIN32
 2 #pragma warning (disable: 4786)
 3 #endif
 4 
 5 #include <vector>
 6 #include <set>
 7 
 8 #include <algorithm>    // 算法
 9 #include <numeric>    // 算法
10 #include <functional>    // 算法
11 
12 using namespace std;
13 
14 void main()
15 {
16     vector<int> vecInt;
17     vecInt.push_back(1);
18     vecInt.push_back(30);
19     vecInt.push_back(5);
20     vecInt.push_back(17);
21     vecInt.push_back(9);
22 
23     sort(vecInt.begin(), vecInt.end());
24 
25     vector<int>::iterator it = vecInt.begin();
26     // ZC: 从这里打印的信息来看，它自动做了排序处理
27     int iIdx = 0;
28     while (it != vecInt.end())
29     {
30         printf("[%02d] ==> *it : %d
", iIdx, *it);
31         it ++;
32         iIdx ++;
33     }
34 }

ZC：控制台输出 - 1：

 1 [00] ==> *it : 1
 2 [01] ==> *it : 2
 3 [02] ==> *it : 3
 4 [03] ==> *it : 4
 5 [04] ==> *it : 5
 6 [05] ==> *it : 6
 7 [06] ==> *it : 7
 8 [07] ==> *it : 8
 9 [08] ==> *it : 9
10 Press any key to continue

ZC: VC6 测试代码 - 2：

 1 #ifdef WIN32
 2 #pragma warning (disable: 4786)
 3 #endif
 4 
 5 #include <string>
 6 #include <vector>
 7 #include <set>
 8 
 9 #include <algorithm>    // 算法
10 #include <numeric>    // 算法
11 #include <functional>    // 算法
12 
13 using namespace std;
14 
15 //学生类
16 class CStudent
17 {
18 public:
19     CStudent(int iID, string strName)
20     {
21         m_iID=iID;  
22         m_strName=strName; 
23     }
24 public:            
25     int m_iID;
26     string m_strName;
27 };
28 
29 //学号比较函数
30 bool Compare(const CStudent &stuA, const CStudent &stuB)
31 {
32     return (stuA.m_iID < stuB.m_iID);
33 }
34 
35 void main()
36 {
37     vector<CStudent> vecStu;
38     vecStu.push_back(CStudent(2, "老二"));
39     vecStu.push_back(CStudent(1, "老大"));
40     vecStu.push_back(CStudent(3, "老三"));
41     vecStu.push_back(CStudent(4, "老四"));
42 
43     sort(vecStu.begin(), vecStu.end(), Compare);
44     //  此时，vecStu容器包含了按顺序的"老大对象","老二对象","老三对象","老四对象"
45 
46     vector<CStudent>::iterator it = vecStu.begin();
47     while (it != vecStu.end())
48     {
49         printf("%s
", it->m_strName.c_str());
50         it ++;
51     }
52 }

ZC：控制台输出 - 2：

1 老大
2 老二
3 老三
4 老四
5 Press any key to continue

1.3、第6讲 PPT.30

◆ random_shuffle() : 对指定范围内的元素随机调整次序。

ZC: 有两种参数格式，返回值是 void

ZC: VC6 测试代码 - 1：

 1 #ifdef WIN32
 2 #pragma warning (disable: 4786)
 3 #endif
 4 
 5 #include <time.h>
 6 
 7 #include <string>
 8 #include <vector>
 9 #include <set>
10 
11 #include <algorithm>    // 算法
12 #include <numeric>    // 算法
13 #include <functional>    // 算法
14 
15 using namespace std;
16 
17 void main()
18 {
19     //设置随机种子
20     srand(time(0));
21 
22     vector<int> vecInt;
23     vecInt.push_back(1);
24     vecInt.push_back(3);
25     vecInt.push_back(5);
26     vecInt.push_back(7);
27     vecInt.push_back(9);
28 
29     string str("UIPower");
30 
31     random_shuffle(vecInt.begin(), vecInt.end());    //随机排序，结果比如：9,7,1,5,3
32     random_shuffle(str.begin(), str.end());            //随机排序，结果比如："owreUIP"
33 
34     vector<int>::iterator it = vecInt.begin();
35     int iIdx = 0;
36     while (it != vecInt.end())
37     {
38         printf("[%02d] ==> %d
", iIdx, *it);
39         it ++;
40     }
41 
42     printf("str : %s
", str.c_str());
43 }

ZC：控制台输出 - 1：

1 [00] ==> 9
2 [00] ==> 1
3 [00] ==> 3
4 [00] ==> 5
5 [00] ==> 7
6 str : IroePUw
7 Press any key to continue

ZC: VC6 测试代码 - 2（来自：http://www.cplusplus.com/reference/algorithm/random_shuffle/）：

 1 // random_shuffle example
 2 #include <iostream>     // std::cout
 3 #include <algorithm>    // std::random_shuffle
 4 #include <vector>       // std::vector
 5 #include <ctime>        // std::time
 6 #include <cstdlib>      // std::rand, std::srand
 7 
 8 // random generator function:
 9 int myrandom (int i)
10 {
11     int iRand = std::rand();
12     int iRtn = iRand % i;
13     printf("%d %% %d ==> %d
", iRand, i, iRtn);
14     return iRtn;
15 
16     //return std::rand()%i;
17 }
18 
19 int main () {
20   std::srand ( unsigned ( std::time(0) ) );
21   std::vector<int> myvector;
22 
23   // set some values:
24   for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
25 
26   // using built-in random generator: // ZC: built-in ==> 内置
27   //std::random_shuffle ( myvector.begin(), myvector.end() ); // ZC: 先把这句代码注释掉，暂时只关注自定义的随机生成函数
28 
29   // using myrandom:
30   std::random_shuffle ( myvector.begin(), myvector.end(), myrandom);
31 
32   printf("
");
33 
34   // print out content:
35   std::cout << "myvector contains:";
36   for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
37     std::cout << ' ' << *it;
38 
39   std::cout << '
';
40 
41   system("pause");
42   return 0;
43 }

ZC：控制台输出 - 2：

 1 4094 % 2 ==> 0
 2 3749 % 3 ==> 2
 3 18714 % 4 ==> 2
 4 6449 % 5 ==> 4
 5 634 % 6 ==> 4
 6 29214 % 7 ==> 3
 7 14374 % 8 ==> 6
 8 8421 % 9 ==> 6
 9 
10 myvector contains: 2 1 4 7 6 5 9 3 8
11 请按任意键继续. . .

ZC：我理解的自定义随机函数变换方式：

1 2 3 4 5 6 7 8 9   原来的顺序（对于第0个元素 不做随机运算）
2 1 3 4 5 6 7 8 9   第1个元素(数字"2") 和 第0个元素 交换位置之后的结果
2 1 3 4 5 6 7 8 9   第2个元素(数字"3") 和 第2个元素 交换位置之后的结果(位置都没动)
2 1 4 3 5 6 7 8 9   第3个元素(数字"4") 和 第2个元素 交换位置之后的结果
2 1 4 3 5 6 7 8 9   第4个元素(数字"5") 和 第4个元素 交换位置之后的结果(位置都没动)
2 1 4 3 6 5 7 8 9   第5个元素(数字"6") 和 第4个元素 交换位置之后的结果
2 1 4 7 6 5 3 8 9   第6个元素(数字"7") 和 第3个元素 交换位置之后的结果
2 1 4 7 6 5 8 3 9   第7个元素(数字"8") 和 第6个元素 交换位置之后的结果
2 1 4 7 6 5 9 3 8   第8个元素(数字"9") 和 第6个元素 交换位置之后的结果

1.4、第6讲 PPT.30

◆ reverse() : 对指定范围内元素重新反序排序。

ZC: 只有一种参数格式，返回值是 void

ZC: VC6 测试代码：

 1 #ifdef WIN32
 2 #pragma warning (disable: 4786)
 3 #endif
 4 
 5 #include <string>
 6 #include <vector>
 7 #include <set>
 8 
 9 #include <algorithm>    // 算法
10 #include <numeric>    // 算法
11 #include <functional>    // 算法
12 
13 using namespace std;
14 
15 void main()
16 {
17     vector<int> vecInt;
18     vecInt.push_back(1);
19     vecInt.push_back(3);
20     vecInt.push_back(5);
21     vecInt.push_back(7);
22     vecInt.push_back(9);
23 
24     reverse(vecInt.begin(), vecInt.end());        //{9,7,5,3,1}
25 
26     vector<int>::iterator it = vecInt.begin();
27     int iIdx = 0;
28     while (it != vecInt.end())
29     {
30         printf("[%02d] ==> %d
", iIdx, *it);
31         it ++;
32     }
33 }

ZC：控制台输出：

1 [00] ==> 9
2 [00] ==> 7
3 [00] ==> 5
4 [00] ==> 3
5 [00] ==> 1
6 Press any key to continue

?.?、第6讲 PPT.?

◆

ZC: VC6 测试代码：

ZC：控制台输出：