第四十七课选择排序和插入排序

添加选择排序：

 1 #ifndef SORT_H
 2 #define SORT_H
 3 
 4 #include "Object.h"
 5 
 6 namespace DTLib
 7 {
 8 
 9 class Sort : public Object
10 {
11 private:
12     Sort();
13     Sort(const Sort&);
14     Sort& operator = (const Sort&);
15 
16     template <typename T>
17     static void Swap(T& a, T& b)
18     {
19         T c(a);
20         a = b;
21         b = c;
22     }
23 
24 public:
25     template < typename T >
26     static void Select(T array[], int len)
27     {
28         for(int i = 0; i < len; i++)
29         {
30             int min = i;
31             for(int j = i + 1; j < len; j++)
32             {
33                 if( array[min] > array[j] )
34                 {
35                     min = j;
36                 }
37             }
38 
39             if( min != i)
40             {
41                 Swap(array[i], array[min]);
42             }
43         }
44     }
45 };
46 
47 }
48 
49 #endif // SORT_H

测试程序如下：

 1 #include <iostream>
 2 #include <cstring>
 3 #include "DTString.h"
 4 #include "LinkList.h"
 5 #include "Object.h"
 6 #include "Sort.h"
 7 
 8 using namespace std;
 9 using namespace DTLib;
10 
11 
12 int main()
13 {
14     int array[] = {3, 1, 2, 5, 4};
15 
16     Sort::Select(array, 5);
17 
18     for(int i=0; i < 5; i++)
19     {
20         cout << array[i] << endl;
21     }
22 
23     return 0;
24 }

结果如下：

给Select添加一个参数，支持从小到大排序和从大到小排序：

 1 #ifndef SORT_H
 2 #define SORT_H
 3 
 4 #include "Object.h"
 5 
 6 namespace DTLib
 7 {
 8 
 9 class Sort : public Object
10 {
11 private:
12     Sort();
13     Sort(const Sort&);
14     Sort& operator = (const Sort&);
15 
16     template <typename T>
17     static void Swap(T& a, T& b)
18     {
19         T c(a);
20         a = b;
21         b = c;
22     }
23 
24 public:
25     template < typename T >
26     static void Select(T array[], int len, bool min2max=true)
27     {
28         for(int i = 0; i < len; i++)
29         {
30             int min = i;
31             for(int j = i + 1; j < len; j++)
32             {
33                 if( min2max ? (array[min] > array[j]) : (array[min] < array[j]) )
34                 {
35                     min = j;
36                 }
37             }
38 
39             if( min != i)
40             {
41                 Swap(array[i], array[min]);
42             }
43         }
44     }
45 };
46 
47 }
48 
49 #endif // SORT_H

注意：选择排序是不稳定的。

添加插入排序操作：

 1 #ifndef SORT_H
 2 #define SORT_H
 3 
 4 #include "Object.h"
 5 
 6 namespace DTLib
 7 {
 8 
 9 class Sort : public Object
10 {
11 private:
12     Sort();
13     Sort(const Sort&);
14     Sort& operator = (const Sort&);
15 
16     template <typename T>
17     static void Swap(T& a, T& b)
18     {
19         T c(a);
20         a = b;
21         b = c;
22     }
23 
24 public:
25     template < typename T >
26     static void Select(T array[], int len, bool min2max=true)
27     {
28         for(int i = 0; i < len; i++)
29         {
30             int min = i;
31             for(int j = i + 1; j < len; j++)
32             {
33                 if( min2max ? (array[min] > array[j]) : (array[min] < array[j]) )
34                 {
35                     min = j;
36                 }
37             }
38 
39             if( min != i)
40             {
41                 Swap(array[i], array[min]);
42             }
43         }
44     }
45 
46     template < typename T >
47     static void Insert(T array[], int len, bool min2max=true)
48     {
49         for(int i=1; i < len; i++)  //从1开始，第0个元素没有必要插入操作
50         {
51             int k = i;
52             T e = array[i];
53 
54             for(int j=i-1; (j>=0) && (min2max ? (array[j] > e) : (array[j] < e)); j--)
55             {
56                 array[j+1] = array[j];
57                 k = j;
58             }
59 
60             if( k != i )   //赋值比“比较操作耗时”
61             {
62                 array[k] = e;
63             }
64         }
65     }
66 };
67 
68 }
69 
70 #endif // SORT_H

注意：插入排序是稳定的排序

选择排序的时间复杂度是O(n*n)

插入排序的时间复杂度是O(n*n)

小结：

第四十七课 选择排序和插入排序

第四十七课选择排序和插入排序