#include<iostream>
using namespace std;
int main() {
	int arr[100]={999999,3,1,5,7};
	int n = 4;
	for(int i=1;i<=n-1;i++){
		for(int j=i+1;j<=n;j++){
			if(arr[i] > arr[j]){
				swap(arr[i],arr[j]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<arr[i]<<" ";
	}
	return 0;
}

C++排序算法教程（冒泡排序、插入排序、选择排序）——0基础详细讲解

一、什么是排序？

排序（Sorting），就是将一组数据按照某种规则（如从小到大或从大到小）排列的过程。它是计算机科学中最基础、最常见的操作之一。

在本教程中，我们将学习三种最基本的排序算法：

1. 冒泡排序（Bubble Sort）
2. 插入排序（Insertion Sort）
3. 选择排序（Selection Sort）

这些排序算法虽然效率不高，但非常适合初学者理解排序的基本思想。

---

二、准备工作：C++数组和循环基础

我们使用一个整型数组 arr[] 来存储待排序的数据。例如：

int arr[] = {5, 3, 8, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度

我们也会用到两层嵌套循环来实现排序逻辑。

---

三、冒泡排序（Bubble Sort）

📌 原理：

冒泡排序通过重复遍历数组，比较相邻的两个元素，如果顺序错误就交换它们，这样每一轮可以“冒”出一个最大的数到最后。

🧠 理解方式：

想象气泡从水底上升一样，较小的元素慢慢“浮”上来。

🔢 时间复杂度：

• 最坏情况：O(n²)
• 最好情况（已排序）：O(n)

✅ 示例代码：

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {               // 控制轮数
        for (int j = 0; j < n - i - 1; j++) {       // 控制每轮比较次数
            if (arr[j] > arr[j + 1]) {              // 如果前一个比后一个大，交换
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    cout << "冒泡排序结果: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    
    return 0;
}

---

四、插入排序（Insertion Sort）

📌 原理：

插入排序就像你整理扑克牌一样，把一个元素插入到它前面已经排好序的部分中的正确位置。

🧠 理解方式：

每次取出一个元素，把它插入到前面合适的位置，使得前面始终是有序的。

🔢 时间复杂度：

• 最坏情况：O(n²)
• 最好情况（已排序）：O(n)

✅ 示例代码：

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {          // 从第二个元素开始
        int key = arr[i];                  // 当前要插入的元素
        int j = i - 1;

        // 将比key大的元素向后移动一位
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;   // 插入到正确位置
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    cout << "插入排序结果: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    
    return 0;
}

---

五、选择排序（Selection Sort）

📌 原理：

选择排序通过不断查找未排序部分中的最小值，并将其放到当前轮次的起始位置。

🧠 理解方式：

每次都选出最小的，放到最前面。

🔢 时间复杂度：

• 所有情况都是 O(n²)

✅ 示例代码：

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {         // 控制轮数
        int minIndex = i;

        // 在剩下的元素中找最小值的索引
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        swap(arr[i], arr[minIndex]);   // 把最小值放到当前位置
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    cout << "选择排序结果: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    
    return 0;
}

---

六、总结对比

---

七、动手练习建议

你可以尝试以下练习加深理解：

1. 修改排序方向为从大到小。
2. 输入由用户输入而非固定数组。
3. 对比不同算法对同一组数据的运行时间差异（可以用 clock() 测试时间）。
4. 尝试分析每种算法的步骤，画出过程示意图。

---

八、结语

虽然这三种排序算法的时间复杂度较高，在实际开发中可能不会单独使用，但它们是理解更高级排序算法（如快速排序、归并排序等）的基础。掌握它们有助于你培养编程思维和算法逻辑。

如果你有任何疑问或者希望继续学习其他排序算法（比如快速排序、归并排序、堆排序等），欢迎继续提问！

---

📌 下一步推荐学习内容：
✅ 快速排序（Quick Sort）
✅ 归并排序（Merge Sort）
✅ 排序算法稳定性与应用场景分析

下面是添加了详细注释的冒泡排序C++代码：

#include <iostream>
#include <vector>

// 冒泡排序函数，接收一个整数向量作为待排序的数组
void bubbleSort(std::vector<int>& arr) {
    // 获取数组的长度
    int n = arr.size();
    // 外层循环控制比较的轮数，总共需要进行 n - 1 轮
    for (int i = 0; i < n - 1; ++i) {
        // 内层循环控制每一轮比较的次数，每一轮比较后，最大的元素会“浮”到数组的末尾
        // 所以每一轮比较的次数会逐渐减少
        for (int j = 0; j < n - i - 1; ++j) {
            // 如果当前元素大于下一个元素，则交换它们的位置
            if (arr[j] > arr[j + 1]) {
                // 临时变量，用于交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    // 初始化一个待排序的数组
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    // 调用冒泡排序函数对数组进行排序
    bubbleSort(arr);
    // 输出排序后的数组
    std::cout << "冒泡排序后的数组: ";
    // 遍历数组并输出每个元素
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

以上代码添加了详细的注释，解释了每一步的作用，希望能帮助你更好地理解冒泡排序的实现过程。

以下为你详细介绍三种基础的排序算法：冒泡排序、插入排序和选择排序，适合零基础的你学习。

1. 冒泡排序

冒泡排序是一种简单的排序算法，它会重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

以下是冒泡排序的C++代码示例：

#include <iostream>
#include <vector>

// 冒泡排序函数
void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    std::cout << "冒泡排序后的数组: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

代码解释：

• bubbleSort 函数接收一个整数向量 arr 作为参数。
• 外层循环 i 控制比较的轮数，总共需要进行 n - 1 轮，其中 n 是数组的长度。
• 内层循环 j 控制每一轮比较的次数，每一轮比较后，最大的元素会“浮”到数组的末尾，所以每一轮比较的次数会逐渐减少。
• 如果当前元素 arr[j] 大于下一个元素 arr[j + 1]，则交换它们的位置。

2. 插入排序

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

以下是插入排序的C++代码示例：

#include <iostream>
#include <vector>

// 插入排序函数
void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        // 将比 key 大的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        // 插入 key
        arr[j + 1] = key;
    }
}

int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    insertionSort(arr);
    std::cout << "插入排序后的数组: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

代码解释：

• insertionSort 函数接收一个整数向量 arr 作为参数。
• 外层循环 i 从第二个元素开始，将其作为待插入的元素 key。
• 内层循环 j 从 i - 1 开始向前扫描，将比 key 大的元素向后移动一位。
• 最后将 key 插入到合适的位置。

3. 选择排序

选择排序的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

以下是选择排序的C++代码示例：

#include <iostream>
#include <vector>

// 选择排序函数
void selectionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        // 找到最小元素的索引
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换最小元素和当前元素
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    selectionSort(arr);
    std::cout << "选择排序后的数组: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

代码解释：

• selectionSort 函数接收一个整数向量 arr 作为参数。
• 外层循环 i 控制当前要确定位置的元素。
• 内层循环 j 从 i + 1 开始寻找最小元素的索引 minIndex。
• 如果 minIndex 不等于 i，则交换 arr[i] 和 arr[minIndex] 的位置。

这些排序算法的时间复杂度都是 $O(n^2)$，适合处理小规模的数据。希望通过这些示例和解释，你能对这三种排序算法有更深入的理解。