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
|
#include <iostream>
#include <algorithm>
using namespace std;
void Bubble_Sort(int a[], int len)
{
// 冒泡排序，不断比较相邻的数，每次可以选出一个最小或最大的数，是稳定排序
// 相邻比较的次数由外层控制，例如5个数只需要比较4次，所以是 i < len-1
for (int i = 0; i < len-1; i++) {
// 每次冒泡一个最大的数在最后面
// 内层循环比较与外层无关，这里用i避免与后面已排序的进行比较
for (int j = 0; j < len-1-i; j++) {
if (a[j] > a[j+1]) {
swap(a[j], a[j+1]);
}
}
}
for_each(a, a+len, [](int n){ cout << n << " "; });
cout << endl;
}
void Select_Sort(int a[], int len)
{
// 选择排序，每次从无序队列中选择一个最小值，放到有序队列的末尾，不稳定排序
// 比如 2 2 1 这3个元素，把1和第一个2交换，那么原来相同的元素的位置就变化了
for (int i = 0; i < len; i++) {
int min = i;
for (int j = i+1; j < len; j++) {
if (a[j] < a[min]) {
min = j;
}
}
swap(a[i], a[min]);
}
for_each(a, a+len, [](int n){ cout << n << " "; });
cout << endl;
}
void Insert_Sort(int a[], int len)
{
// 插入排序，始终定义第一个元素为有序，将元素逐个插入到有序队列中，是稳定排序
// 需要不断移动数据，空出适当位置把数据插入，所以while循环中j从后向前
for (int i = 1; i < len; i++) {
int temp = a[i];
int j = i-1;
while (j >= 0 && a[j] > temp) {
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
for_each(a, a+len, [](int n){ cout << n << " "; });
cout << endl;
}
// 时间复杂度：数据量变大时，耗时如何变化，对应的还有 空间复杂度
// 时间复杂度：O(NlogN)，其中的Log是以2为底的，比如当数据增大8倍，复杂度只增加3倍(2^3=8)
// 二分查找就是O(logn)的算法，每查找一次排除掉一半，以2为底，这里就是对半分的概念
// 快速排序时间复杂度，最差的情况是，假设pivot是区间最大或最小的那个值，那么对于n个数来说，需要操作n次，
// 而每一次需要遍历剩下的所有元素，时间复杂度就是O(n^2)。
// 最好的情况，刚好可以对半分，对于n个数只需要操作LogN次，所以是O(nLogN)。
void Quick_Sort(int a[], int left, int right)
{
int i = left;
int j = right;
// 快速排序，先选择一个枢轴点，随机或中值，不稳定排序
int pivot = a[(left + right)/2];
// 每个元素与枢轴点比较，两个指针，i向右递增，j向左递减
// 当i和j停下来后，进行元素交换，最后用枢轴点分割数组完成
while (i <= j) {
while (a[i] < pivot)
i++;
while (a[j] > pivot)
j--;
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
if (left < j)
Quick_Sort(a, left, j);
if (i < right)
Quick_Sort(a, i, right);
}
void Merge_Sort(int a[], int left, int right, int temp[])
{
// 归并排序，先把数组不断分割，然后再合并排序所有，是稳定排序
if (left < right) {
int middle = (left + right) / 2;
Merge_Sort(a, left, middle, temp);
Merge_Sort(a, middle + 1, right, temp);
int i = left; // 左边数据起始位置
int j = middle+1; // 右边数据起始位置
int k = left; // 用于temp数组下标
while (i <= middle && j <= right) {
// 如果左边数据较小，则将其放到临时数组里，并将左边位置向后移一位
if (a[i] < a[j]) {
temp[k++] = a[i++];
}
// 否则将右边数据放到临时数组里，并将右边位置向后移一位
else {
temp[k++] = a[j++];
}
}
// 如果左边还有数据，则将剩余的部分全都复制到临时数组里
while (i <= middle) {
temp[k++] = a[i++];
}
// 如果右边还有数据，则将剩余的部分全都复制到临时数组里
// 左右两边只可能存在一边有剩余数据的情况
while (j <= right) {
temp[k++] = a[j++];
}
// 再将临时数组里的数据（已经排好序了）保存到原始数据中，以达到对原始数据的排序
for (k = left; k <= right; k++) {
a[k] = temp[k];
}
}
}
void HeapAdjust(int a[], int len)
{
// 序列调整完之后第一个元素是序列的最大的元素
for (int index = len/2-1; index >= 0; index--) {
//获取该节点的左子节点索引和右子节点索引
int left = index * 2 + 1;
int right = index * 2 + 2;
//暂时把该索引当做最大值所对应的索引
int max = index;
//判断左子节点的值是否大于当前最大值
if (left < len && a[left] > a[max])
max = left;
//判断右子节点的值是否大于当前最大值
if (right < len && a[right] > a[max])
max = right;
//如果该节点不是最大值所在的节点，则将其和最大值节点进行交换
if (max != index)
swap(a[index], a[max]);
}
}
void Heap_Sort(int a[], int len)
{
// 二叉堆是一个近似完全二叉树的结构，性质：子结点的键值或索引总是小于（或者大于）它的父节点。
// 一般都是数组来存储堆，i结点的父结点下标就为(i–1)/2，它的左右子结点下标分别为2*i+1和2*i+2。
// 时间复杂度：O(NlogN)，每次重新恢复堆的时间复杂度为O(logN)，共N-1次重新恢复堆操作。
HeapAdjust(a, len);
for (int i = len-1; i > 0; i--) {
// 将第一个元素与当前最后一个元素交换，保证当前的最后一个位置的元素都是现在的这个序列中最大的
swap(a[0], a[i]);
// 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
HeapAdjust(a, i);
}
for_each(a, a+len, [](int n){ cout << n << " "; });
cout << endl;
}
int main()
{
int a[] = {10, 7, 12, 1, 3, 60, 80, 30};
int size = sizeof(a)/sizeof(a[0]);
}
|