本文共 2768 字，大约阅读时间需要 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/