Fork me on GitHub

排序算法@C++描述-插入排序

1.插入排序

普通版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
template <typename T>
void insertionSort(vector<T> &a)
{
int i;
for (int j = 1; j < a.size(); j++) {
T tmp = a[j];
for (i = j; i > 0 && tmp < a [i - 1]; i--)
a[i] = a[i - 1];
a[i] = tmp;
}
}
int main()
{
vector<int> test = {190, 435, 834, 8954, 923, 56, 20 ,1, 934};
clock_t time_stt = clock();
insertionSort(test);
cout << "Total time: " << 1000 * (clock() - time_stt) / (double)CLOCKS_PER_SEC << "ms" << endl;
for (auto i : test)
cout << i << " ";
cout << endl;
return 0;
}
  • 运行结果:
    1
    2
    3
    $ ./a.out
    Total time: 0.002ms
    1 20 56 190 435 834 923 934 8954

STL实现版本(模仿STL sort() 接口)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
// 模仿STL sort()接口
template <typename Iterator, typename Object, typename Functor>
void insertionSort(const Iterator &begin, const Iterator &end, Functor func, const Object &obj)
{
Iterator i;
for (Iterator j = begin + 1; j != end; j++) {
Object tmp = *j;
for (i = j; i != begin && func(tmp, *(i - 1)); i--)
*i = *(i - 1);
*i = tmp;
}
}
template <typename Iterator, typename Functor>
void insertionSort(const Iterator &begin, const Iterator &end, Functor func)
{
insertionSort(begin, end, func, *begin);
}
template <typename Iterator, typename Object>
void _insertionSort(const Iterator &begin, const Iterator &end, const Object &obj)
{
insertionSort(begin, end, less<Object>());
}
template <typename Iterator>
void insertionSort(const Iterator &begin, const Iterator &end)
{
_insertionSort(begin, end, *begin);
}
int main()
{
vector<int> test = {190, 435, 834, 8954, 923, 56, 20 ,1, 934};
clock_t time_stt = clock();
insertionSort(test.begin(), test.end());
cout << "Total time: " << 1000 * (clock() - time_stt) / (double)CLOCKS_PER_SEC << "ms" << endl;
for (auto i : test)
cout << i << " ";
cout << endl;
return 0;
}
  • 运行结果:
    1
    2
    3
    $ ./a.out
    Total time: 0.005ms
    1 20 56 190 435 834 923 934 8954

仿函数

此时引入了仿函数(也叫函数结构,functor),可以对排序顺序进行自定义

比如可以利用lambda讲排序结果反过来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
// 模仿STL sort()接口
template <typename Iterator, typename Object, typename Functor>
void insertionSort(const Iterator &begin, const Iterator &end, Functor func, const Object &obj)
{
Iterator i;
for (Iterator j = begin + 1; j != end; j++) {
Object tmp = *j;
for (i = j; i != begin && func(tmp, *(i - 1)); i--)
*i = *(i - 1);
*i = tmp;
}
}
template <typename Iterator, typename Functor>
void insertionSort(const Iterator &begin, const Iterator &end, Functor func)
{
insertionSort(begin, end, func, *begin);
}
template <typename Iterator, typename Object>
void _insertionSort(const Iterator &begin, const Iterator &end, const Object &obj)
{
insertionSort(begin, end, less<Object>());
}
template <typename Iterator>
void insertionSort(const Iterator &begin, const Iterator &end)
{
_insertionSort(begin, end, *begin);
}
int main()
{
vector<int> test = {190, 435, 834, 8954, 923, 56, 20 ,1, 934};
clock_t time_stt = clock();
insertionSort(test.begin(), test.end(), [](int a, int b){
if (a > b)
return 1;
else
return 0;
});
cout << "Total time: " << 1000 * (clock() - time_stt) / (double)CLOCKS_PER_SEC << "ms" << endl;
for (auto i : test)
cout << i << " ";
cout << endl;
return 0;
}
  • 运行结果:
    1
    2
    3
    $ ./a.out
    Total time: 0.006ms
    8954 934 923 834 435 190 56 20 1