C++冒泡排序

思想：

     从左到右，相邻两数两两比较，若下标小的数大于下标大的数则交换，将最大的数放在数组的最后一位(即下标n-1的位置)
    
     采用相同的方法，再次遍历数组，将第二大的数，放在数组倒数第二的位置(即n-2的位置)，以此类推，直到数组有序
    
     优化：当数组在整个遍历过程中没有发生交换，说明待排序数组已经有序，此时可以直接结束排序过程(用bool类型变量作标记)。

代码：

#include<iostream>#include<vector>usingnamespace std;voidbubbleSort(vector<int>&vec,int n){for(int j = n; j >=1; j--){bool flag =true;for(int i =0; i < j -1; i++){if(vec[i]> vec[i +1]){swap(vec[i], vec[i +1]);
                flag =false;}}if(flag)return;}}intmain(){
    vector<int>vec ={2,3,5,8,9,7,4,6,1};bubbleSort(vec, vec.size());for(auto it : vec){
        cout << it <<" ";}return0;}

时间复杂度：

    最好时间复杂度(有序情况)：O(n)
    比较n-1次，交换0次 故最好时间复杂度为O(n)

    最坏时间复杂度(逆序情况):O(n2)
    第一次排序时是n个元素，比较n-1次,交换n-1次
    第二次排序时是n-1个元素，比较n-2次，交换n-2次
    ...
    第n-1次排序时是2个元素，比较1次，交换1次
    第n次排序时是1个元素，比较0次，交换0次
    故选择排序时间复杂度为O((1+2+3+...+n-1)*2)=O(n*(n-1))=O(n2) 

空间复杂度：

    在原数组上操作，即使用了常数级空间O(1)

投稿来自 指针38期 - 东北石油大学 - 大数据201 - 金树正