算法描述

将待排元素逐个向前相比较，使待排子表中最小的元素浮动到自己的最终位置。每一趟排序确定一个元素的最终位置，最多进行n-1趟排序。

代码实现

// 冒泡排序
#include <iostream>
#include <fstream>
using namespace std;

const int n = 8;

void selection_sort(int arr[]){
    for(int i=0; i<n; ++i){
        for(int j=n-1; j>i; --j){
            if(arr[j] < arr[j-1]){
                int tmp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

int main(){
    fstream inFile;
    inFile.open("in.txt");
    int *arr = new int[n];
    for(int i=0; i<n; ++i)
        inFile >> arr[i];

    selection_sort(arr);    //冒泡排序
    for(int i=0; i<n; ++i)
        cout << arr[i] << " ";

    delete[] arr;
    inFile.close();
    return 0;
}

算法分析

（1）时间复杂度O(n²)，空间复杂度O(1);

（2）冒泡排序是一个稳定的排序算法。