题目：给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法。
1.冒泡：从头开始，比较相邻的两个元素，大的放在后面。一轮结束之后，最大的数沉底，不参与下一轮比较。重复 直至待排序的元素个数为1。
class Solution
{
public:
/*** @param A an integer array @return void*/
void sortIntegers(vector<int>& A) {
if(A.size()!=0)//一定要进行判断，否则A中无元素时不成立
{for (int i = 0; i < A.size()-1; i++)
{ for (int j = 0; j < A.size()-1-i; j++)
{if (A[j] > A[j+1])
{A[j]^=A[j+1];
A[j+1]^=A[j];
A[j]^=A[j+1];
}
}
}
}
}
};
优化的冒泡：序而不排
class Solution
{
public:
/*** @param A an integer array @return void*/
void sortIntegers(vector<int>& A) {
if(A.size()!=0)//一定要进行判断，否则A中无元素时不成立 {
for (int i = 0; i < A.size()-1; i++) {
int flag=0;//标志位
for (int j = 0; j < A.size()-1-i; j++) {
if (A[j] > A[j+1]) {
A[j]^=A[j+1];
A[j+1]^=A[j];
A[j]^=A[j+1];
flag=1;
}
}
if(flag==0)
break;
}
}
}
};
2.选择排序：取首元素，同其后所有的元素一一比较，若大就交换。一轮之后，首元素有序，之后在重复。
class Solution
{
public:
/*** @param A an integer array @return void*/
void sortIntegers(vector<int>& A) {
if(A.size()!=0)//一定要进行判断，否则A中无元素时不成立
{for (int i = 0; i < A.size()-1; i++)
{ for (int j = i+1; j < A.size(); j++)
{if (A[i ]> A[j])
{A[i]^=A[j];
A[j]^=A[i];
A[i]^=A[j];
}
}
}
}
}
};
选择优化：比而不换(只记录下标)
class Solution
{
public:
/*** @param A an integer array @return void*/
void sortIntegers(vector<int>& A) {
if(A.size()!=0)//一定要进行判断，否则A中无元素时不成立
{ int idx;
for (int i = 0; i < A.size()-1; i++)
{ idx=i;
for (int j = i+1; j < A.size(); j++)
{
if(A[idx]>A[j]
idx=j;
}
if(idx!=i)
{A[i]^=A[idx];
A[idx]^=A[i];
A[i]^=A[idx];}
}
}
}
}
};