排序算法-C++实现

排序算法:选择排序,插入排序,冒泡排序,快速排序,堆排序,归并排序,C++实现!

如果对算法的具体思路不太清楚的,建议去B站看看视频,推荐正月点灯笼!

选择排序

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
#include <iostream>
#include <vector>
using namespace std;

void swap(vector<int> & arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

int findMaxIndex(vector<int> & arr, int n) {
int max = arr[0], pos = 0;
for (int i = 0; i < n; ++i) {
if (max < arr[i]) {
pos = i;
max = arr[i];
}
}
return pos;
}

void select_sort(vector<int> & arr) {
int n = arr.size();
while (n > 1) {
int pos = findMaxIndex(arr, n);
swap(arr, pos, n - 1);
--n;
}
}

int main()
{
vector<int> arr{0,2,5,3,3,100,99,10,4};
select_sort(arr);
for (auto item : arr) {
cout << item << endl;
}
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
using namespace std;

void insert_sort(vector<int> & vec) {
int n = vec.size();
for (int i = 1; i < n; ++i) {
int j = i - 1;
while (j >= 0 && vec[j] > vec[j+1]) {
vec[j+1] = vec[j];
--j;
}
vec[j+1] = vec[i];
}
}

int main() {
vector<int> tree{3,1,2,5,6,7,8};
insert_sort(tree);
for (int i = 0; i < tree.size(); ++i)
cout << tree[i] << endl;
return 0;
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void quick_sort(vector<int> & nums, int start, int end){
if (start < end){
int index = getIndex(nums, start, end);
quick_sort(nums, start, index-1);
quick_sort(nums, index+1, end);
}
}

int getIndex(vector<int> & nums, int start, int end){
int pivot = nums[start];
while(start < end){
while(start < end && nums[end] > pivot)
--end;
nums[start] = nums[end];
while(start < end && nums[start] < pivot)
++start;
nums[end] = nums[start];
}
nums[start] = pivot;
return start;
}

堆排序

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>
using namespace std;

void swap(vector<int> & tree, int i, int j) {
int temp = tree[i];
tree[i] = tree[j];
tree[j] = temp;
}
void heapify(vector<int> & tree, int n, int i) {
int child1 = i * 2 + 1;
int child2 = i * 2 + 2;
int maxIndex = i;
if (child1 < n && tree[maxIndex] < tree[child1]) {
maxIndex = child1;
}
if (child2 < n && tree[maxIndex] < tree[child2]) {
maxIndex = child2;
}
if (i != maxIndex) {
swap(tree, maxIndex, i);
heapify(tree, n, maxIndex);
}
}

void build_heap(vector<int> & tree, int n) {
int last_node = n - 1;
int parent = (last_node - 1) / 2;
for (int i = parent; i >= 0; --i) {
heapify(tree, n, i);
}
}
//从小到大排序
void heap_sort(vector<int> & tree) {
build_head(tree, tree.size());
for (int i = tree.size() - 1; i >= 0; --i) {
swap(tree, i, 0);
build_heap(tree, i);
}
}

int main()
{
vector<int> tree{2,5,3,1,10,4};
heap_sort(tree);
for (auto item : tree) {
cout << item << endl;
}
}

冒泡排序

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
#include <vector>
using namespace std;

void swap(vector<int> & arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

void bubble(vector<int> & arr, int n) {
for (int i = 0; i < n-1; ++i) {
if (arr[i] > arr[i + 1])
swap(arr, i, i + 1);
}
}

void bubble_sort(vector<int> & arr) {
for (int i = arr.size(); i >= 1; --i) {
bubble(arr, i);
}
}
//递归实现
//void bubble_sort(vector<int> & arr, int n) {
// if (n == 1)
// return;
// int i = 0;
// while (i < n-1) {
// while (i < n-1 && arr[i] <= arr[i + 1])
// ++i;
// if (i < n -1 && arr[i] > arr[i+1])
// swap(arr, i, i + 1);
// }
// bubble_sort(arr, n - 1);
//}

int main()
{
vector<int> arr{0,2,5,3,3,100,99,10,4};
//bubble_sort(arr, arr.size());
bubble_sort(arr);
for (auto item : arr) {
cout << item << endl;
}
}

归并排序

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
#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int> & arr, int start, int mid, int end) {
int LEFT_SIZE = mid - start + 1;
int RIGHT_SIZE = end - mid;
vector<int> left(LEFT_SIZE), right(RIGHT_SIZE);

for (int i = start; i <= mid; ++i) {
left[i - start] = arr[i];
}
for (int i = mid + 1; i <= end; ++i) {
right[i - mid - 1] = arr[i];
}


int i = 0, j = 0, k = start;
while (i < LEFT_SIZE && j < RIGHT_SIZE) {
if (left[i] < right[j]) {
arr[k++] = left[i++];
}
else {
arr[k++] = right[j++];
}
}
while (i < LEFT_SIZE) {
arr[k++] = left[i++];
}
while (j < RIGHT_SIZE) {
arr[k++] = right[j++];
}

}

void merge_sort(vector<int> & arr, int start, int end) {
if (start == end)
return;
int mid = start + (end - start) / 2;
merge_sort(arr, start, mid);
merge_sort(arr, mid + 1, end);

merge(arr,start, mid, end);
}


int main() {
vector<int> tree{2,3,7,9,4,1,6,5,4,8};
merge_sort(tree,0, tree.size()-1);
for (int i = 0; i < tree.size(); ++i)
cout << tree[i] << endl;
return 0;
}
zxp wechat
欢迎关注微信公众号!