LintCode 入门-整数排序

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

冒泡排序：

class Solution {
public:
/**
* @param A: an integer array
* @return: nothing
*/
void sortIntegers(vector<int> &A) {
// write your code here
int length,trans;
length=A.size();
for(int i=0;i<length-1;i++)
{

for(int j=0;j<length-1-i;j++)
{
if(A[j+1]<A[j])
{
trans=A[j];
A[j]=A[j+1];
A[j+1]=trans;
}
}

}
for(int i=0;i<length;i++)
cout<<A[i]<<endl;

}

};

选择排序：

class Solution {
public:
/**
* @param A: an integer array
* @return: nothing
*/
void sortIntegers(vector<int> &A) {
// write your code here
int length,trans;
length=A.size();

//选择排序
for(int i=0;i<length-1;i++)
{
int min=i;
for(int j=i+1;j<length;j++)
if(A[j]<A[min]) min=j;
trans=A[i];
A[i]=A[min];
A[min]=trans;
}
for(int i=0;i<length;i++)
cout<<A[i]<<endl;

}
};

//插入排序

class Solution {
public:
/**
* @param A: an integer array
* @return: nothing
*/
void sortIntegers(vector<int> &A) {
// write your code here
int length,trans;
length=A.size();

for(int i=1;i<length;i++)
{
int v=A[i];
int j=i-1;
while(j>=0&&A[j]>v)
{
A[j+1]=A[j]; //A[j]往后走 v往前走
j=j-1;
A[j+1]=v;
}
}
for(int i=0;i<length;i++)
cout<<A[i]<<endl;
}
};