基础数据结构复习-排序

温故而知新。基础虽然简单,但是万变的根本。

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
namespace N {
class sort {
public:

/// <summary>
/// 交换两个数
/// </summary>
template<typename T> void swap(T& a, T& b) {
T temp = a;
a = b;
b = temp;
};

/// <summary>
/// 冒泡排序:比较每个集合内最小的数字,通过两两交换不断把最小的数移到集合最左端,然后从头开始重复寻找第二个最小的数
/// 第一次排序要 N 次比较,然后再寻找的,需要再重复 N-1 次,故我们可以用两个for循环,第二个for循环设置动态边界(即不需要再比较左边最小的数)
/// 复杂度:时间: O(N*N),极端情况,集合顺序正好与需要的顺序相反; 空间:O(1), 没有额外的空间,仅有一个临时变量,可以忽略不计
/// </summary>
template<typename T> void Bubblesort(vector<T>& t) {
int len = t.size();

for (int i = 0; i < len; ++i) {
for (int j = len - 1; j > i; --j) {
if (t[j - 1] > t[j]) {
swap(t[j - 1], t[j]);
}
}
}
};

/// <summary>
/// 选择排序:找出数组内最小的数,然后将其按照所需顺序放在指定的位置
/// 我们需要不断遍历整个数组来寻找最小的数,若数组长度为N,则要遍历 (N-1)+(N-2).....+1
/// 复杂度: 时间:O((N*N)/2), 空间:O(1)
/// 相较于冒泡来说,不需要每次比较都去交换位置。但仍比较暴力
/// </summary>
template<typename T> void Selectionsort(vector<T>& t) {
int len = t.size();
int min;
T val;

for (int i = 0; i < len - 1; ++i) {
min = i;
val = t[i];

for (int j = i + 1; j < len; ++j) {
if (val > t[j]) {
min = j;
val = t[j];
}
}
swap(t[i], t[min]);
}
}

/// <summary>
/// 插入排序: 指定一个有序的集合(若无,可以随机放置一个到该集合),然后用之后为排序的数与该集合进行对比,再进行插入的操作
/// 与冒泡和选择类似,都需要遍历两次,
/// 复杂度:时间: O((N*N)/2), 空间:O(1)
/// 这个相较于冒泡和选择,有了一些改良。减少了一些重复的比较操作
/// </summary>
template<typename T> void Insertsort(vector<T>& t) {
int len = t.size();

for (int i = 1; i < len; ++i) {
for (int j = i; j > 0; --j) {
if (t[j - 1] > t[j]) {
swap(t[j - 1], t[j]);
}
else {
break;
}
}
}

}

/// <summary>
/// 堆排序: 根据完全二叉树结点序列连续的特性(从上到下,从左到右), 将数组中的元素与之对应找出最小最大值。
/// 时间复杂度:由于其需要不断调整堆,且调整一次堆所需时间为logn, 故最坏的情况需要n个数据时,需要O(n*logn)。
/// </summary>
template<typename T> void HeapSort(vector<T>& v, int i) {
buildheap(v, 0);
int len = v.size();
int lastnode = len - 1;

//为取出顶,将其与最后一个结点互换位置,然后将它择出,对剩余结点进行heapify,然后重复以上操作
for (i = lastnode; i > 0; --i) {
swap(v[0], v[i]);
Heapify(v, i, 0);
}
}

/// <summary>
/// 归并排序:将整个序列不断划分到最小单元,进行排序,然后再不断升级原来的大数组进行排序。直接的思想的就是会用到递归。
/// 复杂度:由于要层层递归,故递归的时间时logn, 且每层的时间为n, 故总时间复杂度为O(nlogn)
/// </summary>
template<typename T> void Groupsort(vector<T>& t, int L, int R) {

if (L == R) return;
int mid = (L + R) / 2;
Groupsort(t, L, mid);
Groupsort(t, mid + 1, R);

_GroupSort(t, L, mid+1, R);
}

/// <summary>
/// 快速排序:选一个标准,然后对比,小的放一边,大的放一边,然后再快速排序小的一堆和大的一堆。
/// 提示:当选择数组内某个值当标准时,我们可以将它提取出来利于我们后续对原有数组进行重新排序
/// 复杂度:由于用到递归,且每次递归都要进行n-1次比较,故复杂度为O(nlogn)
/// </summary>
template<typename T> void QuickSort(vector<T>& v, int L, int R) {
T pivot = v[L];
int L_pre = L;
int R_pre = R;

while (L < R) {
if (v[R] < pivot) {
v[L] = v[R];
--R;
}

if (v[L] > pivot) {
v[R] = v[L];
++L;
}
}

v[L] = pivot;

QuickSort(v, L_pre, L);
QuickSort(v, R, R_pre);
}

/// <summary>
///
/// </summary>
private:
//在已有子堆上,不断地建立堆
template<typename T> void Heapify(vector<T>& v, int n, int i) {
if (i > n) return; //叶节点序列不超过结点个数

int l_node = 2 * i + 1;
int r_node = 2 * i + 2;
int max = i;

if (l_node < n && v[i] < v[l_node]) {
max = l_node;
}

if (r_node < n && v[max] < v[r_node]) {
max = r_node;
}

if (max != i) {
swap(v[i], v[max]);
Heapify(v, n, max);
}
}

//构建堆, 从堆中最后一个父节点开始构建
template<typename T> void buildheap(vector<T>& v, int i) {
int len = v.size();
int lastnode = len - 1;
int parent_lastnode = (lastnode - 1)/2;

for (i = parent_lastnode; i >= 0; --i) {
Heapify(v, len, i);
}
}

//对两个有序的部分进行合并
template<typename T> void _GroupSort(vector<T>& v, int L, int M, int R) {
int left_size = M - L;
int right_size = R - M + 1;

vector<T> LeftV(left_size);
vector<T> RightV(right_size);

for (int i = L; i < M; ++i) {
LeftV[i-L] = v[i];
}

for (int i = M; i <= R; ++i) {
RightV[i - M] = v[i];
}

int i = 0, j = 0, k = L;

while (i < left_size && j < right_size) {
if (LeftV[i] < RightV[j]) {
v[k++] = LeftV[i++];
}
else {
v[k++] = RightV[j++];
}
}

while (i < left_size)
v[k++] = LeftV[i++];
while (j < right_size)
v[k++] = RightV[j++];
}
};
};
作者

Dylan Zhu

发布于

2021-03-17

更新于

2021-03-27

许可协议

评论

:D 一言句子获取中...