463.整数排序

描述

给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法。

 您在真实的面试中是否遇到过这个题？  
 是

样例对于数组 [3, 2, 1, 4, 5], 排序后为：[1, 2, 3, 4, 5]。

采用 冒泡排序：
最坏时间复杂度{\displaystyle O(n^{2})}
最优时间复杂度{\displaystyle O(n)}
平均时间复杂度{\displaystyle O(n^{2})}
空间复杂度总共{\displaystyle O(n)}，需要辅助空间{\displaystyle O(1)}

class Solution {
public:
    /**
     * @param A: an integer array
     * @return: nothing
     */
    void sortIntegers(vector<int> &A) {
        // write your code here
        if(A.size()!=0){
            for(int i=0;i<A.size()-1;i++){
                for(int j=0;j<A.size()-1;j++){
                    swap(A[j],A[j+1]);
                }
            }
        }
    }
    
    void swap(int &a,int &b){
        if(a>b){
            a^=b;
            b^=a;
            a^=b;
        }
    }
};