題目
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]
.
分析
顯然這道題我們可以用冒泡箩言，選擇喷面，插入等排序方法實(shí)現(xiàn)评甜。
就此機(jī)會正好復(fù)習(xí)一下這三種復(fù)雜度為 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);
}
}
}
}
小結(jié)
三種排序都用了兩個for循環(huán)實(shí)現(xiàn)。實(shí)現(xiàn)這三種排序的代碼很多荣恐，也可以用while循環(huán)實(shí)現(xiàn)。重要的是三種排序方法的思想以及將算法轉(zhuǎn)換為代碼的能力
