本文共 2851 字，大约阅读时间需要 9 分钟。

冒泡排序、选择排序、插入排序

冒泡排序（BubbleSort）

冒泡排序是一种简单但效率较低的排序算法，通过多次对相邻元素进行比较和交换，最终将数组按升序排序。

工作原理

步骤如下：

这意味着，每次经过一趟扫描，你都会找到当前数组中的最大值，并逐步将数组整理有序。

代码示例

#include 
   
    
#include 
    
     
using namespace std;
void BubbleSort(vector
     
       &arr) {
    int n = arr.size();
    if (n < 2) {
        return;
    }
    for (int i = 0; i < n; ++i) {
        bool changed = false;
        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;
                changed = true;
            }
        }
        if (!changed) break;
    }
}
int main() {
    vector
      
        arr = {9, 8, 7, 5, 7, 3, 4, 1};
    BubbleSort(arr);
    for (int i : arr) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
      
     
    
   

运行结果：

冒泡排序后的数组为：1 3 4 5 7 7 8 9

选择排序（SelectionSort）

选择排序通过每次找出当前未排序区间内的最小值，将其交换到目标位置，最终完成排序。

工作原理

步骤如下：

代码示例

#include 
   
    
#include 
    
     
using namespace std;
void DataSwap(int &data1, int &data2) {
    int temp = data1;
    data1 = data2;
    data2 = temp;
}
void SelectionSort(vector
     
       &arr) {
    int n = arr.size();
    if (n < 2) {
        return;
    }
    for (int i = 0; i < n - 1; ++i) {
        int min_index = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        if (min_index != i) {
            DataSwap(arr[min_index], arr[i]);
        }
    }
}
int main() {
    vector
      
        arr = {9, 8, 7, 5, 7, 3, 4, 1};
    SelectionSort(arr);
    for (int i : arr) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
      
     
    
   

运行结果：

选择排序后的数组为：1 3 4 5 7 7 8 9

插入排序（InsertionSort）

插入排序通过将每个元素插入到其适当的位置，逐步生成一个有序的数组。

工作原理

步骤如下：

由于插入操作的性质，插入排序的效率较高，特别适用于有局部有序的情况。

代码示例

#include 
   
    
#include 
    
     
using namespace std;
void InsertionSort(vector
     
       &arr) {
    int n = arr.size();
    if (n < 2) {
        return;
    }
    for (int i = 1; i < n; ++i) {
        int tmp = arr[i];
        int j = i - 1;
        while (j >= 0 && tmp < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = tmp;
    }
}
int main() {
    vector
      
        arr = {9, 8, 7, 5, 7, 3, 4, 1};
    InsertionSort(arr);
    for (int i : arr) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
      
     
    
   

运行结果：

插入排序后的数组为：1 3 4 5 7 7 8 9

总结

这三种排序算法各有优缺点：

• 冒泡排序：简单易懂，但效率较低。
• 选择排序：逐步完善，但几次比较可能较多。
• 插入排序：适合有局部有序的情况，效率较高。

根据具体需求选择合适的排序方法，能优化算法性能。

转载地址：http://ctuiz.baihongyu.com/