首页 > 代码库 > LintCode 整数排序
LintCode 整数排序
题目：给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 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[j];
A[j]^=A[i];
A[i]^=A[j];
}
}
}
}
};
LintCode 整数排序