C++ 基本算法 冒泡法、交换法、选择法、实现代码集合

C++ 基本算法 冒泡法、交换法、选择法

在编程中，基本算法是非常重要的。本文将介绍C++中基本算法的三种实现方式：冒泡排序、交换排序、选择排序，并附上相应的实现代码集合以及示例说明。

冒泡排序

冒泡排序，顾名思义，就像水中的气泡一样，从底部慢慢上升。在排序过程中，每次比较相邻两个元素的大小，如果发现顺序不对，就进行交换，直到所有元素都排列好。冒泡排序的时间复杂度为$O(n^2)$，因此对于大规模数据的排序效率比较低。

实现代码：

void bubble_sort(int array[], int length){
    for(int i = 0; i < length - 1; i++){
        for(int j = 0; j < length - i - 1; j++){
            if(array[j] > array[j+1]){
                std::swap(array[j], array[j+1]);
            }
        }
    }
}

示例说明：

int main() {
    int arr[5] = {5, 3, 2, 4, 1};
    bubble_sort(arr, 5);
    for(int i = 0; i < 5; i++){
        std::cout << arr[i] << " ";
    }
    return 0;
}

输出结果为：1 2 3 4 5，说明成功排列数组中的元素。

交换排序

交换排序也是像冒泡排序一样，通过交换相邻的元素来进行排序。但是，它和冒泡排序的区别在于，交换排序只在确认了所有的比较结果后，再进行元素交换。因此，相比冒泡排序，交换排序的效率会更高。

实现代码：

void exchange_sort(int array[], int length){
    for(int i = 0; i < length - 1; i++){
        int min_idx = i;
        for(int j = i + 1; j < length; j++){
            if(array[j] < array[min_idx]){
                min_idx = j;
            }
        }
        std::swap(array[i], array[min_idx]);
    }
}

示例说明：

int main() {
    int arr[5] = {5, 3, 2, 4, 1};
    exchange_sort(arr, 5);
    for(int i = 0; i < 5; i++){
        std::cout << arr[i] << " ";
    }
    return 0;
}

输出结果为：1 2 3 4 5，说明成功排列数组中的元素。

选择排序

选择排序和冒泡排序和交换排序不同，它并不是每次将相邻的元素进行比较和交换，而是选择一个最小的元素，将它依次放到数组的最前面，然后继续进行选择排序。选择排序的时间复杂度为$O(n^2)$。

实现代码：

void selection_sort(int array[], int length){
    for(int i = 0; i < length-1; i++){
        int min_idx = i;
        for(int j = i + 1; j < length; j++){
            if(array[j] < array[min_idx]){
                min_idx = j;
            }
        }
        if(i != min_idx){
            std::swap(array[i], array[min_idx]);
        }
    }
}

示例说明：

int main() {
    int arr[5] = {5, 3, 2, 4, 1};
    selection_sort(arr, 5);
    for(int i = 0; i < 5; i++){
        std::cout << arr[i] << " ";
    }
    return 0;
}

输出结果为：1 2 3 4 5，说明成功排列数组中的元素。

以上是C++中基本算法冒泡排序、交换排序和选择排序的代码实现和示例说明，希望对读者有所帮助。