1. 排序算法概念：
1. 稳定与不稳定：a与b相等情况下，前后位置出现变化为不稳定。
冒泡排序（时间复杂度平均O（n2）、空间复杂度O（1），稳定）：
算法描述
- 比较相邻的元素。
如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
时间复杂度最坏情况O（n2）：每轮循环都有元素交换。
例如：9 8 7 6 5 4 3 2 1
时间复杂度最好情况O（n）：一轮循环没有任何元素交换。
例如：1 2 3 4 5 6 7 8 9
代码详情：
#include
#include
using namespace std;
template
ostream& operator << (ostream& os, const vector& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
os << nums[i];
if (i + 1 < n) {
os << " ";
}
}
return os;
}
class Solution {
private:
int timecount = 0;
public:
vector sort(vector& nums) {
int n = nums.size();
cout << "数组长度：" << n << endl;
bool flag = false; //是否有元素交换顺序
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
++timecount;
if (nums[j] > nums[j + 1]) {
flag = true;
swap(nums[j], nums[j + 1]);
}
}
cout << "当前排序结果：" << nums << " 运行次数：" << timecount << endl;
if (!flag) {
break;
}
}
return nums;
}
};
/*
输入数据：
8 9 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
*/
int main() {
vector nums;
int num = 0;
while (cin >> num) {
nums.push_back(num);
if (cin.get() == '\n') {
break;
}
}
Solution sl;
cout << "最终排序结果：" << sl.sort(nums) << endl;
return 0;
} 快速排序（时间复杂度平均O（nlog2n）、空间复杂度O（nlog2n），不稳定）：
算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。
具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
在这个分区退出之后，该基准就处于数列的中间位置。
这个称为分区（partition） *** 作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
时间复杂度最坏情况O（n2）：每次选择的枢轴都是最小（升序时）或者最大（降序时）。
例如：1 2 3 4 5 6 7 8 9
时间复杂度最好情况O（nlog2n）：每次选择的枢轴都是中间值。
例如：5 3 2 1 4 7 6 8 9
代码详情：
#include
#include
using namespace std;
template
ostream& operator << (ostream& os, const vector& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
os << nums[i];
if (i + 1 < n) {
os << " ";
}
}
return os;
}
class Solution {
private:
int timecount = 0;
public:
vector sort(vector& nums) {
int n = nums.size();
cout << "数组长度：" << n << endl;
Partition(nums, 0, n - 1);
return nums;
}
int QuickSort(vector& nums, int left, int right) {
++timecount;
int i = left + 1, j = right;
while (i <= j) {
while (i < right && nums[i] <= nums[left]) {
++timecount;
++i;
}
while (j > left && nums[j] > nums[left]) {
++timecount;
--j;
}
if (i >= j) {
break;
}
swap(nums[i], nums[j]);
}
swap(nums[left], nums[j]);
cout << "当前排序结果：" << nums << " 运行次数：" << timecount << " left：" << left << " right：" << right << endl;
return j;
}
void Partition(vector& nums, int left, int right) {
++timecount;
if (left >= right) {
return;
}
int mid = QuickSort(nums, left, right);
Partition(nums, left, mid - 1);
Partition(nums, mid + 1, right);
return;
}
};
/*
输入数据：
8 9 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
5 3 2 1 4 7 6 8 9
*/
int main() {
vector nums;
int num = 0;
while (cin >> num) {
nums.push_back(num);
if (cin.get() == '\n') {
break;
}
}
Solution sl;
cout << "最终排序结果：" << sl.sort(nums) << endl;
return 0;
} 简单插入排序（时间复杂度平均O（n2）、空间复杂度O（1），稳定）：
算法描述
一般来说，插入排序都采用in-place在数组上实现。
具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5
时间复杂度最坏情况O（n2）：每次选择都是比前面元素小，例如：9 8 7 6 5 4 3 2 1
时间复杂度最好情况O（n）：每次选择都比前面元素大，例如：1 2 3 4 5 6 7 8 9
代码详情：
#include
#include
using namespace std;
template
ostream& operator << (ostream& os, const vector& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
os << nums[i];
if (i + 1 < n) {
os << " ";
}
}
return os;
}
class Solution {
private:
int timecount = 0;
public:
vector sort(vector& nums) {
int n = nums.size();
cout << "数组长度：" << n << endl;
int preIndex;
int current;
for (int i = 1; i < n; ++i) {
current = nums[i];
preIndex = i - 1;
while (preIndex >= 0 && current < nums[preIndex]) {
++timecount;
nums[preIndex + 1] = nums[preIndex];
--preIndex;
}
nums[preIndex + 1] = current;
cout << "当前排序结果：" << nums << " 运行次数：" << timecount << endl;
}
return nums;
}
};
/*
输入数据：
8 9 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
5 3 2 1 4 7 6 8 9
*/
int main() {
vector nums;
int num = 0;
while (cin >> num) {
nums.push_back(num);
if (cin.get() == '\n') {
break;
}
}
Solution sl;
cout << "最终排序结果：" << sl.sort(nums) << endl;
return 0;
} 希尔排序（时间复杂度平均O（n1.3）、空间复杂度O（1），不稳定）：
算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
时间复杂度最坏情况O（n2）：每次选择的元素都比前面的小，例如：9 8 7 6 5 4 3 2 1
时间复杂度最好情况O（n）：每次选择的元素都比前面大，例如：1 2 3 4 5 6 7 8 9
代码详情：
#include
#include
using namespace std;
template
ostream& operator << (ostream& os, const vector& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
os << nums[i];
if (i + 1 < n) {
os << " ";
}
}
return os;
}
class Solution {
private:
int timecount = 0;
public:
vector sort(vector& nums) {
int n = nums.size();
cout << "数组长度：" << n << endl;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; ++i) {
int preIndex = i - gap;
int current = nums[i];
while (preIndex >= 0 && current < nums[preIndex]) {
++timecount;
nums[preIndex + gap] = nums[preIndex];
preIndex -= gap;
}
nums[preIndex + gap] = current;
cout << "当前排序结果：" << nums << " 运行次数：" << timecount << endl;
}
}
return nums;
}
};
/*
输入数据：
8 9 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
5 3 2 1 4 7 6 8 9
*/
int main() {
vector nums;
int num = 0;
while (cin >> num) {
nums.push_back(num);
if (cin.get() == '\n') {
break;
}
}
Solution sl;
cout << "最终排序结果：" << sl.sort(nums) << endl;
return 0;
} 简单选择排序（时间复杂度平均O（n2）、空间复杂度O（1），不稳定）：
算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。
具体算法描述如下：
- 初始状态：无序区为R[1..n]，有序区为空；
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。
该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- n-1趟结束，数组有序化了。
时间复杂度最坏最好都是情况O（n2）：每轮都有元素交换，例如：9 8 7 6 5 4 3 2 1
代码详情：
#include
#include
using namespace std;
template
ostream& operator << (ostream& os, const vector& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
os << nums[i];
if (i + 1 < n) {
os << " ";
}
}
return os;
}
class Solution {
private:
int timecount = 0;
public:
vector sort(vector& nums) {
int n = nums.size();
cout << "数组长度：" << n << endl;
int Index;
for (int i = 0; i < n - 1; ++i) {
Index = i;
for (int j = i + 1; j < n; ++j) {
++timecount;
if (nums[j] < nums[Index]) {
Index = j;
}
}
swap(nums[i], nums[Index]);
cout << "当前排序结果：" << nums << " 运行次数：" << timecount << endl;
}
return nums;
}
};
/*
输入数据：
8 9 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
5 3 2 1 4 7 6 8 9
*/
int main() {
vector nums;
int num = 0;
while (cin >> num) {
nums.push_back(num);
if (cin.get() == '\n') {
break;
}
}
Solution sl;
cout << "最终排序结果：" << sl.sort(nums) << endl;
return 0;
} 堆排序（时间复杂度平均O（nlog2n）、空间复杂度O（1），不稳定）：
特性：
1. 结构性：用数组表示完全二叉树。
2. 有序性：任一结点的值是其子树所有结点的最大值或最小值。
算法描述
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。
不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
代码详情：
#include
#include
using namespace std;
template
ostream& operator << (ostream& os, const vector& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
os << nums[i];
if (i + 1 < n) {
os << " ";
}
}
return os;
}
class Solution {
private:
int timecount = 0;
public:
vector sort(vector& nums) {
int n = nums.size();
int size = n; //堆大小
cout << "数组长度：" << n << endl;
CreateMaxHeap(nums);
while (size > 0) {
int MaxNum = DeleteMaxHeap(nums, size);
nums[size] = MaxNum;
cout << "当前排序结果：" << nums << " 运行次数：" << timecount << " 当前size：" << size << endl;
}
return nums;
}
void CreateMaxHeap(vector& nums) {
int n = nums.size();
int currentIndex = n / 2;
while (currentIndex > 0) {
int Index = currentIndex;
int TailNum = nums[currentIndex - 1];
while (Index <= n / 2) {
++timecount;
if (TailNum < nums[Index * 2 - 1] && (Index * 2 + 1 > n || nums[Index * 2 - 1] > nums[Index * 2])) {
nums[Index - 1] = nums[Index * 2 - 1];
Index = Index * 2;
}
else if (TailNum < nums[Index * 2] && nums[Index * 2] > nums[Index * 2 - 1]) {
nums[Index - 1] = nums[Index * 2];
Index = Index * 2 + 1;
}
else {
break;
}
}
nums[Index - 1] = TailNum;
--currentIndex;
}
return;
}
int DeleteMaxHeap(vector& nums, int& size) {
int MaxNum = size > 0 ? nums[0] : INT_MIN;
int TailNum = nums[size - 1];
size--;
int Index = 1;
while (Index <= size / 2) {
++timecount;
if (TailNum < nums[Index * 2 - 1] && (Index * 2 + 1 > size || nums[Index * 2 - 1] > nums[Index * 2])) {
nums[Index - 1] = nums[Index * 2 - 1];
Index = Index * 2;
}
else if (TailNum < nums[Index * 2] && nums[Index * 2] > nums[Index * 2 - 1]) {
nums[Index - 1] = nums[Index * 2];
Index = Index * 2 + 1;
}
else {
break;
}
}
nums[Index - 1] = TailNum;
return MaxNum;
}
};
/*
输入数据：
8 9 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
5 3 2 1 4 7 6 8 9
*/
int main() {
vector nums;
int num = 0;
while (cin >> num) {
nums.push_back(num);
if (cin.get() == '\n') {
break;
}
}
Solution sl;
cout << "最终排序结果：" << sl.sort(nums) << endl;
return 0;
} 归并排序（时间复杂度平均O（nlog2n）、空间复杂度O（n），稳定）
算法描述
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
代码详情：
#include
#include
using namespace std;
template
ostream& operator << (ostream& os, const vector& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
os << nums[i];
if (i + 1 < n) {
os << " ";
}
}
return os;
}
class Solution {
private:
int timecount = 0;
public:
vector sort(vector& nums) {
int n = nums.size();
cout << "数组长度：" << n << endl;
mergesort(nums, 0, n - 1);
return nums;
}
void mergesort(vector& nums, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergesort(nums, left, mid);
mergesort(nums, mid + 1, right);
merge(nums, left, mid, mid + 1, right);
return;
}
void merge(vector& nums, int l1, int r1, int l2, int r2) {
vector result(r2 - l1 + 1, 0);
int start = l1;
int i = 0;
while (l1 <= r1 && l2 <= r2) {
result[i++] = nums[l1] <= nums[l2] ? nums[l1++] : nums[l2++];
}
while (l1 <= r1) {
result[i++] = nums[l1++];
}
while (l2 <= r2) {
result[i++] = nums[l2++];
}
for (i = start; i <= r2; ++i) {
nums[i] = result[i - start];
}
return;
}
};
/*
输入数据：
8 9 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
5 3 2 1 4 7 6 8 9
*/
int main() {
vector nums;
int num = 0;
while (cin >> num) {
nums.push_back(num);
if (cin.get() == '\n') {
break;
}
}
Solution sl;
cout << "最终排序结果：" << sl.sort(nums) << endl;
return 0;
} 2. 计算机内部如何存储负数和浮点数？
负数：通过标志位和补码表示。
补码：正数反码加1，方便加减运算。
浮点数：符号位+指数位+尾数部分。
3. 红黑树
红黑树：一种含有红黑结点并能自平衡的二叉搜索树，时间复杂度为O（log2n）。
具有以下性质：
1. 根节点为黑色。
2. 一个结点为红色，它的左右两个孩子结点为黑色。
3. 对于每个结点，从该结点到所有后代叶子结点的简单路径上，均包含相同数目的黑色结点。
4. 最长路径不会超过最短路径两倍。
4.
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）