C++自学精简教程 目录(必读)
1 前驱知识点
3.5 for循环语句 3.6 if语句 3.7 函数 3.8 动态内存
2 排序
是将元素按照从小到大的顺序存放的方法。
一开始元素可能并不是按照从小到大的顺序存放的。
这时候我们需要找到需要调整的元素对，并交换这两个元素的值，不断重复这个过程，最终让所有元素都按照从小到大的顺序存放。
3 冒泡排序
Bubble Sort 是一种思路很简单的排序方法。
冒泡的泡是指当前待排序的序列中元素最大的那个元素，我们找到这个元素，并把这个元素放到最后一个位置，那么最大的元素就已经排好序了（冒泡了）。
这时候再将剩下的元素序列用同样的方法处理，就会出现所有元素中第二大的元素冒泡，第3大的元素冒泡，一直到最后一个元素不用冒泡了。全部元素就排好序了。
待排序数据
49,38,65,97,76,13,27,49
过程见下图
4 代码实现
4.1 普通代码实现（眉毛胡子一把抓）
下面的代码只用了一个BubbleSort函数，代码都集中在这一个函数里，细节很多，比较容易写错。
#include <iostream>
using namespace std;
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n; i++) { // i-th pass
for (int j = 1; j < n-i; j++) {
if (arr[j - 1] > arr[j]) { // swap if out of order
//(1) your code
// swap arr[j-1] and arr[j]
}
}
}
}
int main()
{
int n = 8;
int* arr = new int[n]{49,38,65,97,76,13,27,49};//申请8个int变量,并初始化
//执行排序
BubbleSort(arr, 8);
//输出排序后的序列
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
delete[] arr;//释放动态数组需要用delete[]
return 0;
}
输出结果：
4.2 使用更多函数
让代码更清晰的方法！
我们将冒泡函数Bubble提出出来，交换两个变量的值的函数Swap也提取出来，代码一下子简单了很多。
#include <iostream>
using namespace std;
//打印数组中的每一个元素
void print_array(int* arr, int length)
{
for (int i = 0; i < length; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
//swap two number
void Swap(int& a, int& b)
{
int tmp = a; a = b; b = tmp;
}
//put max element to the end
void Bubble(int* arr, int length)
{
for (int j = 1; j < length; j++) {
if (arr[j - 1] > arr[j]) { // swap if out of order [j-1] and [j]
//(2) your code
}
}
}
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n; i++) { // i-th pass
Bubble(arr, n - i);//put max element to the end
print_array(arr, n);
}
}
int main()
{
int n = 8;
int* arr = new int[n] {49, 38, 65, 97, 76, 13, 27, 49};//申请8个int变量,并初始化
//执行排序
BubbleSort(arr, 8);
//输出排序后的序列
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
delete[] arr;//释放动态数组需要用delete[]
return 0;
}
输出结果：
4.3 使用仿函数
将比较两个整数的功能单独用一个仿函数来实现。
#include <iostream>
#include <functional>
using namespace std;
//打印数组中的每一个元素
void print_array(int* arr, int length);
//swap two number
void Swap(int& a, int& b)
{
int tmp = a; a = b; b = tmp;
}
//put max element to the end
void Bubble(int* arr, int length, function<bool(int, int)>& compare)
{
for (int j = 1; j < length; j++) {
if (!compare(arr[j - 1], arr[j])) { // swap if out of order [j-1] and [j]
//(2) your code
Swap(arr[j - 1], arr[j]);
}
}
}
void BubbleSort(int* arr, int n, function<bool(int, int)>& compare)
{
for (int i = 0; i < n; i++) { // i-th pass
Bubble(arr, n - i, compare);//put max element to the end
print_array(arr, n);
}
}
int main()
{
int n = 8;
int* arr = new int[n] {49, 38, 65, 97, 76, 13, 27, 49};//申请8个int变量,并初始化
function<bool(int, int)> compare = [](int a, int b) { return a < b; };//升序
//执行排序
BubbleSort(arr, 8, compare);
//输出排序后的序列
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
delete[] arr;//释放动态数组需要用delete[]
return 0;
}
//打印数组中的每一个元素
void print_array(int* arr, int length)
{
for (int i = 0; i < length; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
输出结果：
38 49 65 76 13 27 49 97
38 49 65 13 27 49 76 97
38 49 13 27 49 65 76 97
38 13 27 49 49 65 76 97
13 27 38 49 49 65 76 97
13 27 38 49 49 65 76 97
13 27 38 49 49 65 76 97
13 27 38 49 49 65 76 97
13 27 38 49 49 65 76 97
