题目
Given an integer array, sort it in ascending order. Use selection sort, bubble sort, insertion sort or any O(n2) algorithm.
Example Given[3, 2, 1, 4, 5] , return[1, 2, 3, 4, 5]
.
分析
显然这道题我们可以用冒泡，选择，插入等排序方法实现。
就此机会正好复习一下这三种复杂度为 O(n2)的排序算法
解答
冒泡排序
public class Bubble {
public static void sort(int a[])
{
int N = a.length;
for(int i=0;i<N;i++)
{
for(int j=0;j<N-i-1;j++)
{
if(a[j+1]<a[j])
exch(a,j,j+1);
}
}
}
}
选择排序
public class Selection {
public static void sort(int a[])
{
int N = a.length;
for(int i=0;i<N;i++)
{
int min = i;
for(int j=i+1;j<N;j++)
{
if(a[j]<a[min])
min = j;
}
exch(a,i,min);
}
}
}
插入排序
public class Insert {
public static void sort(int a[])
{
int N = a.length;
for(int i=1;i<N;i++)
{
for(int j=i;j>0 && a[j]<a[j-1];j--)
{
exch(a,j,j-1);
}
}
}
}
小结
三种排序都用了两个for循环实现。实现这三种排序的代码很多，也可以用while循环实现。重要的是三种排序方法的思想以及将算法转换为代码的能力
