实现思路：https://blog.csdn.net/morewindows/article/details/6657829
Lintcode:https://www.lintcode.com/problem/sort-integers-ii/description
设数组长度为N。
1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
3．N=N-1，如果N不为0就重复前面二步，否则排序完成。
按照此代码 编写，在LintCode 运行超时，这道题目是nlgN的时间复杂度，冒泡不行，A了80多
public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers2(int[] A) {
// write your code here
BuddleSort(A);
}
public void BuddleSort(int [] A)
{
for(int i=A.length-1;i>0;i--)
{
for(int j=0;j<i;j++)
{
if(A[j] > A[j+1])
{
int temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
}
}下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成
运行结果与第一种一样，超时，看来优化还是不给力
public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers2(int[] A) {
// write your code here
BuddleSort(A);
}
public void BuddleSort(int [] A)
{
boolean flag = false;
for(int i=A.length-1;i>0;i--)
{
flag = false;
for(int j=0;j<i;j++)
{
if(A[j] > A[j+1])
{
int temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
flag = true;
}
}
if(flag == false)
return;
}
}
}再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。
依旧只A了83%,果然冒泡的时间复杂度是无法A这道题的
说一下我的代码思路：只有在冒泡的过程中发生了交换也就是flagSwap = true,那么才说明在索引j与j+1这两个数发生了交换，才标记j+1这个索引（flag =j+1）,如果没发生交换的话，依旧令i=flag会发生循环无法跳出的情况，因为没有交换，flag的值没有变化，如果令i=flag那么会一直重复没有交换，i=flag这个过程，i就一直无法为0结束这个循环，会发生运行时超时的错误，附上我的错误代码，供大家理解我刚才说的话的意思。
代码：
public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers2(int[] A) {
// write your code here
BuddleSort(A);
}
public static void BuddleSort(int [] A)
{
int flag = -1;
boolean flagSwap = false;
for(int i=A.length-1;i>0;i--)
{
flagSwap = false;
for(int j=0;j<i;j++)
{
if(A[j] > A[j+1])
{
int temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
flag = j+1;
flagSwap = true;
}
}
if(flagSwap)
i = flag;
}
}
}错误代码
public static void BuddleSort(int [] A)
{
int flag = -1;
for(int i=A.length-1;i>0;i--)
{
for(int j=0;j<i;j++)
{
if(A[j] > A[j+1])
{
int temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
flag = j+1;
}
}
System.out.println(i + " " + flag+ Arrays.toString(A));
i = flag;
}
}用例，[1, 1, 2, 3, 4, 7, 8, 9]，这样会会一直卡死在i=1,flag=2,然后i=flag i = 2然后在for循环中i减一变成1，然后没交换flag还是2，i=flag这样重复这个过程。
参考链接：https://blog.csdn.net/morewindows/article/details/6665714
最终AC了94%,时间复杂度还是高啊
附上代码：
public class Solution {
public void sortIntegers2(int[] A) {
InsertSort(A);
}
public void InsertSort(int[] A)
{
int i,j,k;
for(i=1;i<A.length;i++)
{
for(j=i-1;j>=0;j--)
{
if(A[j] <= A[i])//寻找第一个小于A[i]的位置,也就是[i]该插入的地方
break;
}
if(j != i-1) //这个判断的意思是如果是刚好A[i-1]这个地方小于A[i],那么不需要操作
{
int temp = A[i];
for(k=i-1;k>j;k--)
A[k+1] = A[k];
A[k+1] = temp;//循环结束k=j,故需要k+1放在该放的位置上
}
}
}
}参考链接：https://blog.csdn.net/morewindows/article/details/6671824
时间复杂度不够，只A了89%
代码：
public class Solution {
public void sortIntegers2(int[] A) {
SelectSort(A);
}
public void SelectSort(int[] A)
{
for(int i=0;i<A.length;i++)
{
int minIndex = i;
for(int j=i;j<A.length;j++)
{
if(A[j] < A[minIndex])
minIndex = j;
}
int temp = A[i];
A[i] = A[minIndex];
A[minIndex] = temp;
}
}
}