Bubble Sort
临近比较，如果逆序，则进行 swap。
Bubble Sort 例子
代码：
public void bubbleSort(int[] array) {
for (int i = array.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (array[j] > array[j+1]) {
swap(array, i, j);
}
}
}
}
时间复杂度： Fixed O(n^2)
空间复杂度：No extra space
Selection Sort
select the smallest unsorted item each time.
Selection Sort 例子
代码：
public void selectionSort(int[] array) {
int smallestIndex = 0;
for (int i = 0; i < array.length; i++) {
smallestIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[smallestIndex]) {
smallestIndex = j;
}
}
swap(array, i, smallestIndex);
}
}
时间复杂度：Fixed O(n^2)
空间复杂度：No extra space
Insertion Sort
each time insert next item to the sorted partial previous to the item.
Insertion Sort 例子
代码：
public void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int j = i;
while (j >= 1 && array[j] < array[j - 1]) {
swap(array, j, j - 1);
}
}
}
对于已经排序好的array，insertion Sort 时间复杂度为 O(n). 所以 insertion Sort 很适合对基本已经排序好的数组进行排序。
worst runtime: O(n^2).
Average runtime: O(n^2)
空间复杂度：No extra space
