常用的排序算法

cpp 评论

常用的排序算法

merge()

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

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

例如：vecIntA,vecIntB,vecIntC是用vector<int>声明的容器，vecIntA已包含1,3,5,7,9元素，vecIntB已包含2,4,6,8元素

vecIntC.resize(9); //扩大容量

merge(vecIntA.begin(),vecIntA.end(),vecIntB.begin(),vecIntB.end(),vecIntC.begin());

此时vecIntC就存放了按顺序的1,2,3,4,5,6,7,8,9九个元素

sort()

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
50
51
52
53
54
55
56
57
58
59
60
61
//学生类

Class CStudent:

{

public:

​    CStudent(int iID, string strName)

​          {

m_iID=iID; 

m_strName=strName; 

}

public:      

​     int m_iID;

​     string m_strName;

}

 

//学号比较函数

bool Compare(const CStudent &stuA,const CStudent &stuB)

{

​          return (stuA.m_iID<strB.m_iID);

}

void main()

{

​    vector<CStudent> vecStu;

​    vecStu.push_back(CStudent(2,"老二"));

vecStu.push_back(CStudent(1,"老大"));

vecStu.push_back(CStudent(3,"老三"));

vecStu.push_back(CStudent(4,"老四"));

 

   sort(vecStu.begin(),vecStu.end(),Compare);

 

// 此时，vecStu容器包含了按顺序的"老大对象","老二对象","老三对象","老四对象"

}

random_shuffle()

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
 random_shuffle:   对指定范围内的元素随机调整次序。

​          srand(time(0));              //设置随机种子

 

​          vector<int> vecInt;

​          vecInt.push_back(1);

​          vecInt.push_back(3);

​          vecInt.push_back(5);

​          vecInt.push_back(7);

​          vecInt.push_back(9);

 

​          string str("itcastitcast ");

​     

​          random_shuffle(vecInt.begin(), vecInt.end());  //随机排序，结果比如：9,7,1,5,3

​          random_shuffle(str.begin(), str.end());         //随机排序，结果比如：" itstcasticat "

reverse()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
       vector<int> vecInt;

​          vecInt.push_back(1);

​          vecInt.push_back(3);

​          vecInt.push_back(5);

​          vecInt.push_back(7);

​          vecInt.push_back(9);

 

​          reverse(vecInt.begin(), vecInt.end());        //{9,7,5,3,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
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<ctime>
#include<cstdlib>

using namespace std;

void printV(vector<int> &v) {

	for (vector<int>::iterator it = v.begin(); it != v.end() ; it++)
	{
		cout << *it << " ";
	}
	cout << endl << "============================" << endl;
}

void test_merge() {
	vector<int> v1;
	v1.push_back(0);
	v1.push_back(1);
	v1.push_back(5);
	v1.push_back(60);
	v1.push_back(1);

	sort(v1.begin(),v1.end());

	vector<int> v2;
	v2.push_back(2);
	v2.push_back(4);
	v2.push_back(6);
	v2.push_back(8);
	sort(v2.begin(), v2.end());
	vector<int> v3;
	v3.resize(v1.size() + v2.size());

	merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());

	printV(v3);


}

class Student {

public:
	Student() {
		m_name = "";
		m_age = 0;
		m_id = 0;
	}
	Student(string name, int id, int age)
	{
		m_name = name;
		m_age = age;
		m_id = id;
	}

	bool operator()(Student & s1, Student & s2) {

		if (s1.m_id <= s2.m_id)
		{
			if (s1.m_id == s2.m_id)
			{
				return s1.m_age >= s2.m_age;
			}
			else {
				return true;
			}
		}
		else {
			return false;
		}

	}

	void printAll() {
		cout << "name: " << m_name << "\tid: " << m_id << "\tage: " << m_age << endl;
	}
private:
	string	m_name;
	int		m_id;
	int		m_age;
};

void printV2(Student & s) {
	s.printAll();
}
void test_sort() {
	vector<int> v1;
	v1.push_back(0);
	v1.push_back(1);
	v1.push_back(5);
	v1.push_back(60);
	v1.push_back(1);

	sort(v1.begin(),v1.end());//默认升序排序
	printV(v1);

	vector<Student> v2;
	v2.push_back(Student("老大",1,22));
	v2.push_back(Student("老大",1,23));
	v2.push_back(Student("老二", 2, 20));
	v2.push_back(Student("老四", 4, 18));
	v2.push_back(Student("老大",1,22));
	v2.push_back(Student("老三", 3, 19));

	sort(v2.begin(),v2.end(),Student());
	for_each(v2.begin(),v2.end(),printV2);

}

void test_random_shuffle() {
	vector<Student> v2;
	v2.push_back(Student("老大", 1, 22));
	v2.push_back(Student("老大", 1, 23));
	v2.push_back(Student("老二", 2, 20));
	v2.push_back(Student("老四", 4, 18));
	v2.push_back(Student("老大", 1, 22));
	v2.push_back(Student("老三", 3, 19));

	srand(time(NULL));

	random_shuffle(v2.begin(),v2.end());
	cout << "========================" << endl;
	for_each(v2.begin(), v2.end(), printV2);

	string str = "1234567";
	random_shuffle(str.begin(), str.end());

	cout << str << endl;
}

void test_reverse() {
	vector<Student> v2;
	v2.push_back(Student("老大", 1, 22));
	v2.push_back(Student("老大", 1, 23));
	v2.push_back(Student("老二", 2, 20));
	v2.push_back(Student("老四", 4, 18));
	v2.push_back(Student("老大", 1, 22));
	v2.push_back(Student("老三", 3, 19));

	sort(v2.begin(), v2.end(), Student());
	reverse(v2.begin(), v2.end());
	for_each(v2.begin(),v2.end(),printV2);
}

int main(char *argv[], int argc)
{
	test_merge();
	test_sort();
	test_random_shuffle();
	test_reverse();
	return 0;
}

YanChen

Personal profile